해시 충돌이란?

해시 충돌이란?

●해시 충돌이란?

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

●해시 충돌 완화하는 방법

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

●개방 주소법에서 다른 해시 버킷을 찾기 위한 방법

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

• 선형 탐사법(Linear Probing) 은 임의의 고정된 크기만큼 한 칸씩 옮기면서 빈 버킷을 찾는 방법이며, 특정 버킷 주변이 모두 채워져 있는 경우 해시 성능이 저하될 수 있으며 (1차 군집 현상) 따라서, 해당 접근 방법은 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 유용

• 제곱 탐사법(Quadratic Probing) 은 선형 탐사법처럼 한 칸씩 찾는 것이 아닌 제곱으로 늘리면서 빈 버킷을 찾으며 보폭이 점점 늘어나기 때문에 선형 탐사법처럼 특정 영역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있지만, 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사할 수밖에 없어 비효율적인 상황이 발생할 수 있음 (2차 군집 현상)

• 이중 해싱(Double Hashing) 은 해시 충돌이 발생하는 경우, 보조 해시 함수를 사용하는 방법이며, 해당 방법은 해시 충돌 가능성이 가장 작지만, 추가적인 보조 해시 함수에서 연산이 발생하기 때문에 다른 방식에 비해 많은 연산량이 요구