해싱 (Hashing) (1)

Hashing

Hash Table

- 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법들 중 하나이다.

적절한 가정을 한 후에는 평균적인 탐색, 삽입, 삭제 시간에 O(1)만이 소요된다.

최악의 경우 시간 복잡도는 대부분의 경우 Θ(n)이 된다.

- 해쉬 함수 (hash function) h를 이용해 키 k를 T[h(k)]에 저장하게 된다.

h : U -> {0, 1, ..., m - 1} // 이 때 m은 테이블의 크기, U는 가능한 모든 키들의 집합이다.

이 과정은 보통 키 k가 h(k)로 해싱되었다라고 말하게 된다.

해쉬 함수의 예

- 모든 키들을 자연수라고 가정한다. (어떤 데이터들일지라도 자연수로 해석이 가능하다.)

- Ex : 문자열

ASCII 코드 : C = 67, L = 76 등

- 해쉬 함수의 예

h(k) = k % m (key를 하나의 자연수로 해석한 후 테이블의 크기 m으로 나눈 나머지)

문자열 CLRS라 할 경우

(67 * $128^3$) + (76 * $128^2$) + (82 * $128^1$) + (83 * $128^0$) = 141,764,947 (자연수)

항상 값은 0 ~ m - 1 사이의 정수가 된다.

x = 1024, m = 100이면 24번 인덱스에 1024를 저장하게 된다.

충돌 (Collision)

- 두 개 이상의 키가 동일한 위치로 해싱되는 경우를 말한다.

- 서로 다른 두 키 $k_1$과 $k_2$에 대해서 h($k_1$) = h($k_2$)인 상황이다.

- 일반적으로는 | U | >> m이기 때문에 항상 충돌은 발생 가능하다. (즉, 단사 함수가 아니다.)

- 만약 | K | >> m이여도 역시 충돌 발생 가능성이 존재한다. (K = 실제로 저장된 키들의 집합)

- 충돌이 발생했을 때는 대처 방법이 필요해진다.

- 충돌 해결 방법의 대표적인 두 가지 : Chaining / Open Addressing

Chaining을 이용한 충돌 해결

- 동일한 장소로 해싱된 모든 키들을 하나의 연결 리스트 (Linked List)로 저장한다.

- 키의 삽입 (Inertion)

키 k를 리스트 T[h(k)]의 맨 앞에 삽입 => 시간 복잡도 O(1)

중복된 키가 들어올 수 있고 중복 저장이 허용되지 않는다면 삽입시 리스트를 검색해야 한다. 그에 따라 시간 복잡도는 리스트의 길이에 비례하게 된다.

- 키의 검색 (Search)

리스트 T[h(k)]에서 순차 검색을 시행한다.

시간 복잡도는 키가 저장된 리스트의 길이에 비례하게 된다.

- 키의 삭제 (Deletion)

리스트 T[h(k)]로부터 키를 검색한 후 삭제한다.

키를 검색해 찾은 후에는 O(1)시간만을 소요해 삭제가 가능하다.

- 최악의 경우는 모든 키가 하나의 슬롯으로 해싱되는 경우에 발생하게 된다.

이 경우 길이가 n인 하나의 연결리스트가 만들어진다.

최악의 경우 탐색시간은 Θ(n) + 해쉬함수의 계산시간이 된다.

- 평균의 시간 복잡도는 키들이 여러 슬롯들에 얼마나 잘 분배되냐에 따라 결정된다.

 

SUHA (Simple Uniform Hashing Assumption)

- 각각의 키가 모든 슬롯들에 균등한 확률을 통해 (equally likely) 독립적으로 (independently) 해싱된다 가정한다.

성능을 분석하기 위해 주로 하는 가정법이다.

hash함수는 deterministic하기 때문에(무작위가 아니기 때문에) 현실에는 적용이 불가능하다.

- Load factor α = n / m

n : 테이블에 저장될 키의 개수

m : 해쉬 테이블의 크기, 즉 연결리스트의 개수

α : 각 슬롯에 저장된 키의 평균 개수

- 연결리스트 T[j]의 길이를 $n_j$라고 하면 E[$n_j$] = α

- 만일 n = O(m)이라면 평균 검색 시간은 O(1)이 된다.