여기서 보조 해시 함수가 사용되는 것을 볼 수 있는데 바로 해쉬 값에 상위 16비트 값을 XOR 연산 하는 것 입니다.
3가지 Map 모두 Thread-Safe하지 않습니다.
동기화를 위해서는 CocurrentHashMap, ConcurrentSkipListMap 등을 사용합니다.
HashMap의 해시 버킷 인덱스 값으로 해시 값에 나머지 연산을 한 값을 사용하는데 이 값은 서로 다른 키라도 중복될 수 있습니다. 이 상황을 충돌 또는 해쉬 충돌이라고하고 이 상황을 해결하는 방법으로 Open Addressing과 Seperate Chaining이 있습니다.
JAVA의 HashMap은 Seperate Chaining 기법을 채택하여 사용하고 있습니다.
충돌이 발생했을 때 충돌이 발생한 인덱스의 다음 인덱스부터 빈 버킷을 찾아 데이터를 넣는 방식입니다.
선형 탐사는 충돌 시 하나씩 인덱스를 이동해보며 빈 곳을 찾습니다. 제곱 탐사는 이동폭이 제곱수로 늘어납니다.
두 개의 해시 함수를 이용합니다 하나는 최초의 인덱스 값을 얻을 때 사용하고, 두 번째 해시함수는 충돌 시 얼마 만큼 건너 뛴 버킷에 넣을지 정하는데 사용합니다.
해시 테이블의 크기를 늘리고 다시 모든 데이터를 재 해싱 합니다.
JAVA의 HashMap이 채택하고 있는 방법으로, 버킷에 링크드리스트 또는 트리(Red-Black Tree)를 사용해 충돌을 해결합니다.
앞에서 Seperate Chaining 기법으로 링크드 리스트 또는 트리를 사용해 충돌을 해결한다고 말했는데 정확히 말하자면 한 버킷에 일정 개수 이상의 Key-Value 쌍이 들어가면 Tree로 변환하고, 일정 개수 이하로 줄어들면 LinkedList로 변환 합니다. 그 개수는 다음과 같습니다.
트리로의 변환에는 조건이 하나 더 있습니다. 맵의 전체 버킷의 수가 64개 이상이어야 합니다. 너무 적으면 resize만해서 다시 seperating chaining을 구성합니다.
정렬이 필요 없이 빠른 성능을 원한다면 HashMap
성능을 조금 포기하고 정렬된 순서를 유지하려면 TreeMap
메모리를 더 사용해서 삽입 순서를 유지하고 빠른 성능을 원한다면 LinkedHashMap을 사용하면 됩니다.
모두 Thread-safe하지 않기 때문에 별도의 Thread-safe한 Map을 사용하면됩니다.
HashMap은 충돌 해결 방법으로 Seperate Chaining 기법을 사용하며 충돌이 적을 때에는 Linked List를 사용, 많을 때에는 Tree(Red-Black Tree)를 사용합니다.