Javascript Object

자바스크립트에서의 Object,Map이 굉장하게 유사해보인다. 둘 다 key,value를 저장한다는 점에서 똑같아 보인다.

• 크게 차이를 보이는 점은 다음과 같다.(https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map)
  1. key로 가능한 자료형
     • Map : 모든 값이 키로 가능.
     • Object: String이나 Symbol만 가능.
  2. 삽입순서.
     • Map : 키가 정렬되어 삽입.
     • Object : 키가 정렬 X
  3. 크기
     • Map : size를 통해 크기를 쉽게 파악 가능.
     • Object : 키를 모두 구해야 알 수 있음.

그래서 데이터를 만들어 놓고 수정,삭제가 필요가 없으면 Object가 좀 더 나은 성능을 보인다. 하지만 데이터의 크기가 변경되는 수정, 데이터의 삭제의 경우 Map이 더 나은 성능을 가진다.

처음에는 map은 key값으로 찾는다고 잘못 알고 있었다. map은 redblacktree로 보통 구현해서 logN의 복잡도를 가진다. 하지만 object는 키 값을 이용해서 찾기 때문에 상수 시간 복잡도를 가진다.

Map과 HashMap의 차이.

두 데이터 구조에서의 차이는 key값으로 바로 접근하냐 아니냐의 차이인 것 같다.

hashmap은 키값을 해쉬함수를 이용해 인덱스 값으로 바꾸고 그것을 배열에 저장하기 때문에 탐색 삭제 추가 같은 경우에 속도가 상수값이다.

Map의 경우에는 redblacktree와 같은 자료구조를 이용해 구현하기 때문에 logn의 시간이 걸린다.

이렇게만 보면 hashmap이 훨씬 좋아보인다. 하지만 hashmap은 배열에 저장하는 것이기 때문에 처음 메모리를 크게 할당해줘야한다. Map은 추가할 때마다 늘리면 되지만, hashmap은 배열의 인덱스를 사용하기 때문에 그것이 불가능하다.

그리고, hashmap은 정말 작은 확률이지만, 충돌의 가능성이 크다(bucket size가 작을수록). 충돌 가능성의 크기가 크면 클수록 시간도 더 걸린다.

효율적인 hash 키를 생성

hash키를 생성하는데에는 많은 방법들이 있다. 좋은 hashing함수는

1. 효율적이여야한다.(해싱 하는 과정이 빨라야함.)
2. 같은 키를 가질 확률이 정말 많이 낮아야한다.

사실 hashmap은 키 값을 만들어줘야하는 특성때문에,

임의의 랜덤 숫자를 hashmap의 사이즈로 나눈 나머지(값을 넣을 때 좋음)을 사용하기도 하고,

key의 비트 표현 값에 key비트표현 * A(A = s/2^w) 등등 정말 많은 방법들이 존재하는 것 같다.

또 해싱함수들의 집단을 만들어놓고 해싱을 하고 값이 같으면 또 해싱함수를 불러와서 해싱하는 경우도 있다고 한다.

이 중 뭐가 좋은 hash방법인지는 잘 모르겠다..