해쉬 충돌

백준 알고리즘 7453번 문제를 해결하는 와중에 해쉬를 이용하여 해당 문제에 접근하였으나 시간초과로 생각한 개념이 적용이 되지 않았다. 문제의 원인을 해결하기 위해서 구글링을 한 결과 해쉬를 사용할 때는 해쉬 충돌을 고려해야한다는 것을 알 수 있었다.

 

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

 

다시말해 입력 값의 집합과 해쉬 함수의 출력 값의 집합의 관계가 1:1이어야만 탐색시 O(1)의 성능을 발휘할 수 있다는 것이다. 1:1관계가 성립하지 않는다면 해당 값의 위치를 해쉬의 저장된 키 값을 모두 탐색해야하므로 탐색시 O(n)의 시간 복잡도를 가지게 된다.

 

해시 충돌을 해결하기 위해서 해결 방법은 두가지가 있다.하나는 열린 어드레싱 방법이다.

 

1. 선형 조사법(Linear Probing)충돌이 발생한 공간을 기준으로 다른 주소 공간을 검색하여 빈 공간에 데이터를 저장하는 기법이다.가장 단순한 해결방법이라고 생각한다. 단순한 해결 방법인 만큼 단점이 있다.- 검색에 시간이 많이 소요된다.- 데이터들이 일정한 키 값으로 모이는 현상이 발생한다.

 

2. 이차 조사법(Quadratic Probing)선형 조사법과 비슷한 방식이지만 빈 공간을 저장하는 범위의 차이가 있다는 것이 차이점이다.

 

3. 이중 해시(Double Hash)충돌이 발생하는 경우 새로운 해쉬함수를 적용하여 저장하는 공간을 특정 짓는 방법이다.

 

4. 재해싱(Rehasing)해시 테이블의 크기를 늘리고 늘린 해시 테이블에 값을 해싱하는 방법이다. 공간을 확장하여 해시 함수의 1:1관계를 보다 강하게 보장하는 방법이다. 하지만 필요한 공간이 많아지며 재배치로 인한 비용이 발생한다.

 

다른 하난는 닫힌 어드레싱 방법이다.

 

1. 체이닝해시 테이블 자체는 포인터 배열로 만들고, 같은 주소공간에 해당하는 데이터들을 체인 형식(연결리스트)으로 만들어 연결하는 방식이다.

체이닝

 

출처

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

https://parksh86.tistory.com/111