해시 충돌(Hash Collision)이란? [+ 전략 비교]!

해시 충돌(Hash Collision)

해시 자료구조에서는 hashCode로 먼저 비교를 하고, 결과가 같다면 equals로 추가로 비교한다.

관련하여는 자바에서 equals와 hashCode의 관계를 다루는 이전 포스팅 (https://jaehoney.tistory.com/168)을 참고하자.

 

요약하자면, 해시 알고리즘에서 낮은 확률로 다른 Instance이지만 같은 HashCode를 가질 수 있다.

 

우리가 아는 해시 테이블의 구조는 아래와 같이 생겼다.

그렇다면, 만약 여기서 새로운 Instance가 추가 되었는데, 해시(Hash)를 적용하니 HashCode가 01이 나왔다!

 

그러면 기존의 01번 버킷에 데이터를 덮어쓰면 될까? 당연히 안된다.

 

해당 포스팅에서는 이런 경우에 새로운 데이터는 어디에 저장되고 어떻게 처리되는 지 다룬다.

 

해시 충돌 전략

해시 충돌 전략은 크게 아래 두 가지로 나뉜다.

1. 체이닝(Chaining)

체이닝은 버킷에 연결리스트(Linked List)를 할당해서, 해시 충돌이 발생할 경우 연결리스트에 데이터를 추가하는 방법이다.

탐색할 때는 HashCode 기반의 비교를 한 후, Equals()가 false라면 찾거나 리스트가 끝날 때까지 다음 노드를 탐색하게 된다.

Java에서는 기본적으로 체이닝 방법을 사용한다. (Reference: https://www.baeldung.com/java-hashmap-advanced)

 

2. 개방 주소법(Open Addressing)

개방주소법은 해시 충돌이 발생했을 시 정해진 규칙에 따라 비어있는 다른 버킷을 결정해서 해당 버킷에 데이터를 보관하는 방법이다. 개방 주소법은 대표적으로 3가지가 있다.

• 선형 탐색(Linear Probing) - 해시충돌 시 다음 버킷 또는 비어 있지 않다면 몇 개 건너뛰어 데이터를 삽입한다.
• 제곱 탐색(Quadratic Probing - 해시충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입한다.
• 이중 해시(Double Hashing) - 해시충돌 시 해시를 한번 더 적용해서 나온 버킷에 데이터를 삽입한다.

 

특징

체이닝

• 연결 리스트만 사용하면 된다. 계산식을 사용할 필요가 없다.
• 연결리스트가 쌓이면 탐색에 O(n)이 소요된다.
• 특별한 경우 연결리스트가 아닌 자가균형 이진 트리로 구현이 가능하다.
• 데이터가 채워짐에 따라 성능이 적게 감소한다.

개방 주소법

• 2차 충돌이 생길 수 있다. (다른 버킷에 데이터를 저장하기 때문)
• 다른 자료구조(Linked List)나 포인터가 필요 없다.
• 메모리 효율이 높다.
• 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 돌아올 수도 있다.
• 삽입, 삭제 오버헤드가 적다. (메모리 할당 X)
• 데이터가 적을 때 유리하다.

 

아래 그림은 개방 주소법의 선형 탐색과 Chaning 기법을 비교한 것이다.

버킷의 80% 이상이 가득 차게 되면 선형 탐색의 경우 캐시 미스가 급격하게 높아진다. 즉, 성능이 크게 저하된다. 이는 2차 충돌, 3차 충돌 등이 발생하기 때문이다.

 

OcccWiki에 따르면 해시 알고리즘이 일반적으로 충분히 빠르고, 메모리 사용량도 과도하다고 간주되지 않는다. 그래서 이러한 해시충돌 전략은 사실 성능 차이는 미미하다고 한다.

 

 

 

---

 

Reference

• https://preamtree.tistory.com/20
• https://en.wikipedia.org/wiki/Hash_table
• http://occcwiki.org/index.php/Hash_Tables