[MIT 6.006 정리] Lec 08. 해싱 (딕셔너리, 프리해싱, 해싱, 체이닝)

* 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D

 

------- * ------- * ------- * -------

 

* 딕셔너리 (Dictionary)

• 키(key) 를 갖는 아이템의 집합(set of items) 을 보관 (maintain, store) 하는 추상 자료형 (Abstract Data Type, ADT) 의 하나
• 삽입(insert[item]) / 제거(delete[item]) / 탐색(search[key]) 연산이 가능
  • 탐색(search[key]) : 주어진 키에 해당하는 아이템을 찾거나, 해당하는 키가 없는 경우 키 에러(key error) 를 띄움
  • cf. 이진 탐색 트리 (BST) 의 경우, 해당하는 키가 없는 경우 그보다 크거나 작은 아이템(선행자/후속자) 를 찾을 수 있다는 점에서 차이!  -->  키가 존재하는지만 알 수 있다는 점에서 (exact search) 라고도 함
  • 따라서 각 아이템은 유일한(unique) 키를 갖는다고 가정함  -->  이미 키가 존재하는 아이템을 추가할 경우 덮어쓰기 됨!
• AVL 트리 구조로 구현 시 각 연산을 O(log n) 시간에 수행 가능  -->  at best, 상수 시간 O(1) 안에 수행 가능!

 

* 딕셔너리의 구현 -- via 직접 접근 테이블 (Direct-Access Table)

• 배열(Array) 를 통해 구현: 배열의 인덱스를 키(key) 로 활용하며, 아이템을 키의 인덱스에 따라 저장함
• 한계 1) 키가 non-negative 정수가 아닐 수도 있음  <--  배열의 인덱스는 0 이상의 정수만 가능하므로!
• 한계 2) 메모리 낭비가 큼  <--  배열에서 키마다 슬롯이 필요하므로 키가 아주 많을 경우에 필요한 메모리 공간이 

 

+ 해결책 1) 프리 해싱(pre-hash)

• 프리해싱 함수 hash(x): 어떤 키든 간에 음이 아닌 정수로 대응시켜 주는 함수
  • Theoretically, 키는 유한하고(finite) 불연속적임(discrete)  <-- 정수 == 비트열(string of bits)!
  • Ideally, if hash(x) = hash(y)  <=>  x = y

+ 해결책 2) 해싱(hashing)

• 해싱 함수 h(x): 모든 키를 담은 공간 key space 을 그보다 작은 크기 m 인 슬롯 집합으로 줄이는 함수
  • 전체 집합을 0, 1, ..., m-1 에 대응시키는 것과 같음 (== 배열 T (aka 해시 테이블) 로 매핑!)
• 핵심 아이디어는 모든 가능한 키를 작은(reasonable size m) 정수 집합으로 줄이며, m = O(n) 이 되게 하는 것
  • '해시 테이블의 크기 m' 과 '현재 딕셔너리에 있는 키의 개수 n' 이 최대한 비슷한 값을 갖도록 함
  • 테이블의 크기가 딕셔너리에 있는 키의 개수에 비례하게 됨 (m 개를 저장하고 싶을 때 최대 2m 또는 3m 만큼의 공간을 쓰는 것!)
• 충돌(collision): 두 개 이상의 다른 키가 해시 테이블의 동일한 슬롯에 대응되는 것
  • h(k_i) = h(k_j)  인데  k_i != k_j  인 경우...!
• 체이닝(chaining): 여러 아이템이 해시 테이블의 같은 위치에 있을 때, 이들을 (연결) 리스트로 저장하는 것
  • 최악의 경우 (삽입하는 모든 키가 테이블의 동일한 슬롯에 대응), n 개의 항목으로 이루어진 연결 리스트가 됨 ==> O(n)
  • 하지만 특별히 운이 나쁘지 않은 이상, 해시 함수 h 가 항목을 잘 나눠주어 대부분 리스트는 상수 길이를 가질 것 --> 가정을 통해 증명 가능
  • [증명 w/가정 of 단순 균일 해싱 simple uniform hashing]
    • 단순 균일 해싱: 각 키는 각 테이블의 슬롯에 동일한 확률로 (균일성), 해시되는 다른 키들과 독립적으로 (독립성) 해시된다
    • 적재율 alpha = n / m  --  n 개의 키와 m 개의 슬롯이 있을 때 체인 길이의 기댓값
    • m = O(n) 조건이 만족하는 한,  적재율 alpha (n/m) 는 O(1) 이 됨!
    • 따라서, 각 연산의 실행 시간은 O(1 + chain) = O(1 + alpha)  <-- 1 은 해시함수로 계산할 때 드는 기본 비용!

 

* Then, How do we construct h(x)?  (그래서 그 좋은 해시함수... 어떻게 구현한다는거니...?)

• 실제로 어떻게 큰 전체집합에 있는 키를 테이블의 작은 슬롯 집합에 대응시킬 것인가?
• 공통 가정: 테이블 크기는 2의 제곱
• 1) 나누기 방법 division method: 키가 있을 때, 이를 m 으로 나눈 나머지를 구하는 것
  • h(k) = k mod m
• 2) 곱하기 방법 multiplication method: 나누기 방법은 m, k 이 공약수를 가질 때 좋지 않으니 오히려 곱해보자...!
  • h(k) = [ (a * k) mod 2^w ] >> (w-r)   ( m = 2^r ) 
  • 가정: w 비트 머신에 있음 (a 는 랜덤한 w 비트 정수로, 2^(r-1) 과 2^r 사이에 있는 홀수)
  • 최종적으로 구해진 숫자는 0과 m-1 사이에 있음
• 3) 유니버셜 해싱 universal hashing: 위의 둘과 달리 이론적으로 아름다운 방법(...!)
  • h(k) = [ (ak+b) mod p ] mod m
  • 가정: a, b 는 0 과 (p-1) 사이의 랜덤한 숫자이며, p 는 전체집합 크기보다 큰 소수(prime number)
  • 최악의 경우, 서로 다른 키 k_1, k_2 에 대해 h(k_1) = h(k_2) 일 확률 (두 키가 충돌할 확률) 은 1 / m