컴퓨터알고리즘#13

LeeMir, 12 May 2021

해시테이블

키 - 주소 매핑에 의해 구현된 사전 ADT
해시테이블 = 버켓 배열 + 해시함수
- 버켓 배열
  - 크기 M의 배열 A
  - A의 각 셀을 버켓으로 봄(슬롯이라고도 함)
  - 키 k를 가진 원소 e는 버켓 A[k]에 삽입(정확히는 A[h(k)]), 해시함수의 결과를 idx로 사용)
  - 사전에 존재하지 않는 키에 속하는 버켓 셀들은 NoSuchKey라는 특별한 개체를 담는 것으로 가정
- 해시함수
  - 주어진 형의 키를 고정 범위 [0, M-1]로 매핑
  - h(x) = 정수 키 x의 해시값
  - 주어진 키 형의 테이블은 해시함수 h와 크기 M의 배열(테이블)로 구성
성능
- 탐색, 삽입, 삭제 : O(n)의 최악 시간, O(1)의 기대 시간(키가 [0, M-1] 범위에 고르게 분포되어 있을 경우)
- M이 n에 비해 매우 크다면 공간 낭비
- 키들이 [0, M-1] 범위 내의 유일한 정수여야 하지만, 이는 종종 비현실적
해시코드맵
- 메모리 주소
  - 키 개체의 메모리 주소를 정수로 재해석
  - 동일한 값이 객체로 존재할 경우 다른 저장 공간에 저장해있어 적용하기 곤란
- 정수 캐스트
  - 키의 비트값을 정수로 재해석
  - 정수형에 할당된 비트수를 초과하지 않는 길이의 키에는 적당
- 요소합
  - 키의 비트들을 고정길이의 요소들로 분할한 후 각 요소를 합함
  - 정수형에 할당된 비트 수 이상의 고정길이의 수치 키에 적당
  - 문자의 순서에 의미가 있는 문자열 키에는 부적당
    - 예 : stop-tops-spot-pots
- 다항 누적
  - 요소합과 마찬가지로, 키의 비트들을 고정길이의 요소들로 분할
  - 고정값 z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산(overflow는 무시)
  - 문자열에 특히 적당
    - 예 : 고정값 z = 33을 선택할 경우, 50000개의 영단어에 대해 단지 6회의 충돌 발생
압축맵
- [0, M-1]에 매핑
- 나누기
  - h2(k) = k % M
  - 해시테이블의 크기 M은 일반적으로 소수로 선택
- 승합제(Multiply, Add and Divide, MAD)
  - h2(k) = ak + b % M
  - a와 b는 음이 아닌 정수로서 a % M != 0
    - 그렇지 않으면, 모든 정수가 동일한 값 b로 매핑됨
충돌 해결
- 충돌 : 두 개 이상의 원소들이 동일한 셀로 매핑
  - 즉, 상이한 키, k1과 k2에 대해 h(k1) = h(k2)면 충돌이 발생했다고 말함
- 분리연쇄법
  - 각 버켓 A[i]는 리스트 Li에 대한 참조를 저장
    - Li는 해시함수가 버켓 A[i]로 매핑한 모든 항목들을 저장
    - 무순리스트 또는 기록파일 방식을 사용하여 구현된 미니 사전이라 볼 수 있음
  - 단순하고 빠르다는 장점이 있으나 테이블 외부에 추가적인 저장공간을 요구
- 개방주소법
  - 충돌 항목을 테이블의 다른 셀에 저장
  - 분리연쇄법에 비해 공간 사용을 절약하지만, 삭제가 어렵다는 것과 사전 항목들이 연이어 군집화
- 선형조사법
  - 충돌 항목을 바로 다음의 비어 있는 테이블 셀에 저장함으로써 충돌을 처리
  - 검사되는 각 테이블 셀은 조사(probe)라 불림
  - 충돌 항목들은 군집화하며, 이후의 충돌에 의해 더욱 긴 조사열로 군집 - 1차 군집화
- 2차 조사법
  - 순서를 +0, +1, +4, +9 …의 순서로 조사함
  - 해시값이 동일한 키들은 동일한 조사를 수반
  - 1차 군집화를 피하지만 나름대로의 군집을 형성 - 2차 군집화
  - M이 소수가 아니거나 버켓 배열이 반 이상 차면, 비어 있는 버켓이 남아 있더라도 찾지 못할 수 있음
- 이중해싱
  - 두번째의 해시함수 h’를 사용하여 +0, +h’(k), +2h’(k), +3h’(k)의 순서로 조사
  - 일반적으로 h'(k) = q - (k % q) 또는 1 + (k % q)를 사용 - q < M은 소수, M 역시 소수
적재율
- 해시테이블의 적재율 α = n/M
- 해시테이블의 적재율을 상수(보통 0.75) 이하로 유지하기 위해서는, 원소를 삽입할 때마다 이 한계를 넘기지 않기 위해 추가적인 작업 필요
- 재해싱
  - 버켓 배열의 크기를 원래 배열의 대략 두 배 크기로(소수여야함) 증가 후 새 크기에 대응하도록 압축맵을 수정하고, 새 압축맵을 사용해 기존 해시테이블의 모든 원소들을 새 테이블에 삽입