[MIT 6.006 정리] Lec 10. 해싱 (개방 주소법, 균일 해싱)

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

 

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

 

* 개방 주소법 (Open Addressing)

• 해싱 구현 과정에서 충돌(collision) 을 해결하는 방법 중 하나로, 해시 테이블을 구현하는 가장 쉬운 방법
  • 포인터를 사용하지 않기 때문에 구현하기 쉽고 적은 메모리를 차지함
  • BUT... 효율적으로 구현하기 위해선 체이닝(chaining) 을 이용할 때보다 더욱 정교하게 짜야함!
• 여러 항목을 갖고 있는 배열(array) 로서 해시 테이블을 구현하되, 배열의 각 슬롯 당 하나의 아이템만 존재할 수 있음
  • 체이닝과 같이 연결 리스트(linked list) 를 이용해서 슬롯 당 저장 크기를 늘릴 수 없으니, 항목 수(n) 가 배열의 크기(m) 보다 커질 수 없음
  • 해시 테이블의 슬롯 크기 m ≥ 항목 수 n
  • 이를 위해, '조사(probing)' 과정을 필요로 함

 

+ 조사(probing)

• 해시 테이블에 데이터(키 key) 삽입을 할 수 있는지 살피고, 안되면 약간 다른 (새로운) 해시값을 구하는 것
  
  • 해시 함수 h: U (universe of keys) × {0, 1, ..., (m-1)} (시도 횟수 trial count)  →  {0, 1, ... (m-1)} (해시값)
• for arbitrary key k,  벡터 [ h(k, 1), h(k, 2), ..., h(k, (m-1)) ]  가 0 ~ (m-1) 까지의 순열(permutation) 이 되길 원함
  
  • 해시 테이블에 데이터(항목 item)을 고르게 분배(load balancing) 하기 위해서는, 모든 슬롯에 대해 채워질 기회가 동등하게 주어져야 함
  • 항목 수 n 이 m 과 가까워졌을 때 (ex. only one slot left...), 어떠한 키가 주어져도 그 나머지(마지막) 슬롯을 채울 수 있어야 함
  • 결국, 해시 테이블 전체를 낭비 없이 다 쓰기 위한 조건인 것...!
• 이때 사용되는 해시 함수는 주어진 키에 대해 조사할 슬롯의 순서(order) 를 정함 (for 삽입/삭제/탐색)
  
  • 키를 삽입하는 순서가, 어떤 슬롯에 어떤 키가 들어갈 지를 결정하게 됨
• 이러한 '조사(probing)' 개념을 바탕으로, 키가 주어졌을 때, 탐색을 위해 여러 다른 해시값들이 계산될 것
  • INSERT(k, v): 빈 슬롯을 찾을 때까지 계속 조사하고, (빈 슬롯을) 찾으면 해당 슬롯에 항목 (key-value pair) 을 넣음  --  m ≥ n 이므로 알맞은 슬롯을 반드시 찾게 되어 있음!
  • SEARCH(k): 찾고자 하는 키 k 의 해시 값을 가지고 각 슬롯에 대해 조사하여, 슬롯에 들어있는 키와 k 값이 다르다면 다른 슬롯에 대해 시도하고, 같다면 해당 키를 반환함  --  k 를 찾거나 빈 슬롯을 만날 때까지 반복! (빈 슬롯 == SEARCH 결과 못 찾은 것...!)
  • DELETE(k): 삭제하고자 하는 키에 대해 빈 슬롯을 나타내는 'None' flag 와는 구별되는 다른 flag 로 대체함! 
    --  삽입 시에는 빈 슬롯과 동일하게 취급하여 해당 공간을 활용하되, 실제로 'None' flag 가 아니므로 탐색 중 삭제된 아이템을 만나도 탐색을 멈추지 않고 계속 해나갈 수 있음 
• ==> '시도 횟수' 라는 새로운 변수를 추가적으로 고려한, 해시값이 순열(permutations) 의 속성을 갖는 새로운 해시 함수를 어떻게 정의할 것인가...!

 

+ Probing strategies (= 해시 함수를 개방 주소법을 적용 가능하도록 바꾸는 것)

• 선형 조사법 (Linear probing):  h(k, i) = ( h'(k) + i ) mod m   (where h'(k) is an ordinary hash fx)
  • 순열이 되는 조건은 만족하나, 값이 들어있는 연속된 슬롯들 (군집 cluster) 이 생기고 이들이 점점 커지게 되므로, 항목의 분배 (load balancing) 측면에서 좋지 않음
  • 대부분의 적재율에서 해시 테이블에 선형 조사법을 사용할 경우 평균 O(1) 상수시간으로 탐색 가능하다는 성질을 잃게 됨  ==>  not applicable...!
• 이중 해싱 (Double hashing):  h(k, i) = (h_1(k) + i * h_2(k) ) mod m
  • h_2(k) 와 m 이 서로소일 때, 해당 해시 함수는 순열 조건을 만족함  -->  m 이 2의 제곱수이고 h_2(k) 가 모든 k 에 대해 홀수이면 됨!
  • 개방 주소법을 구현하는 좋은 방법!!

 

* 균일 해싱 가정 (Uniform Hashing Assumption)

• 개방 주소법이 체이닝만큼 잘 동작하는지 증명하기 위해서는 균일 해싱 가정이 필요함...! (증명 TBA)
• 각 키가 갖는 조사 순서(probe sequence) 는 m! 개의 순열 중 하나이며, 특정 순열이 될 확률은 모두 같다는 것
  (Each key is equally likely to have any one of the m! permutations, as its probe sequence)
  • (참고) 단순 균일 해싱(Simple Uniform Hashing): 키가 슬롯에 독립적으로 배정된다는 가정
• 적재율 alpha = n / m 이라 할 때, 삽입/삭제/탐색과 같은 연산의 비용은 1 / (1-alpha) 이하임  -->  적재율 alpha 가 커질수록 (1에 가까울수록), 데이터 삽입을 한다면, 조사 시도 횟수의 기대값이 커짐
  • 이미 많은 슬롯에 데이터가 들어가있으면... 새로운 빈 슬롯을 찾기가 더 어려워지므로!
  • 확률적으로, 적재율이 0.7 처럼 높아지면 개방 주소법이 같은 크기의 체이닝에 비해 덜 효과적이게 됨  -->  적재율이 0.5 이하로 되도록 테이블의 크기가 조절되어야 함