[알고리즘] 해시 테이블(Hash table)

[알고리즘] 해시 테이블(Hash table)

 

해시 테이블

---

해시 함수는 Key값을 입력으로 받고, Index값을 반환한 후 해시 테이블의 Index에 대응하는 slot에 Key값과 Value값을 저장하며 다음의 두 가지 성질을 만족하도록 설계해야합니다.

• 입력 원소가 해시 테이블 전체에서 고루 저장되어야 한다.
• 계산이 간단하여야 한다.

위의 그림은 해시테이블에서 발생하는 문제점인 충돌(Collision)을 Chaining 방법으로 해결한 예시입니다.

Hash function으로는 $H(x) = x\,mod\,10$을 이용하였습니다. 

 

충돌이란, 해시 테이블 내의 한 주소에 두 개 이상의 원소가 들어가는 것을 말합니다. 

그림에서는 해시 테이블의 7번 인덱스에 해당하는 slot에 두 개의 Key값 87과 97이 같이 들어가면서 충돌이 발생하였습니다.

Chaining방법은 이 충돌을 그림과 같이 linked list를 이용하여 해결합니다. 

 

충돌을 해결하는 방법으로는 대표적으로 Chaining과 Open Addressing방법이 있습니다. 이 두 가지 방법의 차이는 뒷부분에 작성하도록 하겠습니다.

 

 

 

해싱

---

Key값을 Hash function에 대입하여 나오는 결과로 주소를 계산하여 바로 값에 접근하는 방법을 해싱이라고 합니다.

즉 위의 그림처럼 해시 테이블에 값들이 저장되어 있을 때, 5123를 Hash function에 대입하여 Index값을 얻고 주소를 계산하여 바로 5123에 접근할 수 있는 방법입니다.

 

 

 

 

시간복잡도 - Chaining

---

linked list의 길이를 $l$, Table에 저장되는 모든 Key값의 수를 $k$라고 하겠습니다.

• Insertion 

동작의 수행시간(중복 저장 허용) : $O(1)$

동작의 수행시간(중복 저장 허용x) : $O(l)$ 

 

중복 저장이 허용되지 않는다면 삽입 시 linked list를 검색해야 하기 때문에 $O(l)$

($l$은 상수이기 때문에 $O(l) = O(1)$이지만 구분을 위하여 다르게 서술하였습니다.)

 

• Search

동작의 수행 시간 : $O(l)$

단, 최악의 경우 모든 원소가 한 개의 slot에 저장되며 이때의 linked list 길이 = $k$

즉 최악의 경우 동작의 수행 시간 : $O(k)$

(이또한 $k$가 상수이기 때문에 $O(k) = O(1)$입니다.)

 

• Deletion

동작의 수행 시간 : $O(1)$