HashMapTreeMapLinkedHashMapHashMap의 충돌 해결 방법Open AddressingLinear Probing(선형 탐사)Quadratic Probing(제곱 탐사)Double Hashing(이중 해싱)Rehashing(재해싱)Seperate Chaining요약
HashMap
- HashMap은 key의 해쉬값을 토대로 배열에 값을 저장합니다.
- table의 사이즈 - 1과 key의 해쉬값을 & 연산한 인덱스에 value를 저장합니다.(테이블의 크기는 필요시 동적으로 변합니다 초기값 = 16)
- 해쉬 버킷의 개수가 적다면 충돌이 잦아져 성능상 문제가 발생할 수 있습니다. 데이터의 개수가 특정 임계값에 도달하면 버킷개수를 두 배씩 증가 시키는데 이때마다 Seperating Chaining을 재구성해야하는 문제점이 있습니다.
- 이러한 문제를 해결하는 방법으로는 데이터가 들어올 양을 미리 예측을하고 HashMap 생성 시 버킷 크기를 미리 지정할 수 있습니다.
- 해쉬값을 통해 값을 저장하므로 순서는 유지되지 않습니다.
- table의 0번째 인덱스는 null key를 위한 공간입니다. 그러므로 하나의 null key와 둘 이상의 null value를 허용합니다.
- 여기서 보조 해시 함수가 사용되는 것을 볼 수 있는데 바로 해쉬 값에 상위 16비트 값을 XOR 연산 하는 것 입니다.
- 이러한 단순한 보조 해쉬 함수를 사용할 수 있었던 배경에는 Seperating Chaining에서 충돌이 많아지면 Tree를 사용함에 따라 성능 문제가 완화 되었고 일차 해시 함수 자체가 균등 분포가 잘 이루어 지도록 설계 되었기 때문입니다. 그렇기 때문에 자바 7이전에서 사용 했던 복잡한 보조 해쉬 함수의 효과를 보지 못해 필요 없게 되었기 때문입니다.
- HashMap은 key의 해쉬값을 이용해 삽입, 검색을 하기 때문에 삽입, 검색의 시간복잡도가 O(1)입니다.
TreeMap
- TreeMap은 내부적으로 Red-Black Tree 구조를 이룹니다.
- key - value 쌍을 key 값을 기준으로 정렬된 상태를 유지합니다. (Comparator 인터페이스를 통해 정렬 순서를 커스텀 할 수 있습니다.)
- key값으로 null을 허용하지 않습니다.
- 기본적으로 사용하는 comparator가 null을 사용하지 않기 때문에 null을 허용하는 comparator를 사용하면 null을 허용할 수도 있습니다.
- Red-Black Tree 구조로 데이터를 관리하기 때문에 검색에는 O(log N), 삽입/삭제에도 O(log N)의 시간복잡도를 가집니다.
LinkedHashMap
- 이중 연결 리스트를 이용해 입력된 순서를 유지하는 구조를 가진 HashMap입니다.
- 이중 연결 리스트 구조를 유지해야 하기 때문에 메모리 사용량이 HashMap보다 높습니다.
- 기본적으로 HashMap을 상속받고 LinkedList 구조를 추가한 구현체입니다.
- 그러므로 삽입/삭제/검색 모두 O(1)의 시간복잡도를 가집니다.
3가지 Map 모두 Thread-Safe하지 않습니다.
동기화를 위해서는 CocurrentHashMap, ConcurrentSkipListMap 등을 사용합니다.
HashMap의 충돌 해결 방법
HashMap의 해시 버킷 인덱스 값으로 해시 값에 나머지 연산을 한 값을 사용하는데 이 값은 서로 다른 키라도 중복될 수 있습니다. 이 상황을 충돌 또는 해쉬 충돌이라고하고 이 상황을 해결하는 방법으로 Open Addressing과 Seperate Chaining이 있습니다.
JAVA의 HashMap은 Seperate Chaining 기법을 채택하여 사용하고 있습니다.
Open Addressing
Linear Probing(선형 탐사)
충돌이 발생했을 때 충돌이 발생한 인덱스의 다음 인덱스부터 빈 버킷을 찾아 데이터를 넣는 방식입니다.
Quadratic Probing(제곱 탐사)
선형 탐사는 충돌 시 하나씩 인덱스를 이동해보며 빈 곳을 찾습니다. 제곱 탐사는 이동폭이 제곱수로 늘어납니다.
Double Hashing(이중 해싱)
두 개의 해시 함수를 이용합니다 하나는 최초의 인덱스 값을 얻을 때 사용하고, 두 번째 해시함수는 충돌 시 얼마 만큼 건너 뛴 버킷에 넣을지 정하는데 사용합니다.
Rehashing(재해싱)
해시 테이블의 크기를 늘리고 다시 모든 데이터를 재 해싱 합니다.
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)를 사용합니다.