[알고리즘] 해시테이블(1) - 설명

해시란 키를 직접 조사하여 저장 주소를 찾는 방식이다

해시테이블은 키-주소 매핑에 의해 구현된 사전ADT이다

그리고 해시테이블은 버켓 배열과 해시함수로 이루어져있다. 버켓배열은 해시테이블을 구현한 1차원 배열을 의미하고, 해시함수는 키-주소 매핑을 위한 연산을 수행하는 함수이다.

해시함수 h는 주어진 형의 키를 고정 범위[0, M-1]로 매핑한다

Ex) 해시함수 h

h(x) = x % M    (h는 정수 키 x에 대한 해시함수이다)

정수 h(x)를 키x의 해시값이라 한다. 주어진 키 형의 해시테이블은 다음으로 구성된다 

- 해시함수h

- 크기M의 배열(해시테이블)

사전을 해시테이블로 구현할 때의 목표는 항목(k, e)를 첨자 i = h(k)에 저장하는 것이다.

해시함수는 보통 두 복함수의 복합체로 명세된다. (2가지 단계)

1단계 - 해시코드맵 : keys -> integers (키값을 정수로)

2단계 - 압축맵 : integers -> [0, M-1] (정수를 방으로 압축)

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

Ex)

임의의 키들	-->	...	-->	0
	-->	...	-->	1
	해시코드맵	-1	압축맵	2
		0		...
		1		...
	-->	2	-->	...
	-->	...	-->	M-1

해시코드맵의 종류

- 메모리 주소

키 개체의 메모리 주소를 정수로 재해석한다. 수치 또는 문자열 키에는 적용이 곤란하다는 단점이 있다. 왜냐하면 동일한 값의 수치나 문자열이 두군데 이상의 매모리에 존재할 경우 각 주소에 따라 상이한 수로 매핑될 수 있기 때문이다

- 정수 캐스트

키의 비트값을 정수로 재해석한다. 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에 사용하기에는 적당하다.

- 요소합

키의 비트들을 고정길이(16bits OR 32bits)의 요소들로 분할한 후 각 요소를 합한다(overflow는 무시) 문자의 순서에 의미가 있는 문자열 키에는 부적당하다는 단점이 있다. 왜냐하면 공통 문자들에 의해 원치 않는 충돌이 발생하기 때문이다

- 다항 누적

요소합에서와 마찬가지로 키의 비트들을 고정길이(8bits OR 16bits OR 32bits)의 요소들로 분할한다. 후에 고정값z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산한다(overflow는 무시)

압축맵의 종류

- 나머지셈

해시테이블의 크기 M은 일반적으로 소수로 선택한다

- 승합제

여기서 a와 b는 음이 아닌 정수로서 a%M은 0과 같지 않아야한다. 그렇지 않으면 모든 정수가 동일한 수 b로 매핑되기 때문이다

충돌은 두 개 이상의 원소들이 동일한 셀로 매핑됨을 말한다

다시말해서 키a와 키b에 대해 k(a) = k(b)면 충돌이 일어났다고 말한다.

충돌 해결을 위한 전략으로는 분리연쇄법과 개방주소법 두 가지가 있다.

분리연쇄법은 각 버켓에 리스트를 참조시키는 것이다. 분리연쇄법은 단순하고 빠르다는 장점이 있지만, 추가적으로 저장공간을 필요로하는 단점이 있다.

Ex) h(k) = k%M / 키 - 25, 13, 16, 15, 7, 28, 31, 20, 1

개방주소법은 충돌항목이 테이블의 다른 셀에 저장된다. 개방주소법은 공간사용을 절약하지만, 삭제가 어렵고 군집화하는 단점이 있다

- 선형조사법

충돌항목을 바로 다음의 비어 있는 테이블 셀에 저장함으로서 충돌을 처리한다

Ex) h(k) = k%M / 키 - 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

- 2차조사법

다음 순서에 의해 버켓을 조사한다.

A[h(k)], A[h(k) + 1], A[h(k) + 4], A[h(k) + 9], A[h(k) + 16].............

Ex) h(k) = k%M / 키 - 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

- 이중해싱

두 번째의 해시함수 h'을 사용하여 다음 순서에 의해 버켓을 조사한다. (단, h'(k)와 M이 서로소여야 한다)

Ex) h(k) = k%M / h'(k) = 11 - (k%11) / 키 - 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사