HashMap & Hash Collision

HashMap

HashMap은 key-value를 쌍으로 저장하는 비선형 자료구조입니다.
일정한 크기의 배열을 생성한 후에 Key 값을 Hash 함수를 통해 index로 변환하여 해당 index에 Key와 Value를 저장합니다.
시간복잡도
- i 번째 데이터에 접근 : O(N)
- x 라는 데이터(Key)가 있는지 탐색 : O(1)
- x 라는 데이터(Key)에 접근 : O(1)
- x 라는 데이터의 삽입 / 삭제 : O(1)

HashMap은 무한에 가까운 Key 값을 유한한 메모리에 저장해야 하기 때문에 아무리 뛰어난 성능의 Hash 로직을 사용하더라도, Hash Collision(해시 충돌)이 발생합니다.

Hash Collision (해시 충돌)

해시 충돌이란 서로 다른 Key 값에 대해서 Hash 함수의 반환 값이 동일한 경우를 말합니다. 또한 버킷이 비어있더라도 해시 충돌은 발생할 수 있습니다.

예를 들어, Java에서 String.hashCode() 함수를 살펴보겠습니다.

Java에서 “FB” 와 “Ea”의 .hashCode() 는 같습니다.

이런 경우가 hashCollision이 발생한다.

FB 와 Ea의 각 문자의 ASCII 코드의 값들이 서로 1씩 차이나고, 해시 코드 계산 중 31을 곱하는 과정 때문에 발생합니다.

Java의 String 의 hashCode() 내부 구현을 살펴보면 다음과 같습니다.

int h = 0;
for (int i = 0; i < length; i++) {
    h = 31 * h + val[i];
}

Hash Collision 해결책

해시 충돌이 발생할 경우 크게 두 가지 방법을 사용하여 문제를 해결합니다.

Open Addressing

스크린샷 2023-10-15 오후 3 56 39

Open Addressing 방법은 비어있는 버킷에 데이터를 저장하는 방식입니다.

해시 충돌이 발생할 경우, 해당 데이터의 접근 / 탐색에 대한 시간 복잡도가 O(n)으로 증가할 수 있습니다.

Chaining

스크린샷 2023-10-15 오후 3 57 10

해시 충돌이 발생한 버킷에 Linked List를 만들고, 해당 Linked List에 데이터를 저장합니다.

Linked List로 데이터를 저장할 경우 데이터의 접근, 탐색까지 O(n)의 시간이 걸릴 수 있습니다.

이러한 문제를 해결하기 위해 BST를 활용합니다.

스크린샷 2023-10-15 오후 3 59 58

Java 에서는 Chaining 전략을 사용하며 해시 충돌이 발생한 버킷에 대해 7개 Bin 까지는 Linked List로, 8개 이상이 되면 BST (Red-Black Tree)로 변경합니다.
반대로 8개에서 Remove에 의해 Bin의 개수가 줄어들면, 6개에서 Linked List로 변경합니다.

Birdie