해시 충돌

해시 충돌

 

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

해시 자료구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 관리한다.

 

 

해시함수는 다른 키를 사용해도 같은 결과가 나오는 경우가 존재하는데 이를 해시 충돌이라고 한다.

 

 

해시충돌 완화법

1. 개방주소법
   특정 값이 들어가야하는 자리가 사용되고 있을 경우 다른 해시 버킷에 데이터를 삽입하는 방법
2. 분리연결법
   버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌 완화하는 방법

 

개방주소법에서 다른 해시 버킷을 찾기 위한 방법에는 어떤 것이 존재하나?

• 선형탐사법
• 제곱탐사법
• 이중해싱

 

선형탐사법

 

임의의 고정된 크기만큼 한칸씩 옮기면서 빈 버킷을 찾는 방법이다. 특정 버킷 주변이 모두 채워져 있는 경우 해시 성능이 저하될 수 있다. 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 사용한다.

 

제곱탐사법

 

선형 탐사법처럼 한칸씩 이동하며 찾는 것이 아니라, 제곱으로 늘리면서 빈 버킷을 찾는 것이다. 보폭이 점점 늘어나기 때문에 특정 영역에 값이 밀집되어 저장되어도, 해당영역을 빠르게 벗어날 수 있다.

하지만 여러값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서대로 탐사할 수 밖에 없어 비효율 적이다.

 

 

이중 해싱

 

해시 충돌이 발생하는 경우 보조 해시 함수를 사용하는 방법이다.

이 방법은 연산을 한번 더 수행하기 때문에 다른 방식에 비해 더 많은 연산량이 요구가 된다.