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