[Hash Table] 해시 테이블, Hash Table

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 용어

• Hashing : 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 해싱이라 함
• Hash function : 해싱에 사용되는 함수
• Hash value : 해시 함수가 계산한 값, 해시 주소라고도 함
• Hash table : 항목이 해시값에 따라 저장되는 1차원 리스트
• Collision : 아무리 우수한 해시함수를 사용하더라도 두 개 이상의 항목을 해시 테이블의 동일한 원소에 저장해야 하는 경우 발생, 서로 다른 키들이 동일한 해시값을 가지는 것을 충돌이라 함

 

- 해시 함수 (Hash Function)

• 가장 이상적인 해시 함수는 키들을 균등하게(Uniformly) 해시 테이블의 인덱스로 변환하는 함수
• 의미가 부여되어 있는 키를 간단한 계산을 통해 뒤죽박죽으로 만든 후 해시 테이블의 크기에 맞도록 해시값을 계산
• 아무리 균등한 결과를 보장하는 해시 함수일지라도 함수 계산 자체에 긴 시간이 소요되면 해싱의 장점인 연산의 신속성 상실
• 해시 함수의 대표적인 예
  • Division function
  • Mid-square function
  • Folding function
  • Multiplicative function

 

- 충돌 처리

• Closed addressing : 충돌이 발생한 키들을 같은 위치에 모아서 저장
  • Chaining : 충돌이 발생한 키들을 한 곳에서 단순 연결 리스트에 저장
    • 레퍼런스가 차지하는 공간이 추가로 필요
    • 해시 테이블의 empty 원소를 찾는 오버헤드가 없음
    • 군집화 현상이 없음
    • 구현이 간결
    • 연결 리스트의 평균 길이가 약 10 정도일 때 좋은 성능
• Open addressing : 해시 테이블 전체를 열린 공간으로 가정하고 충돌된 키를 일정한 방식에 따라서 찾아낸 empty 원소에 저장
  • 선형 조사 (Linear probing) : 충돌이 나면 바로 다음 원소를 검사하여 empty 원소를 찾는 방법
    • 순차 탐색으로 empty 원소를 찾아 충돌된 키를 저장하므로 해시 테이블의 키들이 빈틈 없이 뭉쳐지는 현상 발생 : 1차 군집화 (Primary clustering)
    • 군집화는 탐색, 삽입, 삭제 연산을 수행할 때 군집된 키들을 순차적으로 방문해야 한다는 문제점 : 성능이 극단적으로 저하됨
    • 선형 조사를 위한 삭제 연산에서는 삭제할 원소에 특별한 값이 마킹되어 있어야 함
  • 이차 조사 (Quadratic probing) : 충돌 후 1차원 리스트 a에서 a[(h(key) + j^2) % m], j = 0, 1, 2, 3, ... 으로 선형 조사보다 더 멀리 떨어진 곳에서 empty 원소를 찾는 방법
    • 이웃하는 빈 곳이 채워져 만들어지는 1차 군집화는 해결 되지만 같은 해시 값을 갖는 서로 다른 키들인 동의어(Synonym)들이 똑같은 Jump sequence를 따라 empty 원소를 찾아 저장하므로 또 다른 형태의 군집화인 2차 군집화(Secondary clustering)를 야기
    • 점프 크기가 제곱만큼 커지므로 1차원 리스트에 empty 원소가 있는데도 empty 원소를 건너뛰어 저장에 실패하는 경우도 피할 수 없음
    • 무한 루프 발생 가능성이 있으므로 루프 수행 횟수를 제어할 필요가 있음
  • 랜덤 조사 (Random probing) : Jump sequence를 무작위화하여 empty 원소를 찾는 방법, Python 언어의 dictionary는 랜덤 조사를 기반하여 구현됨
    • 2차 군집화와 유사한 형태의 3차 군집회(Tertiary clustering) 발생
  • 이중 해싱 (Double hashing) : 두 개의 해시 함수를 사용하여 충돌이 발생하면 두 번째 해시 함수를 이용해 empty 원소를 찾는 방법
    • 모든 군집화 문제를 해결하는 충돌 해결 방법
    • 해시 성능을 저하시키지 않는 동시에 해시 테이블에 많은 키들을 저장할 수 있음
• 수행 시간
  • 모든 키가 한 가지의 Hash value를 가지는 경우에 최악 경우 : O(n) 소요, 그러나 확률이 아주 아주 낮고, 해시 함수 자체를 잘못 설정한 것임
  • 평균 경우 해싱은 O(1) 시간이 기대됨