# 해시 충돌

해시(Hash) 자료 구조는 키값 쌍으로 이루어진 데이터 구조로 키를 이용해 값을 O(1) 시간 복잡도로 찾을 수 있음.

해시 자료 구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리하는데, 해시 함수는 다른 키를 사용해도 같은 결과가 나오는 경우가 존재함. 이를 **해시 충돌(Hash Collision)** 이라고 함.

### 해시 충돌 완화

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

### 개방 주소법에서 다른 해시 버킷을 찾기 위한 방법&#x20;

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

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

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

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