Hash Table/Algorithm and Collision Resolution

 

 

00. Hash Table이란?

 

Hash Table이란, Dictionary 구조를 구현하는 효율적인 자료 구조 중 하나이다.

cf. Dictionary: INSERT, SEARCH, 그리고 DELETE 기능이 있는 집합

참고로 Hash Table을 사용하였을 때 SEARCH하는데 걸리는 Time Complexity는 다음과 같다.

• worst case: Θ(n^2)
• expected time: O(1)

Hash Table에는 여러 가지 종류가 존재한다. 이에 대해서 알아보도록 하자.

 

01. Direct Address Table

 

가장 단순한 형태의 Hash Table이다. Key값이 그대로 테이블의 인덱스 값이 되며, 따로 처리할 내용이 없기 때문에 Time Complexity도 항상 O(1)이다. 각 operation에 대한 pseuedocode는 다음과 같다.

 

 

 

다만 구조가 간단한 만큼, key값 중 중복되는 값이 있다면 바로 collision이 발생한다. (Collision이 발생하기 매우 쉬움)

또한, Hash Table의 공간 사용에 있어 매우 비효율적이다.

 

 

02. Collision Resolution Methods

 

위에서도 짧게 언급했지만, 결국 해시 함수에서의 가장 큰 문제 중의 하나는 collision이다. Hash Algorithm의 정의역과 치역을 고려한다면, 보통 치역이 정의역보다 작기 때문에 collision은 발생할 수 밖에 없는 구조이다.

Collision Resolution Methods는 Collision이 발생하였을 때 어떻게 다시 재배치를 해줄 것인지에 대한 것이다.

Collision Resolution Methods에는 크게 3가지가 존재한다. 

 

02-1. Chaining

출처: Wikipedia

 

Chaining은 같은 index의 값이 발생하는 경우, Linked List의 형태로 element를 추가하는 형식이다.

위와 같이 collision이 발생한 John Smith와 Sandra Dee에 대해서, element를 추가하여 managing을 해주었다.

여전히 key값을 이용하여 찾기 때문에 O(1)이지만, 경우에 따라 최악의 경우 key의 갯수만큼 추가로 탐색해야 할 수도 있다. 그러나 O(lgn)보다는 값이 작을 것이기 때문에, Time Complexity는 O(1+α)로 표시한다. 

Search 외의 기능들은 다음과 같이 구현될 수 있다.

 

• expected search time : O(1)

 

cf) 적재율에 관하여

load factor = (number of keys) / (number of slots)

 

 

02-2. Open Addressing

 

Chaining 기법의 경우, 기존에 생성한 Table과 별개로 추가 공간을 사용해야 한다는 단점이 존재한다. 따라서 아직 사용되지 않은 slot을 골라 위치해주게 된다. "아직 사용되지 않은 slot을 골라주는 과정"을 probing이라고 하며, 종류에 따라 다음과 같이 세 가지로 나뉜다.

1) Linear Probing

2) Quadratic Probing

3) Double Probing

 

세 가지 방법의 공통점은, 삭제할 때 조심해야 한다는 것이다. 아무런 조치 없이 하나를 삭제해버리면, searching을 진행할 때 앞선 slot이 NIL로 탐지되어 Hash Table에 존재하지 않는다고 탐지될 수도 있기 때문이다.

 

1) Linear Probing - m possible probe seq.

 

간단하게, 해당 slot이 차있는 경우 다음 slot을 사용하는 것이다.

Linear Probing의 경우 다음 slot을 차지하기 때문에 데이터가 특정 slot 주변에 몰리는 clustering 현상이 발생한다.

O(n)

 

 

 

2) Quadratic Probing - m possible probe seq.

 

Linear Probing에서는 단순하게 다음 slot을 가져갔다면, Quadratic Probing에서는 제곱수만큼 값을 옮겨서 slot 차지를 한다.

Quadratic Probing은 Linear Probing보다는 낫지만, 동일하게 clustering 문제를 가지고 있다.

 

 

3) Double Probing - m^2 probe seq.

 

Double Probing은 위 두 probing method가 가지고 있는 문제를 해결하기 위해 고안되었다.

위 식을 기준으로 이야기하자면, h₁은 일반 해시값을 찾기 위한 함수이고, h₂은 충돌이 발생하였을 때 새로 할당해주기 위한 함수이다. 

또한 h2의 값은 relatively prime이어야 한다.

 

마지막으로 앞서 적재율에 관련해서 간단하게 설명한 적이 있다.

적재율에 따라서 probing을 해야하는 기댓값을 계산할 수 있다. α를 적재율이라고 할 때, search를 실패하는 경우의 probing 기댓값은 다음과 같다.

반면 성공했을 때의 search 횟수는 다음과 같다.

 

 

03. Hash Functions

 

Collision Resolution Methods에서는 이미 발생한 collision에 대해서 어떻게 관리할 것인가에 대한 문제였다면, Hash Function 자체에서 collision을 발생시키지 않도록 하는 방법도 존재한다.

 

03-1. Division Method

단, N은 2의 제곱꼴이 되면 안됨 (하위 ~비트가 짤리기 때문)

 

03-2. Multiplication Method

fractional part만 가져가는 식

결국 N을 곱하고, mod 1을 한 값이 0과 1 사이이므로 0~N사이의 값이 나온다는게 장점