[Introduction to Algorithms] 해시 테이블 - 체이닝에 의한 충돌 해결

 

1) 체이닝이란?

 

 

- 체이닝에서는 위 그림과 같이 같은 위치에 해시되는 모든 원소를 같은 연결 리스트에 넣는다.

  위치 j는 위치 j에 해시된 모든 원소로 이루어진 리스트의 처음을 가리키는 포인터를 가지고 있다.

  이런 원소가 존재하지 않는다면 위치 j는 NIL 값을 가진다. 

 

- 체이닝에 의해 충돌이 해결될 때 해시 테이블 T의 사전적 작업을 구현하기가 매우 쉽다.

  

CHAINED-HASH-INSERT(T, x)
리스트 T[h(x.key)]의 맨 앞에 x 삽입

CHAINED-HASH-SEARCH(T, k)
리스트 T[h(k)]에서 키 k를 가지는 원소를 검색

CHAINED-HASH-DELETE(T, x)
리스트 T[h(x.key)]에서 x를 삭제

 

- 삽입 프로시저는 최악의 경우 수행시간이 O(1)이다. 

  삽입될 원소 x가 테이블에 미리 존재하지 않는다고 가정하기 때문에 삽입 프로시저는 매우 빠르다.

  필요하다면 삽입 전에 키가 x.key인 원소를 찾음으로써 이 가정을 (추가의 비용을 들여)확인할 수 있다. 

 

- 검색 프로시저는 최악의 경우 수행시간이 리스트 길이에 비례한다. 

  이 프로시저에 대한 좀 더 상세한 분석은 아래에서 제공한다. 

  위 그림과 같이 리스트가 양방향 연결이 되어 있다면 원소를 O(1)에 삭제할 수 있다. 

 

2) 체이닝을 사용하는 해싱의 분석

 

- 체이닝을 사용하는 해싱은 얼마나 잘 동작하는가?

  그리고 주어진 키를 가지는 원소를 검색하는데 실제로 얼마나 걸리는가?

  

- m개의 저장 공간을 가지고 있고 n개가 저장된 해시 테이블 T에서 T의 적재율(load factor) a를 

  n/m으로 정의하자. 즉, 적재율은 각 리스트에 저장된 원소의 평균 개수다.

  a는 1보다 작을 수도, 같을 수도, 클 수도 있는데 분석은 이 a에 대해 이루어질 것이다.

 

- 체이닝을 이용하는 해싱의 최악의 경우 수행시간은 굉장히 크다.

  n개의 키가 모두 같은 위치에 해시되는 경우 길이가 n인 리스트가 만들어지게 된다.

 그러므로 최악의 경우 검색 수행시간은 해시값을 계산하는 시간에 O(n)이 추가된다.

 

- 이는 모든 원소에 대해 하나의 연결 리스트를 사용하는 경우보다 좋지 않다.

  물론 이런 최악의 경우 수행시간을 각오하고 해시 테이블을 사용하지는 않는다. 

  해싱의 평균 성능은 해시 함수 h가 저장될 키들의 집합을 m개의 위치에 평균적으로

  얼마나 잘 분산시키느냐에 달려 있다.

  하지만 지금은 임의의 원소가 기존에 해시된 다른 원소의 위치에 상관없이 

  m개의 위치에 골고루 해시된다고 가정한다. 

  이 가정을 단순 균등 해싱이라고 한다.