해시 충돌(Hash Collision)

해시 자료구조는 키값 쌍으로 이루어진 데이터 구조로 키를 이용해 값을 O(1) 시간 복잡도로 찾을 수 있다. 해시 자료구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리한다. 해시 함수는 다른 키를 사용해도 같은 결과가 나오는 경우가 존재하는데 이를 해시 충돌(Hash Collision)이라고 한다.

해시 충돌은 어떻게 완화할 수 있나요? 🤓

해시 충돌을 완화하기 위한 접근 방법으로 개방 주소법과 분리 연결법이 대표적이다. 개방 주소법(Open Addressing)은 특정 값이 들어가야 하는 자리(버킷)가 이미 사용되고 있는 경우 다른 해시 버킷에 데이터를 삽입하는 반면, 분리 연결법(Separate Chaining)은 버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌을 완화한다.

개방 주소법에서 다른 해시 버킷을 찾기 위한 방법에는 어떤 것이 존재하나요? 🤔

버킷이 이미 사용되고 있는 경우, 다른 해시 버킷을 찾기 위한 여러 방법이 존재한다. 선형 탐사법, 제곱 탐사법, 이중 해싱이 이에 해당된다.

 

• 선형 탐사법(Linear Probing)은 임의의 고정된 크기만큼 한 칸씩 옮기면서 빈 버킷을 찾는 방법이다. 선형 탐사법은 특정 버킷 주변이 모두 채워져 있는 경우 해시 성능이 저하될 수 있다. 따라서, 해당 접근 방법은 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 유용하다.
  
  
• 제곱 탐사법(Quadratic Probing)은 선형 탐사법처럼 한 칸씩 찾는 것이 아닌 제곱으로 늘리면서 빈 버킷을 찾는다. 보폭이 점점 늘어나기 때문에 선형 탐사법처럼 특정 영역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있다. 하지만, 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사할 수밖에 없어 비효율적인 상황이 발생할 수 있다.
• 이중 해싱(Double Hashing)은 해시 충돌이 발생하는 경우, 보조 해시 함수를 사용하는 방법이다. 해당 방법은 해시 충돌 가능성이 가장 작지만, 추가적인 보조 해시 함수에서 연산이 발생하기 때문에 다른 방식에 비해 많은 연산량이 요구된다.