해시 충돌의 정의와 해결 방안

해시 테이블이란?

해시 함수를 사용하여 입력 키 값으로부터 해시 값을 얻어 그것을 인덱스로 사용하는 것은 효율적인 검색 방식 중 하나이다.
즉 데이터 저장 공간인 array와 데이터에 대한 위치를 계산하는 hash function 으로 구성된다.
이와  같은 해시 값으로 이루어진 자료구조를 '해시 테이블'이라고 부른다.

해시 충돌이란?

해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.
해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

서로 다른 입력 키 값이 서로 다른 해시 값(인덱스)으로 매핑될 경우 해시 테이블 조회에 걸리는 시간은 상수 시간이 된다.
그러나 여러개의 서로 다른 키 값이 동일한 인데스로 매핑될 경우, 해시 충돌이 발생하여 해시 테이블의 성능을 떨어뜨리게 된다.
이와 같은 해시 충돌을 처리하는 방식 중 가장 많이 쓰이는 것이 '체이닝'과 '개방 번지화'이다.

체이닝

체이닝은 각각의 해시 테이블 인덱스에 해당하는 자료구조를 연결 리스트(linked list)로 만드는 방법이다.

개방 번지화

충돌 발생 시, 주변 또는 어떤 규칙에 의해 해시 테이블 인덱스 중 비어있는 공간(slot)에 할당하는 방법이다.

 

그러나, 체이닝과 개방 번지화는 최악의 경우 조회 복잡도가 원소 개수에 따라 선형 시간(O(n))이 된다.

 

참고 사이트

- 위키 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C