해시 충돌
해시(Hash) 자료 구조는 키-값 쌍으로 이루어진 데이터 구조로 키를 이용해 값을 O(1) 시간 복잡도로 찾을 수 있습니다. 해시 자료 구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리하는데요. 해시 함수는 다른 키를 사용해도 같은 결과가 나오는 경우가 존재합니다. 이를 해시 충돌(Hash Collision) 이라고 합니다.
✔️ 해시 충돌은 어떻게 완화할 수 있을까? 🤔
1) 개방 주소법(Open Addressing)
특정 값이 들어가야 하는 자리(버킷)가 이미 사용되고 있는 경우, 다른 해시 버킷에 데이터를 삽입
2) 분리 연결법(Separate Chaining)
버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌을 완화
✔️ 개방 주소법에서 다른 해시 버킷을 찾기 위한 방법에는 어떤 것이 존재할까? 🤔
버킷이 이미 사용되고 있는 경우, 다른 해시 버킷을 찾기 위한 여러 방법이 존재합니다. 선형 탐사법, 제곱 탐사법, 이중 해싱이 이에 해당됩니다.
1) 선형 탐사법(Linear Probing)
임의의 고정된 크기만큼 한 칸씩 옮기면서 빈 버킷을 찾는 방법입니다. 선형 탐사법은 특정 버킷 주변이 모두 채워져 있는 경우 해시 성능이 저하될 수 있습니다. (1차 군집 현상) 따라서, 해당 접근 방법은 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 유용합니다.
2) 제곱 탐사법(Quadratic Probing)
선형 탐사법처럼 한 칸씩 찾는 것이 아닌 제곱으로 늘리면서 빈 버킷을 찾습니다. 보폭이 점점 늘어나기 때문에 선형 탐사법처럼 특정 영역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있습니다. 하지만, 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사할 수밖에 없어 비효율적인 상황이 발생할 수 있습니다. (2차 군집 현상)
3) 이중 해싱(Double Hashing)
해시 충돌이 발생하는 경우, 보조 해시 함수를 사용하는 방법입니다. 해당 방법은 해시 충돌 가능성이 가장 작지만, 추가적인 보조 해시 함수에서 연산이 발생하기 때문에 다른 방식에 비해 많은 연산량이 요구됩니다.