13 해싱 Hashing
출처
- C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저)
목차
- 해싱의 개념
1-1. 해싱이란
1-2. 해시테이블 Hash Table
1-3. 해싱의 구조
1-4. 해시함수
- 개방 주소법 Open Addressing
2-1. 선형 조사법 Linear Probing
2-2. 이차 조사법 Quadratic Probing
2-3. 이중 해싱법 Double Hashing
1. 해싱의 개념
1-1. 해싱이란?
해싱을 한 마디로 표현하자면 복호화가 불가능한 일방향 암호이다.
해싱이란 앞에서 배웠던 반복 비교를 사용하지 않고 특정 계산만으로 자료의 저장 주소를 찾아내는 탐색 방법이다. O(1)의 시간복잡도로 값을 찾아내는 것이다. 여기서 말하는 특정 계산이란 키 값을 해시 함수로 연산해 결과값을 주소로 값에 접근하는 것을 말한다.
해싱을 구현하는 방법은 다양하며 가장 많이 알려진 방법은 정적 해싱 중 하나인 제산법이다. mod 연산을 통해 키 값을 구하는 방식이다. 그 외에도 중간제곱법, 폴딩법, 기수변환법, 확장 해싱 등이 존재한다.
1-2. 해시테이블 Hash Table
해시테이블은 [키, 값]이 한 쌍이 이루는 집합이다. 연관 배열 추상 데이터 유형을 구현하는 데이터 구조로서, 키를 값에 매핑할 수 있다. 대부분의 상황에서 해시테이블은 검색 트리나 다른 테이블 조회 구조보다 평균적으로 더 효율적이다.
맵 Map이나 딕셔너리 Dictionary로 부르기도 한다. 자바에서는 해시맵 HashMap이란 호칭을 사용한다. 파이썬에서는 딕셔너리 Dictionary와 같은 개념으로 사용되지만 C#에서는 제너릭형인지 오브젝트형인지에 따라 해시테이블과 딕셔너리에 차이가 있는 것으로 보인다.
- 딕셔너리 Dictionary의 추상 자료형(ADT)
객체: 일련의 (key, value) 쌍의 집합
연산:
add(key, value) ::= (key, value)를 사전에 추가한다.
delete(key) ::= key에 해당하는 (key, value)를 찾아 삭제한다. 관련된 value를 반환한다. 만약 탐색이 실패하면 NULL을 반환한다.
search(key) ::= key에 해당하는 value를 찾아 반환한다. 만약 탐색에 실패하면 NULL을 반환한다.
1-3. 해싱의 구조
해싱에서는 자료를 저장할 때 배열을 사용한다. 원하는 항목이 들어있는 위치를 알고 있다면 빠르게 자료에 접근할 수 있다는 장점때문이다. 만약 해당 값의 key 값을 바로 알아낼 수만 있다면 상수 시간 안에 연산을 종료할 수 있다.
해싱은 어떤 항목의 키만 가지고 항목이 들어 있는 배열의 인덱스를 결정하는 기법이다. 해시 함수는 키 입력을 받아 해시 주소를 생성하고 이 해시 주소를 해시 테이블의 인덱스로 사용한다.
해시테이블은 버켓과 슬롯으로 구성되어 있다. 만약 해시 테이블의 버킷의 수가 상대적으로 작아져 할당된 슬롯 수보다 많은 충돌이 발생하게 되면 버킷에 더 이상 항목을 저장할 수 없게 되는 오버플로우 Overflow가 발생하게 된다. 이럴 때는 해시 함수를 수정하거나 해시테이블의 크기를 적절히 조절해줘야 한다.
알파벳 앞자리에 의해 키가 결정된다고 가정해보자. a일 때는 0이고 b이면 1인 식이다. 입력데이터가 array, binary, bubble, file, digit, direct, zero, bucket 순이라고 할 때 아래 해시테이블과 같이 슬롯이 2칸인 경우, bucket이 오버플로우로 인해 저장되지 못하는 것을 확인할 수 있다.
1-4. 해시함수
해시 함수를 정하는 데 있어서 중요한 것은 3가지 이다.
- 충돌이 적어야 한다.
- 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다.
- 계산이 빨라야 한다.
- 제산 함수
h(k)=k mod M로 표현된다.- 해시 테이블의 크기 M은 주로 소수(prime number)로 선택한다.
int hash_function(int key)
{
int hash_index = key % M;
if (hash_index < 0)
hash_index += M;
return hash_index;
}- 폴딩 함수
- 32비트 키를 2개의 16비트로 나누어 비트별로 XOR 연산을 하는 코드는 다음과 같다.
hash_index = (short)(key ^ (key>>16)- 이동 폴딩(shift folding)과 경계 폴딩(boudary folding)
- 중간 제곱 함수
- 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성하는 방법이다.
- 비트 추출 방법
- 탐색키를 이진수로 간주(해시 테이블의 크기 M = 2^k일 경우)하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 방법이다.
- 해시 주소의 집중 현상이 발생할 가능성이 높다.
- 숫자 분석 방법
- 키 중에서 편중되지 않은 수들을 해시테이블의 크기에 적합하게 조합하여 사용하는 방법이다.
- 탐색키가 문자열일 경우
int hash_function(char *key)
{
int hash_index = 0;
while(*key)
hash_index = g * hash_index + *key++;
return hash_index;
}2. 개방 주소법 Open Addressing
충돌(collision)이란 서로 다른 키를 갖는 항목들이 같은 해시주소를 갖는 현상을 말한다. 충돌이 발생하고 빈 버킷이 없으면 오버플로우가 발생한다. 충돌을 해결하는 방법은 2가지가 있다. 개방주소법과 체이닝 기법이다.
2-1. 선형 조사법 Linear Probing
개방 주소법은 특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾는 방법이다. 비어있는 버킷에 항목을 저장하게 된다. 여기서 비어있는 공간을 찾는 것을 조사(probing)이라고 한다.
선형 조사법은 선형 탐색과 같이 오버플로우가 발생했을 때 항목의 저장을 위해 빈 버킷을 순차적으로 탐색해나간다.
선형 조사법에서 삭제가 가능하게 하려면 한 번도 사용하지 않은 버킷과 사용했지만 현재는 비어있는 버킷, 현재 사용 중인 버킷으로 분류해야한다. 여기서 한 번도 사용되지 않은 버킷을 만나야만 탐색이 중단되도록 해야하는데, 똑같은 키값이 할당된 값들 중 중간에 있는 값이 삭제되면 탐색할 때 그 비어있는 값에서 멈춰버리면 뒤의 값들을 탐색하지 못하는 일이 발생하기 때문이다.
선형 조사법 코드 링크: 선형 조사법
2-2. 이차 조사법 Quadratic Probing
선형 조사법과 유사하지만 다음 조사할 위치를 다음 공식으로 정한다. (h(k)+i*i) mod M
위 식에 의해 조사되는 값은 h(k) -> h(k)+1 -> h(k)+4 -> h(k)+9 -> ... 순이 될 것이다.
이차 조사법은 선형 조사법에서의 문제인 군집과 결합을 완화할 수 있다는 장점이 있다. 다만 2차 집중 문제를 일으킬 수 있지만 1차 집중과 같이 결정적인 결함은 아니다.
이차 조사법 코드 링크: 이차 조사법
2-3. 이중 해싱법 Double Hasing
이중 해싱법은 재해싱이라고 부르기도 한다. 오버플로우가 발생하면 원 해시 함수와 다른 별개의 해시 함수를 사용하는 방법이다. 항목들을 균일하게 분포시킬 수 있다는 점이 장점이다. 앞에서 살펴본 조사법들은 충돌이 일어나면 해시 함수의 결과값에 특정 값을 더해 다음 위치를 얻는 방식이었다. 그렇기 때문에 어떤 값의 해시 함수 값이 같으면 차후에 조사하는 위치도 같게 된다는 문제가 있다.
이중 해싱법은 키를 참조하여 더해 `step = C-(k mod C)`으로 다음 조사할 위치의 간격을 정할 수 있다.
충돌이 발생했을 때 h(k) -> h(k)+step -> h(k)+2*step -> ... 순으로 진행되며 빈 버킷을 찾을 것이다. 크기가 7인 해시테이블에서 (8, 1, 9, 6, 13)을 입력하는 예시는 아래와 같다.
이중 해싱법 코드 링크: 이중 해싱법
3. 체이닝 Chaining
선형 조사법이 탐색 시간이 많이 걸리는 이유는 충돌 때문에 해시 주소가 다른 키하고도 비교를 해야 한다는 것 때문이다. 이를 연결리스트를 이용해 동적할당한다면 메모리도 아끼고 불필요한 비교도 하지 않을 수 있다. 이를 통해 오버플로우 문제도 해결할 수 있다.
이중 해싱법과 같은 예시를 체이닝 기법으로 적용하면 아래와 같은 결과가 나온다. (크기가 7인 해시 테이블, [8, 1, 9, 6, 13] 순으로 입력)
이중 해싱법 코드 링크: 이중 해싱법
4. 해싱의 성능 분석
| 탐색방법 | 탐색 | 삽입 | 삭제 | |
|---|---|---|---|---|
| 순차탐색 | O(n) | O(1) | O(n) | |
| 이진탐색 | O(log2n) | O(log2n + n) | O(log2n + n) | |
| 이진탐색트리 | 균형트리 | O(log2n) | O(log2n) | O(log2n) |
| 경사트리 | O(n) | O(n) | O(n) | |
| 해싱 | 최선의 경우 | O(1) | O(1) | O(1) |
| 최악의 경우 | O(n) | O(n) | O(n) |
