빽 투더 기본기 [알고&자구 4편]. 해시 테이블

기본적인 자료구조들 중, 트리에 이어 또 하나 자세히 살펴볼만한 자료구조가 바로 해시 테이블이다.

Ratsgo's blog 님의 정리된 내용을 가지고 간단히 요약해보려고 한다.

 

정의

key, value 형태로 자료를 저장하는 구조를 해시 테이블이라고 한다. 이 때, 테이블에서 인덱스 역할인 key를 만드는 함수를 해시 함수라고 하고, 본래 값에서 해시 함수를 먹여 해시 값(키)를 만드는 과정을 해싱이라고 한다.

 

특징

삽입, 삭제, 탐색에서 해시 충돌이 발생하지 않는다면, 시간복잡도 O(1) 을 보인다.

아래 다른 자료구조들과 비교해보았을 때, 매우 극적인 성능을 보이는 자료구조다.

자료구조	삽입	삭제	탐색
배열	O(n)	O(n)	O(1)
리스트	O(1)	O(1)	O(n)
트리	O(1)	O(1)	O(log n)
해시 테이블	O(1)	O(1)	O(1)

 

이슈

해시 충돌

위에서 해시 충돌이 발생하지 않을 경우에만 시간 복잡도가 O(1) 이라고 했다.

해시충돌이란, 서로 다른 키 값에 대해, 해시함수가 같은 해시 값을 만들어내는 경우를 말한다.
즉, 서로 다른 데이터를 저장하는데, 같은 공간의 인덱스를 할당하여 접근하는데에 충돌을 일으키는 경우이다.

모든 해시 함수는 해시 충돌을 일으키며, 이 해시 충돌을 적게 일으키게 하는 해시함수, 혹은 해시 테이블이 좋다고 할 수 있다.

 

클러스터

해시 함수가 내뱉는 해시 값들이 저장공간 한 쪽에 뭉치게 되는 경우, 저장공간을 온전히 잘 활용해서 쓴다고 볼 수 없다.
예를 들어, 저장 공간이 0-100까지 있는데, 해시 함수가 30-50의 값 위주로 해싱한다면, 0-29, 51-100 의 공간은 쓰이지 않고 낭비되는 것이다.

이렇게, 뭉쳐있는 현상을 클러스터라고 하며, 클러스터 현상이 없을수록 좋은 해시 테이블이라고 할 수 있다.

 

해시 충돌 문제해결

Chaining

해시 테이블에 연결 리스트를 더한 구조다.
즉, 충돌이 일어날 경우, 해당 해시 값에 노드를 하나 추가하여 데이터를 추가한다.

유연하지만, 그만큼 메모리 문제를 야기할 수도 있다.
또한, 일부 해시 값에 클러스터 현상에 생기는 경우, 선형적으로 접근해야 되므로, 성능이 매우 낮아진다.
따라서, 클러스터와 해시함수에 신경을 써서 사용해야 한다.

 

Open addressing

충돌이 일어날 경우, 다른 주소(해시 값)에 저장할 수 있도록 하는 방법이다.
따라서, 충돌이 일어났을 때, 사용 가능한 (충돌이 일어나지 않을) 다른 주소를 어떻게 탐사할 것인지가 또 다른 이슈가 된다.

다른 주소를 어떻게 탐사할지는 다음과 같은 방법이 있다.

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

 

Hash Function

애초에, 충돌을 덜 일으키고, 클러스터 문제를 줄이기 위해, 특정 값에 치우치지 않게 해시 함수를 잘 짜자는 방법이다.

일반적으로 다음과 같은 방법들이 있다고 한다.

• division method
• multiplication method
• Universal hasing