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