[알고리즘] ep4) 해시테이블(hashtable)

선형검색에 반해 해시테이블의 검색시간은 평균적으로 상수시간이다 (사전에 삽입된 모든 키가 충돌하는 최악의 경우는 O(n))

해시테이블의 상수시간이 가능한 이유는 "해시함수"를 통해 바로 접근하기 때문이다

ㅁ해시테이블(hashtable): 버켓배열 + 해시함수

(key, address) 맵핑에 의해 구현된 사전 ADT

※ key-value는 키와 값을 직접 연결하는 방식이라면, key-address는 키가 실제 데이터의 위치(주소)를 가리키는 방식

 

e.g. 컴파일러의 심볼 테이블, 환경변수들의 레지스트리, 소규모 DB, 브라우저 캐시

 

 

ㅇ버켓배열(bucket array) = 테이블

크기 M의 배열 A

 

버켓을 슬롯(slot)이라고도 한다

 

 

ㅇ해시함수(hash fucntion): 맵핑하는 역할

e.g. h(x) = x % M

h(x)는 정수 키 x에 대한 해시함수

 

[좋은 해시함수가 되기 위한 조건]

- 키들을 외견상 무작위(random)하게 분산시켜야 한다

- 계산이 빠르고 쉬워야 한다 (가능하면 상수시간)

 

해시함수는 보통 두 함수의 복합체로 명세한다

"먼저 해시코드맵을 적용하고 그 결과에 압축맵을 적용한다"

e.g.

학번 -> 마지막 4자리 수 -> 방 번호 [0, 2]

식별자 -> 문자 합 -> 심볼 테이블 행 번호 [0, 27]

 

1. 해시코드맵(hashcode map)

ㅇ메모리 주소(memory address): 키 개체의 메모리 주소를 정수로 재해석

- 모든 java 객체들의 기본 해시코드이다

- 일반적으로 만족스러우나 수치 또는 문자열 키에는 적용이 곤란하다

 

ㅇ정수 캐스트(integer cast): 키의 비트값을 정수로 재해석

- 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에는 적당

e.g. Java의 byte, short, int, float

 

ㅇ요소합(component sum): 키의 비트들을 고정길이(e.g. 16bits, 32bits)의 요소들로 분할한 후 각 요소를 합한다 (overflow는 무시)

- 정수형에 할당된 비트 수 이상의 고정길이의 수치 키에 적당

 e.g. Java의 long, double

- 문자의 순서에 의미가 있는 문자열 키에는 부적당

e.g. temp01-temp10, stop-tops-spot-pots

 

ㅇ다항 누적(polynomial accumulation): 요소합과 마찬가지로, 키의 비트들을 고정길이(e.g. 8bits, 16bits, 32bits)의 요소들로 분할 + 고정값 z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산 (overflow는 무시)

- 문자열에 특히 적당

e.g. 고정값 z=33을 선택할 경우, 50000개의 영단어에 대해 오직 6회의 충돌이 발생

 

2. 압축맵(compression map)

ㅇ나누기(division)

h(k) = |k| % M

"해시테이블의 크기 M은 일반적으로 소수로 설정한다"

 

ㅇ승합제(MAD, multiply + add and divide)

h(k) = |ak + b| % M

 

 

 

ㅁ충돌(collision): 두 개 이상의 원소들이 동일한 셀로 맵핑되는 것

즉, 상이한 키 k1과 k2에 대해 h(k1) = h(k2) 면 충돌이 일어난 것이다

 

 

 

이러한 충돌을 대처하는 여러 가지 전략들이 있다

ㅇ연쇄법(chaining) or 분리연쇄법(separate chaining): 각 버켓에 리스트에 대한 참조를 저장

2차원 배열의 hashtable을 사용한다

 

단순하고 빠르다는 장점이 있지만, 테이블 외부의 추가적인 저장공간을 요구한다는 단점이 있다

 

(예시) 해시테이블의 크기 M은 13이라 가정

h(k) = k % M

key: 25, 13, 16, 15, 7, 28, 31, 20, 1

28과 20은 뒤이어 붙게 된다

 

 

ㅇ개방주소법(open addressing): 충돌 항목을 테이블의 다른 셀에 저장

선형 조사, 이차 조사, 이중 해시의 3가지 방법이 있다

분리연쇄법에 비해 공간 사용을 절약한다

 

 

- 선형 조사(linear probing): 충돌 항목을 바로 다음의 비어 있는(원형으로) 테이블 셀에 저장함으로써 충돌을 처리하는 방법

검사 되는 각 테이블 셀은 조사(probe)라 불린다

 

(예시) 해시테이블의 크기 M은 13이라 가정

h(k) = k % M

key: 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

 

 

 

- 이차 조사(quadratic probing): 해시 충돌이 일어나면 증가하는 제곱수(1, 4, 9, 16, ..)를 더해가며 빈 셀을 찾는 방법

M이 소수가 아니거나 버켓배열이 반 이상 차면, 비어 있는 버켓이 남아 있더라도 찾지 못할 수가 있다

 

(예시) 해시테이블의 크기 M은 13이라 가정

h(k) = k % M

key: 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

마지막 38은 5^2가 더해진 상황

 

 

- 이중 해싱(double hashing): 충돌이 발생했을 때 두 번째 해시 함수를 이용해 새로운 인덱스를 계산하여 충돌을 피하는 방법

두 번째 해시 함수 h'(k)는 충돌이 발생했을 때 이동할 간격(step size)을 제공한다

충돌이 발생할 때마다 h'(k)의 값을 더해가며 빈 슬롯을 찾게 된다 (h'는 계산 결과가 0이 되면  안 된다)

최선의 결과를 위해 h'(k)와 M은 서로소여야 한다

 

(예시) 해시테이블의 크기 M은 13이라 가정

h(k) = k % M, h'(k) = 11 - (k % 11)

key: 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

클러스터링 ↓ but 구현 복잡

 

k = 28일 때 h'(k) = 5(step size = 5)이므로 5를 더해가며 빈 슬롯을 찾는다

k = 20일 때 h'(k) = 2(step size = 2)이므로 2를 더해가며 빈 슬롯을 찾는다

k = 38일 때 h'(k) = 6(step size = 6)이므로 6을 더해가며 빈 슬롯을 찾는다

 

 

 

ㅇ적재율(load factor): a = n / M

적재율은 1 아래로 항상 낮게 유지되어야 한다

좋은 해시함수가 주어졌다면, 모든 작업의 기대실행시간은 O(a) 이다

 

[연쇄법 case]

a > 1: 작동은 하지만 비효율적

a <= 1: O(a) = O(1) 의 기대실행시간 가능

 

[개방주소법 case]

(항상 적재율이 1 이하이다)

a > 0.5: 선형 조사 or 이차 조사인 경우 군집화 가능성 농후

a <= 0.5: O(a) = O(1) 의 기대실행시간 가능

 

 

 

ㅇrehashing(재해싱): 해시테이블의 크기 M을 늘려 성능을 개선하기 위해 사용되는 방법

일반적으로 적재율이 '0.75'를 초과하게 되면 rehashing을 고려 (해시 인덱스가 자주 충돌하기 시작)

 

[rehashing을 하는 상황]

- 적재율의 최적치를 초과했을 때

- 삽입에 실패했을 때

- 너무 많은 비활성 셀들로 포화되어 성능이 저하되었을 때

 

[rehashing의 순서]

1. 버켓 배열의 크기를 증가시킨다(원래 배열의 대략 두 배 크기로 - 이때 새 배열의 크기를 소수로 설정하는 것에 유의)

2. 새 크기에 대응하도록 압축맵(compression map)을 수정

3. 새 압축맵을 사용하여, 기존 해시테이블의 모든 원소들을 새 테이블에 삽입

 

 

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan), 해시-해시테이블-해싱 5분만에 이해하기(코딩하는거니)