7. 해시테이블

키-주소 매핑에 의해 구현된 사전

해시테이블 = 버켓 배열 + 해시 함수

• 항목들의 키를 주소로 매핑하여 1차원 배열에 사전 항목을 저장

성능

• 탐색, 삽입, 삭제: O(n) 최악, O(1)기대시간

버켓 배열 이란?

버켓배열: 크기 M의 배열로 키 원소 쌍을 담는 그릇

• 없을 경우 NoSuchKey라는 개체를 담고 있음

이상

• 키가 유일한 정수이고, [0~M-1]범위에 잘 분포 되어있다면, 탐색, 삽입, 삭제에 O(1)최악 시간

결함

• O(n)의 공간을 사용하므로 M이 n에 비해 너무 크면 공간 낭비이다.
• 키들이 [0,M-1]범위 내의 유일한 정수여야하나, 비현실적

목표

• 키를 [0,M-1] 범위내의 정수로 매핑하는 적절한 방식이 필요하다.

해시 함수

주어진 형의 키를 고정범위 [0, M-1]로 매핑

ex) h(x) = x % M 여기서 h(x)는 해시값이라한다.

사전을 해시 테이블로 구현할 때, (k,eK)를 첨자 i = h(k)에 매핑하는 것

해시코드맵: h1: keys → integers(매핑의 역할)

압축맵: h2: integers →[0, M-1](매핑된 값으로 인덱스 구함)

• 키들을 외견상 무작위하게 분산시키고
• 계산이 빠르고 쉬워야한다.(상수시간에 해야한다)
• 키 > 해시코드맵 > 압축맵

해시코드맵

메모리 주소

• 키 개체의 메모리 주소를 정수로 재해석
• ‘total’ = 1101101010(주소값) → 3824(십진으로 매핑)
• 수치, 문자열 키에는 적용하기 힘듦

정수 캐스트

• 키의 비트값을 정수로 재해석
• ‘total’=100101101110(비트값)→107(십진으로 매핑)
• 정수형에 할당된 비트 수를 초과하지 않는 키에는 적당하다.

요소합

• 키의 비트들을 고정길이의 요소들로 분할 하고, 각 요소를 합한다.(Overflow된 값은 무시)
• ex) ‘total’ = 28+32+28+17+19 = 132
• 즉, 순서에 의미가 있는 문자열 키에는 부적당하다.

다항 누적

• 고정값z를 사용해 각 요소의 위치에 따라 별도로 추가 계산
• ex)’total’ = 28+322+282^2+172^3+192^4=568(z = 2)
• 문자열에 특히 적당함(z가 33일경우 5만개의 영단어에 대해 6회충돌만 일어남

압축맵

나누기

• h2(k) = |k|%M
• 해시 테이블의 크기 M은 일반적으로 소수(prime Number)로 선택

승합제

• h2(k) = |ak + b| %M
• a와 b는 음이 아닌 정수로서 a%M ≠ 0

충돌

두개 이상의 원소들이 동일한 셀로 매핑됨

• 즉h(k1) = h(k2)

분리연쇄법

A로 매핑한 모든 함수를 리스트 또는 기록파일 방식으로 저장함.

단순하고, 빠르지만 테이블 외부에 추가 저장공간 요구

개방주소법

충돌 항목의 테이블의 다른 셀에 저장한다.

• 공간 사용을 절약하지만 삭제가 어렵다.
• 일부를 건너뛰는 방식으로 찾음
  • 여러 개의 항목이 같은 셀에 매핑될 경우 계속 위와 같은 방식이 되는데,
  • 중간에 한 항목이 삭제될 때 그냥 삭제하면 그 다음 값을 못찾게됨, 따라서 옮겨주어야함.

선형조사법

25,13,16,15,7,28,31,20,1,38 순서대로 삽입

개방주소법의 한가지 방법으로 바로 다음의 비어있는 테이블 셀에 저장하여 충돌 처리

• 검사되는 각 테이블 셀은 조사(probe)라고 부른다.
• h(k) = k%M
• 위는 38을 삽입
• 위에서 보면 충돌 항목들이 모이게 되어 군집을 이루는 1차 군집화 현상이 일어난다.

2차 조사법

25,13,16,15,7,28,31,20,1,38 순서대로 삽입

개방 주소법의 한가지 방법으로 제곱수로 넣어줌.

• 1차 군집화는 피하지만 나름대로의 군집을 형성하는 2차군집화 현상이 일어난다.
• h(k) = k % M , f(i) = i^2
• M이 소수가 아니거나 버켓 배열이 반 이상 찰 경우 비어있는 버켓이 남아있더라도 찾지 못할 수 있따.

이중해싱

25,13,16,15,7,28,31,20,1,38 순서대로 삽입

개방주소법의 한가지 방법으로 두번째 해시 함수를 이용하여 h’를 이용하여 버켓을 조사

• 최선의 결과를 위해 h’(k)와 M은 서로소여야한다.
• 위의 예시 h(k) = k%M, h’(k) = 11-(k%11)

개방주소법에서의 갱신

기존 태그: empty(비어있는 셀), active(활성)

추가 태그: inactive(비활성)

findElement(k)

• 셀 h(k)에서 출발하여, 다음 가운데 하나일 때 까지 조사
  • 비어있는 셀을 만나면 탐색 실패
  • 활성셀의 항목 (k,e)를 만나면 e를 반환
  • M개의 셀을 검사 이후 없으면 탐색 실패

insertItem(k, e)

• 셀 h(k)에서 출발하여, 다음 가운데 하나일 때까지 조사
  • 비어있거나 비활성인 셀을 만나면 항목 (k,e)를 셀에 저장한 후 활성화
  • M개의 셀을 검사시에 비활성, 빈공간 없으면 예외 발령(테이블 가득참)

removeElement(k, e)

• 셀 h(k)에서 출발하여 다음 가운데 하나일때까지 조사
  • 비어있는 셀을 만나면 탐색 실패
  • 활성 셀의 항목 (k,e)를 만나면 비활성화 후 e를 반환
  • M개의 셀을 검사후 없으면 탐색 실패

적재율

좋은 해시 함수를 사용할 경우 각 버켓의 기대 크기(a = n/M)

• 적재율은 낮게 가능하면 1아래로

분리 연쇄법

• a > 1일 경우 작동은 하지만 비효율적
• a ≤ 1(가능하면 0.75)일 경우 O(1)의 기대실행시간 성취 가능

개방 주소법

• 항상 a ≤ 1
• a > 0.5일 경우 선형, 2차 조사법인 경우 군집화 가능성
• a ≤ 0.5일 경우 O(1)의 기대실행시간 성취 가능

재해싱

테이블의 적재율을 상수 이하로 유지하기 위해

• 버켓 배열의 크기를 증가시키고,
• 새 크기에 대응하도록 압축맵을 수정하며
• 새 압축맵을 사용하여 기존 해시테이블의 모든 원소들을 새 테이블에 삽입

재해싱을 해야할 때

• 적재율의 최적치를 초과했을 때(0.75)
• 삽입이 실패한 경우
• 너무 많은 비활성 셀들로 포화되어 성능이 저하되었을 때

해싱의 성능

• 삽입, 삭제, 탐색등 최악의 경우 O(n) 시간
  • `최악의 경우, 사전에 삽입된 모든 키가 충돌할 경우
• 적재율 a = n/N은 해시테이블의 성능을 좌우함.