해싱(Hashing)
[해싱이란?]
- 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근함.
- 하지만 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근함.
- 해시 테이블(hash table) : 키 값의 연산에 의해 직접 접근이 가능한 구조
- 해싱(hashing) : 해시 테이블을 이용한 탐색
- 해싱은 일상생활에서의 정리 정돈으로 비유할 수 있음.
- 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있으면 O(n)이고 정렬되어 있으면 O(log₂n).
- 이 정도의 시간 복잡도가 허용되는 경우도 있는 반면, 어떤 경우는 더 빠른 탐색 방법이 필요함.
- 해싱은 이론적으로는 O(1)의 시간 안에 탐색을 끝마칠 수도 있음.
- 해싱은 보통 사전(dictionary)와 같은 자료 구조를 구현할 때에 최상의 선택이 됨.
[추상 자료형 사전 구조]
- 사전 구조(dictionary)는맵(map)이나 테이블(table)로 불리기도 함.
- 사전 구조는 다음과 같이 탐색 키와 관련된 값의 2가지 종류의 필드를 가짐.
1. 영어 단어나 사람의 이름 같은 탐색 키(search key)
2. 단어의 정의나 주소 또는 전화 번호 같은 탐색 키와 관련된 값(value)
- 사전구조는 항목들을 탐색 키에 의하여 식별하고 관리함. 항목들의 위치는 상관 없음.
- 따라서 항목들을 접근하고 삭제할 때 단지 탐색 키만 있으면 됨.
- 사전 구조에 있는 항목들은 모두 탐색 키를 가지고 있다는 점에서 리스트와 같은 다른 자료 구조들과는 구분이 됨.
- 리스트에도 물론 탐색 키를 같이 넣어서 저장할 수 있겠지만, 리스트는 근본적으로 위치에 의하여 관리되는 자료 구조.
- 반면 사전 구조는 오직 탐색 키에 의해서만 관리됨.
- 사전 구조에서는 유일한 탐색 키를 사용하기도 하고 동일한 탐색 키를 허용하기도 함.
- 자료 구조에서의 사전 구조에서는 탐색 키에 따라 정렬되어 있기도 하고 그렇지 않기도 함.
- 사전 구조에서는 무조건 탐색 키에 의하여 항목에 접근할 수 있으면 됨.
- 따라서 정렬 여부는 추상 자료형 사전 구조를 구현할 때에 결정하여야 될 문제임.
- 사전 구조의 연산
1. 새로운 항목을 사전에 삽입(add)
2. 탐색 키에 관련된 항목을 삭제(delete)
3. 탐색 키에 관련된 값을 탐색(search)
- 이진 탐색 트리를 사용한 사전 구조는 최악의 경우, 시간 복잡도는 O(n).
- 사전 구조를 가장 효율적으로 구현할 수 있는 방법은 해싱.
- 해싱은 탐색 키의 비교가 아닌 탐색 키에 수식을 적용시켜서 바로 탐색 키가 저장된 위치를 얻음.
[해싱의 구조]
- 해싱의 기본적인 아이디어는 간단함.
- 만약 탐색 키들이 0부터 999까지의 정수라고 가정한다면 가장 빠르게 자료를 저장하고 꺼낼 수 있는 방법은 1000개의 요소를 가지는 배열을 만드는 것.
- 그러면 자료의 삽입과 탐색은 탐색 키를 배열의 인덱스로 생각하고 단지 배열의 특정 요소를 읽거나 쓰면 됨.
- 이들 연산은 명백하게 O(1).
- 하지만, 현실적으로는 탐색 키들이 문자열이거나 매우 큰 숫자이기 때문에 탐색 키를 직접 배열의 인덱스로 사용하기에는 무리가 있으므로 각 탐색 키를 작은 정수로 사상(mapping)시키는 어떤 함수가 필요함.
- 해싱에서는 자료를 저장하는 데 배열을 사용함.
- 배열은 단점도 있지만 만약 원하는 항목이 저장된 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있음.
- 이 경우, 배열의 다른 요소들에는 전혀 접근할 필요가 없음.
- 해싱이란 이런 식으로 어떤 항목의 탐색 키만을 가지고 바로 항목이 저장되어 있는 배열의 인덱스를 결정하는 기법임.
- 해시 함수(hash function) : 탐색 키를 입력으로 받아 해시 주소(hash address)를 생성. 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 됨.
- 이 배열의 인덱스 위치에 자료를 저장할 수도 있고 저장된 자료를 꺼낼 수도 있음.
- 키 값 k를 입력받아 해시 함수 h()로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근함.
- 해시 테이블 ht는 M개의 버켓(bucket)으로 이루어지는 테이블로서 ht[0]0, ht[1], ..., ht[M-1]의 원소를 가짐.
- 하나의 버켓은 s개의 슬롯(slot)을 가질 수 있으며, 하나의 슬롯에는 하나의 항목이 저장됨.
- 하나의 버켓에 여러 개의 슬롯을 두는 이유?
-> 서로 다른 두 개의 키가 해시 함수에 의해 동일한 해시 주소로 변환될 수 있으므로 여러 개의 항목을 동일한 버켓에 저장하기 위해서
- 그러나 대부분의 경우 하나의 버켓은 하나의 슬롯을 가짐.
- 해시 테이블에 존재하는 버켓의 수가 M이므로 해시 함수 h()는 모든 k에 대하여 0≤h(k)≤M-1의 범위의 값을 제공해야 함.
- 대부분의 경우 해시 테이블의 버켓 수는 키가 가질 수 있는 모든 경우의 수보다 매우 작으므로 여러 개의 서로 다른 탐색 키가 해시 함수에 의해 같은 해시 주소로 사상(mapping)되는 경우가 자주 발생함.
- 서로 다른 탐색 키 k1과 k2에 대하여 h(k1) = h(k2)인 경우를 충돌(collision)이라고 하며, 이러한 키 k1과 k2를 동의어(synonym)라 함.
- 만약 충돌이 발생하면 같은 버켓에 있는 다른 슬롯에 항목을 저장하게 됨.
- 충돌이 자주 발생하면 버켓 내부에서의 순차 탐색 시간이 길어져서 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시 테이블의 크기를 적절히 조절해주어야 함.
- 이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(overflow)가 발생하게 됨.
- 만약 버켓당 슬롯의 수가 하나(s=1)이면 충돌이 곧 오버플로우를 의미함.
- 오버플로우가 발생하면 더 이상 항목을 저장할 수 없게 되므로 오버플로우를 해결하기 위한 방법이 반드시 필요함.
- 이상적인 해싱 알고리즘
| add(key, value) index ← hash_function(key) ht[index] = value search(key) index ←hash_function(key) return ht[index] |
-> 해시 테이블이 충분한 공간만 가지고 있으면 잘 동작됨.
- 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 탐색 키당 해시 테이블에서 하나의 공간을 할당할 수가 없음.
- 보통의 경우는 탐색 키는 매우 많고 해시 테이블의 크기는 상당한 제약을 받는 것이 일반적인 상황임.
- 일반적으로 탐색 키에 비하여 해시 테이블의 크기는 작고, 탐색 키 중에 일부만 사용되기 때문에 전체를 위한 공간을 항상 준비할 필요는 없음.
-> 더 작은 해시 테이블을 사용하는 해시 함수를 고안해야 함.
- 간단하면서 강력한 방법은 탐색 키를 해시 테이블의 크기로 나누어서 그 나머지를 해시 테이블의 주소로 하는 것.
- 정수를 해시 테이블의 크기 M으로 나누어서 나머지를 취하면 0에서 M-1까지의 숫자가 생성됨.
- 이 값은 해시 테이블을 위한 유효한 인덱스가 됨.
- 나머지를 구하는 연산자인 mod를 사용하면 해시 함수는 다음과 같이 표시됨.
h(k) = k·mod·M
- 위의 해시 함수는 완벽한 해시 함수가 아니므로 두 개 이상의 탐색 키가 동일한 해시 테이블의 공간으로 사상될 수 있음.
예1) 테이블의 크기를 31이라고 하면 h(00023)와 h(00054)가 같은 주소로 사상됨. -> 충돌 발생.
예2) (하나의 버킷에 여러 개의 슬롯이 있는 경우)
해시 테이블에는 26개의 버켓이 있고, 각 버켓에는 2개의 슬롯이 할당됨. 여기서의 탐색 키는 알파벳으로 되어 있음. 해시 함수는 각 키의 첫 번째 문자를 숫자로 바꿈. 즉, 탐색키가 문자 'a'로 시작하면 해시 주소가 0이고, 문자 'b'로 시작하면 해시 주소는 1이 됨. (array, binary, bubble, file, digit, direct, zero, bucket) 순으로 탐색 키 값이 입력될 경우 -> 저장되는 과정에서 계속 충돌과 오버플로우가 발생.
- 실제의 해싱에서는 충돌과 오버플로우가 빈번하게 발생하므로 시간 복잡도는 이상적인 경우의 O(1)보다는 떨어지게 됨.
[해시 함수]
- 해싱에서는 키 값을 해시 테이블의 주소로 변환하는 해시 함수가 잘 설계되어야만 탐색의 효율이 증대될 수 있음.
- 좋은 해시 함수의 조건
1. 충돌이 적어야 함.
2. 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 함.
3. 계산이 빨라야 함.
- 해시 테이블의 크기가 M인 경우 해시 함수는 탐색 키(주로 정수이거나 문자열)들을 [0, M-1]의 범위의 정수로 변환시켜야 함.
(1) 제산 함수
- 제산 함수 : 나머지 연산자(mod)를 사용하여 탐색 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법.
- 즉, 탐색 키 k에 대하여 해시 함수는 h(k) = k·mod·M으로 하는 것.
- 여기서 M은 해시 테이블의 크기로 해시 함수의 값의 범위는 0~(M-1)이 됨.
- 따라서 해시 테이블의 인덱스로 사용하기에는 이상적인 값이 됨.
- 이는 가장 일반적인 해시 함수로서 해시 테이블의 크기 M은 주로 소수(prime number)로 나누어지지 않는 수로 선택함.
- 이 방법은 다양한 응용 분야에 쉽게 적용할 수 있을 뿐만 아니라, 해시 주소를 상당히 고르게 분포시키는 좋은 방법임.
- M이 짝수라면 k·mod·M은 k가 짝수이면 짝수가 되고 k가 홀수라면 홀수가 됨.
- 만약 메모리 주소를 가지고 해싱을 한다면 k가 짝수가 될 가능성이 높고 (메모리 주소는 보통 2의 배수), 이런식으로 해시 주소가 한쪽으로 편향된다면 해시 테이블을 골고루 사용하지 않으므로 바람직하지 않음.
- 따라서 테이블의 크기인 M은 항상 홀수여야 함.
- 만약 M이 소수라면 즉, 자기 자신과 1만을 약수로 가지는 수라면 k·mod·M은 0에서 M-1을 골고루 사용하는 값을 만들어냄.
- 나머지 연산을 수행했을 때 음수가 나올 가능성에도 대비해야 함.
- 따라서 k·mod·M이 음수라면 여기에 M을 더해서 결과 값이 항상 0에서 M-1이 되도록 해야 함.
- 따라서 최종적인 해시 함수는 다음과 같이 됨.
| int hash_function(int key) { int hash_index = key % M; if(hash_index < 0) { hash_index += M; } return hash_index; } |
(2) 폴딩 함수
- 폴딩 함수 : 탐색 키를 여러 부분으로 나누어 모두 더한 값을 해시 주소로 사용함.
- 탐색 키를 나누고 더하는 방법에는 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 대표적임.
- 이동 폴딩 : 탐색 키를 여러 부분으로 나눈 값들을 더하여 해시 주소로 사용함.
- 경계 폴딩 : 탐색 키의 이웃한 부분을 거꾸로 더하여 해시 주소를 얻음.
- 폴딩 방법을 구현할 때는 키 값을 해시 테이블 크기만큼의 수를 가지는 부분으로 분할한 후, 분할된 부분을 합하여 해시 주소를 만들어줌.
- 폴딩 함수는 주로 탐색 키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용됨.
- 예를 들어 탐색 키는 32비트이고 해시 테이블의 인덱스는 16비트 정수인 경우를 고려할 때, 탐색 키의 앞 16비트만 다르고 뒤의 16비트는 같은 탐색 키인 경우 출돌이 발생할 것임.
- 따라서 탐색 키의 일부만 사용하는 것이 아니고 탐색 키를 몇 개의 부분으로 나누어 이를 더하거나 비트별로 XOR 같은 부울 연산을 하는 것이 훨씬 바람직함.
- 이것을 폴딩(folding)이라고 함.
- 예를 들어, 32비트 키를 2개의 16비트로 나누어 비트별로 XOR 연산을 하는 코드는 다음과 같음.
| hash_index = (short)(key ^ (key>>16)) |
(3) 중간 제곱 함수
- 중간 제곱 함수 : 탐색 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성함.
- 제곱한 값의 중간 비트들은 대개 탐색 키의 모든 문자들과 관련이 있기 때문에 서로 다른 탐색 키는 몇 개의 문자가 같을지라도 서로 다른 해싱 주소를 갖게 됨.
- 탐색 키 값을 제곱한 값의 중간 비트들의 값은 비교적 고르게 분산됨.
(4) 비트 추출 방법
- 비트 추출 방법 : 해시 테이블의 크기가 M=2^k일 때 탐색 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것.
- 이 방법은 아주 간단함.
- 그러나 탐색 키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 높음.
(5) 숫자 분석 방법
- 숫자 분석 방법 : 숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용함
.- 키의 각각의 위치에 있는 숫자 중에서 편중되지 않은 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법임.
- 탐색 키들이 정수일 때는 비교적 쉽게 해시 주소로 변환할 수 있음.
- 그러나 많은 경우, 탐색 키들은 문자열일 수 있음.
- 따라서 문자열로부터 좋은 해시 주소를 생성하는 것이 중요함.
- 대개 문자열 안의 문자에 정수를 할당함.
예) 'a'부터 'z'에 1부터 26을 할당할 수 있음.
- 다른 방법으로는 문자의 아스키 코드 값이나 유니 코드 값을 사용하는 것이 있음.
- 충돌을 막기 위해서는 문자열 안의 모든 문자를 골고루 사용해야 함.
- 가장 보편적인 방법은 각 문자의 아스키 코드 값을 모두 더하는 것.
-> 서로 다른 탐색 키들이 같은 문자로 이루어져 있지 않는 한 비교적 잘 동작함.
-> 그러나 문제점은 탐색 키들이 동일한 문자로 이루어져 있지만 위치가 다른 경우, "are"와 "era"와 같은 탐색 키들은 구분할 수 없음.
-> 아스키 문자 코드의 범위가 65에서 122이기 때문에 만약 3자리로 이루어진 탐색 키의 경우, 195에서 366으로 해시 주소가 집중됨.
- 더 좋은 방법은 문자들의 아스키 코드 값에 위치에 기초한 값을 곱하는 방법. -> 문자열 s가 n개의 문자를 가지고 있다고 가정하고, s 안의 i번째 문자가 u_i라고 하면 해시 주소를 다음과 같이 계산하는 것.
- 여기서 g는 양의 정수.
- 계산량을 줄이기 위하여 다음과 같은 호너의 방법(Horner's method)를 사용할 수 있음.
- 이 방법을 함수로 만들어보면 다음과 같음.
| int hash_function(char *key) { int hash_index = 0; while(*key) { hash_index = g * hash_index + *key++; } return hash_index; } |
- 이 방법은 탐색 키가 긴 문자열로 되어 있을 경우, 오버플로우를 일으킬 수 있음.
- 그러나 C언어에서는 오버플로우를 무시하므로 여전히 유효한 해시 주소를 얻을 수 있음.
- 보통 g의 값으로는 31을 사용함.
- 오버플로우가 발생하면 해시 코드의 값이 음수가 될 수도 있음. -> 이런 경우를 검사해야 함.
[충돌 해결책]
- 충돌(collision) : 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소를 가지는 현상
- 충돌이 발생하면 해시 테이블에 항목을 더 이상 저장하는 것이 불가능해짐.
- 따라서 충돌을 효과적으로 해결하는 방법이 반드시 필요함.
- 충돌을 해결하는 방법으로는 2가지가 있음.
1. 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장함.
2. 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경함.
- 첫 번째 방법은 해시 테이블 안에서 현재 사용되지 않는 공간을 찾는 방법으로 선형 조사법(linear probing)이라고 함.
-> 이 방법은 간단해 보이지만 상당히 복잡해질 수도 있음.
- 해시 테이블의 구조를 바꾸는 두 번째 방법은 체이닝(chaining)으로 대개는 좋은 선택이 될 수 있음.
(1) 선형 조사법
- 선형 조사법 : 특정 버켓에서 충돌이 발생하면 해시 테이블에서 비어 있는 버켓을 찾는 방법
- 이 비어 있는 버켓에 항목을 저장하게 됨.
- 해시 테이블에서 비어 있는 공간을 찾는 것을 조사(probing)라고 하며 여러 가지 방법의 조사가 가능함.
- 선형 조사법에서는 만약 ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어 있는지를 살펴봄.
- 만약 비어 있지 않다면 ht[k+2]를 살펴봄.
- 이런 식으로 비어 있는 공간이 나올 때까지 계속해서 조사하는 방법.
- 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 감.
- 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬 것이 됨.
- 조사되는 위치는 다음과 같이 됨.
h(k), h(k)+1, h(k)+2, h(k)+3, ...
예) h(k) = k mod 7
1단계 (8) : h(8) = 8 mod 7 = 1 (저장)
2단계 (1) : h(1) = 1 mod 7 = 1 (충돌발생)
(h(1)+1) mod 7 = 2 (저장)
3단계 (9) : h(9) = 9 mod 7 = 2 (충돌발생)
(h(9)+1) mod 7 = 3 (저장)
4단계 (6) : h(6) = 6 mod 7 = 6 (저장)
5단계 (13) : h(13) = 13 mod 7 = 6 (충돌 발생)
(h(13)+1) mod 7 = 0 (저장)
1단계 |
2단계 |
3단계 |
4단계 |
5단계 |
|
| [0] | 13 | ||||
| [1] | 8 | 8 | 8 | 8 | 8 |
| [2] | 1 | 1 | 1 | 1 | |
| [3] | 9 | 9 | 9 | ||
| [4] | |||||
| [5] | |||||
| [6] | 6 | 6 |
- 이차 조사법(quadratic probing) : 선형 조사법과 유사하지만, 다음 조사할 위치를 다음 식에 의하여 결정함.
(h(k)+i*i) mod M
- 따라서 조사되는 위치는 다음과 같이 됨.
h(k), h(k)+1, h(k)+4, ...
- 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 함.
- 선형 조사법에서의 문제점인 집중과 결합을 크게 완화함.
- 이 방법도 2차 집중 문제를 일으킬 수 있지만 1차 집중처럼 심각한 것은 아님.
- 2차 집중의 이유는 동일한 위치로 사상되는 여러 탐색 키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문. -> 이중 해싱법으로 해결할 수 있음
- 이중 해싱법(double hashing) / 재해싱(rehashing) : 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법.
- 항목들을 해시 테이블에 더욱 균일하게 분포시킬 수 있으므로 효과적인 방법이라고 할 수 있음.
- 선형 조사법과 이차 조사법은 충돌이 발생했을 경우에 해시 함숫값에 어떤 값을 더해서 다음 위치를 찾음.
- 선형 조사법에서는 더해지는 값이 1이고 이차 조사법에서는 i²이 됨.
- 따라서 해시 함숫값이 같으면 차후에 조사되는 위치도 같게 됨.
- 이중 해싱법에서는 탐색 키를 참조하여 더해지는 값이 결정됨.
- 따라서 해시 함숫값이 같더라도 탐색 키가 다르면 서로 다른 조사 순서를 갖음.
- 따라서 이중 해싱법은 2차 집중을 피할 수 있음.
- 두 번째 해시 함수는 조사 간격을 결정하게 됨.
- 일반적인 형태는 다음과 같음.
step = C - (k mod C)
- 이런 형태의 함수는 [1, C]사이의 값을 생성함.
- 충돌이 발생했을 경우, 조사되는 위치는 다음과 같음.
h(k), h(k) + step, h(k) + 2*step, h(k) + 3*step, ...
- C는 보통 테이블의 크기인 M보다 약간 작은 소수임.
- 이중 해싱에서는 보통 집중 현상이 매우 드묾. (같은 해시 함숫값과 같은 탐색 순서를 가지는 요소들이 거의 없기 때문.)
예) 크기가 7인 해시테이블에서 첫 번째 해시 함수가 k mod M이고 오버플로우 발생 시의 해시 함수 h'(k) = 5-(k mod 5)
입력 파일 (8, 1, 9, 6, 13)
1단계 (8) : h(8) = 8 mod 7 = 1 (저장)
2단계 (1) : h(1) = 1 mod 7 = 1 (충돌발생)
(h(1)+h‘(1)) mod 7 = (1+5-(1 mod 5)) mod 7 = 5 (저장)
3단계 (9) : h(9) = 9 mod 7 = 2(저장)
4단계 (6) : h(6) = 6 mod 7 = 6 (저장)
5단계 (13) : h(13) = 13 mod 7 = 6 (충돌 발생)
(h(13)+h‘(13)) mod 7 = (6+5-(13 mod 5)) mod 7= 1 (충돌발생)
(h(13)+2*h‘(13)) mod 7 = (6+2*2) mod 7= 3 (저장)
1단계 |
2단계 |
3단계 |
4단계 |
5단계 |
|
| [0] | |||||
| [1] | 8 | 8 | 8 | 8 | 8 |
| [2] | 9 | 9 | 9 | ||
| [3] | 13 | ||||
| [4] | |||||
| [5] | 1 | 1 | 1 | 1 | |
| [6] | 6 | 6 |
- 선형 조사법의 문제점은 한 번도 사용되지 않은 위치가 있어야만 탐색이 빨리 끝나게 된다는 것.
- 만약 거의 모든 위치가 사용되고 있거나 사용된 적이 있는 위치라면 실패하는 탐색인 경우, 테이블의 거의 모든 위치를 조사하게 됨.
- 체이닝 방법은 이러한 문제점이 없음.
- 선형 조사법 구현 프로그램
// 선형 조사법 구현 프로그램
#include <stdio.h>
#include <string.h>
#define KEY_SIZE 10 // 탐색 키의 최대 길이
#define TABLE_SIZE 13 // 해시 테이블의 크기 = 소수
#define empty(e) (strlen(e.key) == 0)
#define equal(e1, e2) (!strcmp(e1.key, e2.key))
typedef struct {
char key[KEY_SIZE];
// 다른 필드에 필요한 필드를 여기에 넣는다.
} element;
element hash_table[TABLE_SIZE]; // 해시테이블
void init_table(element ht[]) {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
ht[i].key[0] = NULL;
}
}
// 문자로 된 탐색 키를 숫자로 반환
int transform(char *key) {
int number = 0;
while (*key) { // 간단한 덧셈 방식 사용 자연수 생성
number += *key++;
}
return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char *key) {
return transform(key) % TABLE_SIZE;
}
// 제산 함수를 사용한 해싱 함수
int hash_function2(char *key) {
// 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
return 5 - transform1(key) % TABLE_SIZE;
}
// 선형 조사법을 이용하여 테이블에 키를 삽입하고, 테이블이 가득 찬 경우는 종료
void hash_1p_add(element item, element ht[]) {
int i, hash_value;
hash_value = i = hash_function(item.key);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색 키가 중복되었습니다.\n");
return;
}
i = (i + 1) % TABLE_SIZE;
if (i == hash_value) {
fprintf(stderr, "테이블이 가득찼습니다.\n");
return;
}
}
ht[i] = item;
}
// 선형 조사법을 이용하여 테이블에 저장된 키를 검색
void hash_1p_search(element item, element ht[]) {
int i, hash_value;
hash_value = i = hash_function(item.key);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색성공: 위치 = %d\n", i);
return;
}
i = (i + 1) % TABLE_SIZE;
if (i == hash_value) {
fprintf(stderr, "찾는 값이 테이블에 없음. \n");
return;
}
}
fprintf(stderr, "찾는 값이 테이블에 없음. \n");
}
// 해싱 테이블의 내용을 출력
void hash_1p_print(element ht[]) {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
printf("[%2d] %5s\n", i, ht[i].key);
}
}
// 이차 조사법의 구현
void hash_qp_add(element item, element ht[]) {
int i, hash_value, inc = 0;
hash_value = i = hash_function(item.key);
// printf("hash_address=%d\n", i);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색 키가 중복되었습니다. \n");
exit(1);
}
i = (hash_value + inc*inc) % TABLE_SIZE;
inc = inc + 1;
if (i == hash_value) {
fprintf(stderr, "테이블이 가득 찼습니다. \n");
exit(1);
}
}
ht[i] = item;
}
// 이중 해싱법의 구현
void hash_dh_add(element item, element ht[]) {
int i, hash_value, inc = 0;
hash_value = i = hash_function(item.key);
inc = hash_function2(item.key);
while (!empty(ht[i])) {
if (equal(item, ht[i])) {
fprintf(stderr, "탐색 키가 중복되었습니다. \n");
return;
}
i = (i + inc) % TABLE_SIZE;
inc = inc + 1;
if (i == hash_value) {
fprintf(stderr, "테이블이 가득 찼습니다. \n");
exit(1);
}
}
ht[i] = item;
}
// 해싱 테이블을 사용한 예제
void main() {
element tmp;
int op;
while (1) {
printf("원하는 연산을 입력하시오 (0=입력, 1=탐색, 2=종료)=");
scanf("%d", &op);
if (op == 2) break;
printf("키를 입력하시오=");
scanf("%s", tmp.key);
if (op == 0) {
hash_1p_add(tmp, hash_table);
}
else if (op == 1) {
hash_1p_search(tmp, hash_table);
}
hash_1p_print(hash_table);
}
}
(2) 체이닝
- 선형 조사법이 탐색 시간이 많이 소요되는 이유는 해시 주소가 다른 탐색 키하고도 비교해야 하는 데 있음.
- 만약 해시 주소가 같은 탐색 키들을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것.
- 이러한 리스트는 그 크기를 예측할 수 없으므로 연결 리스트로 구현하는 것이 가장 바람직함.
- 이와 같이 충돌을 해결하는 두 번째 방법은 해시 테이블의 구조를 변경하여 각 버켓이 하나 이상의 값을 저장할 수 있도록 하는 것임.
- 버켓은 여러 가지 방법으로 구현될 수 있음.
- 체이닝(chaining) : 오버플로우 문제를 연결 리스트로 해결함.
- 즉, 각 버켓에 고정된 슬롯을 할당하는 것이 아니라, 각 버켓에 삽입과 삭제가 용이한 연결 리스트를 할당함.
- 물론 버켓 내에서 원하는 항목을 찾을 때는 연결 리스트를 순차 탐색함.
예) 크기가 7인 해시테이블에 h(k)=k mod 7의 해시 함수를 이용하여 8, 1, 9, 6, 13을 삽입할 때에의 체이닝에 의한 충돌 처리
- 한 가지 결정해야 할 것은 연결 리스트의 어디에다 새로운 항목을 삽입하느냐 하는 것.
- 만약 탐색 키들의 중복을 허용한다면 연결 리스트의 처음에다 삽입하는 것이 가장 능률적임.
- 만약 중복이 허용되지 않는다면 연결 리스트를 처음부터 탐색하여야 하므로 어차피 연결 리스트의 뒤로 가야 하고 여기에다 삽입하는 것이 자연스러움.
- 체이닝 구현 프로그램
// 체이닝 구현 프로그램
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define KEY_SIZE 10 // 탐색 키의 최대 길이
#define TABLE_SIZE 13 // 해싱 테이블의 크기 = 소수
#define equal(e1, e2) (!strcmp(e1.key, e2.key))
typedef struct {
char key[KEY_SIZE];
// 다른 필요한 필드들
} element;
typedef struct ListNode {
element item;
struct ListNode *link;
} ListNode;
ListNode *hash_table[TABLE_SIZE];
// 문자로 된 탐색 키를 숫자로 반환
int transform(char *key) {
int number = 0;
while (*key) { // 간단한 덧셈 방식 사용 자연수 생성
number += *key++;
}
return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char *key) {
return transform(key) % TABLE_SIZE;
}
// 체이닝을 이용하여 테이블에 키를 삽입
void hash_chain_add(element item, ListNode *ht[]) {
int hash_value = hash_function(item.key);
ListNode *ptr; // 새로운 노드
ListNode *node_before = NULL; // 이전 노드
ListNode *node = ht[hash_value]; // 현재 노드
for (; node; node_before = node, node = node->link) {
if (equal(node->item, item)) {
fprintf(stderr, "이미 탐색 키가 저장되어 있음. \n");
return;
}
}
ptr = (ListNode *)malloc(sizeof(ListNode));
ptr->item = item;
ptr->link = NULL;
if (node_before) { // 기존의 연결 리스트가 있으면
node_before->link = ptr;
}
else { // 기존의 연결 리스트가 없으면
ht[hash_value] = ptr;
}
}
// 체이닝을 이용하여 테이블에 저장된 키를 탐색
void hash_chain_find(element item, ListNode *ht[]) {
ListNode *node;
int hash_value = hash_function(item.key);
for (node = ht[hash_value]; node; node = node->link) {
if (equal(node->item, item)) {
printf("키를 찾았음. \n");
return;
}
}
printf("키를 찾지 못했음. \n");
}
// 해싱 테이블의 내용을 출력
void hash_chain_print(ListNode *ht[]) {
struct ListNode *node;
int i;
for (i = 0; i<TABLE_SIZE; i++) {
printf("[%d]->", i);
for (node = ht[i]; node; node = node->link) {
printf("%s->", node->item.key);
}
printf("\n");
}
}
// 해싱 테이블을 사용한 예제
void main() {
element tmp;
int op;
while (1) {
printf("원하는 연산을 입력하시오(0=입력, 1=탐색, 2=종료)=");
scanf("%d", &op);
if (op == 2) break;
printf("키를 입력하시오=");
scanf("%s", tmp.key);
if (op == 0) {
hash_chain_add(tmp, hash_table);
}
else if (op == 1) {
hash_chain_find(tmp, hash_table);
}
hash_chain_print(hash_table);
}
}
- 체이닝에서 항목을 탐색하거나 삽입하고자 하면 키 값의 버켓에 해당하는 연결 리스트에서 독립적으로 탐색이나 삽입이 이루어짐.
- 체이닝은 해시 테이블을 연결 리스트로 구성하므로 필요한 만큼의 메모리만 사용하게 되어 공간적 사용 효율이 매우 우수함.
- 또한 오버플로우가 발생할 경우에도 해당 버켓에 할당된 연결 리스트만 처리하게 되므로 수행 시간 면에서도 매우 효율적임.
[해싱의 성능 분석]
- 해싱에서 가장 중요한 연산은 탐색 연산. -> 해시 테이블에 자료를 추가하거나 자료를 꺼내거나 자료를 삭제하는 연산들은 모두 탐색 연산을 사용하게 됨.
- 탐색 연산은 2가지 중의 하나임. -> 성공적인 탐색과 실패한 탐색의 2가지로 나누어 생각해야 함.
- 이상적인 해싱의 시간 복잡도는 O(1) (충돌은 전혀 일어나지 않는다는 가정하에서만 가능함.)
- 일반적으로는 충돌이 있다고 가정해야 하고 따라서 해싱 탐색 연산은 O(1)보다는 느려지게 됨.
- 해싱의 성능을 분석하기 위하여 해시 테이블이 얼마나 채워져 있는지를 나타내는 하나의 척도를 정의함.
- 해시 테이블의 적재 밀도(loading density) 또는 적재 배율(loading factor)은 현재 저장된 항목의 개수 n과 해시 테이블의 크기 M의 비율.
- 여기서 α가 0이면 해시 테이블은 비어 있음.
- α의 최댓값은 충돌 해결 방법에 따라 달라짐.
(1) 선형 조사법
- 선형 조사법에서는 해시 테이블이 가득 찬다면 각 버켓당 하나의 항목이 저장될 것이기 때문에 1이 됨.
- 체이닝에서는 저장할 수 있는 항목의 수가 해시 테이블의 크기를 넘어설 수 있기 때문에 α는 최댓값을 가지지 않음.
- 선형 조사법에서는 해시 테이블이 채워지면 충돌이 더 자주 일어남.
- 탐색을 위한 비교 연산의 개수는 다음과 같음,
(2) 체이닝
- 체이닝에서는 α가 항목의 개수를 연결 리스트의 개수로 나눈 것이 됨.
- 즉, α는 평균적으로 하나의 연결 리스트당 몇 개의 항목을 가지고 있느냐가 됨.
- 실패하는 탐색을 생각해보면, 찾고자 하는 위치에 연결 리스트가 비어 있다면 O(1)의 시간이 걸림.
- 그러나 평균적인 경우, α만큼의 항목을 탐색해야 함.
- 성공적인 탐색인 경우에는 항상 연결 리스트에 항목이 존재함. -> 평균적으로 α/2의 항목을 비교하여야 하고, 테이블에 존재하는 포인터까지 계산에 넣는다면 1+α/2
- 각 알고리즘에 따른 평균 버켓 접근 수
α = n / M |
.50 |
.70 |
.90 |
.95 |
||||
해싱 함수 |
체인 |
선형조사 |
체인 |
선형조사 |
체인 |
선형조사 |
체인 |
선형조사 |
중간 제곱 |
1.26 |
1.73 |
1.40 |
9.75 |
1.45 |
37.14 |
1.47 |
37.53 |
제산 |
1.19 |
4.52 |
1.31 |
7.20 |
1.38 |
22.42 |
1.41 |
25.79 |
이동 폴딩 |
1.33 |
21.75 |
1.48 |
65.10 |
1.40 |
77.01 |
1.51 |
118.57 |
경제 폴딩 |
1.39 |
22.97 |
1.57 |
48.70 |
1.55 |
69.63 |
1.55 |
97.56 |
숫자 분석 |
1.35 |
4.55 |
1.49 |
30.62 |
1.52 |
89.20 |
1.52 |
125.59 |
이론적 |
1.25 |
1.50 |
1.37 |
2.50 |
1.45 |
5.50 |
1.45 |
10.50 |
(V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조)(V.Lum, P.Yuen, M.Dodd, CACM, 1971, Vol.14, No.4 참조)
<정리>
- 선형 조사법은 적재 밀도를 0.5 이하로 유지해야 함.
- 이차 조사법과 이중 해싱법에서는 적재 밀도를 0.7 이하로 유지시키는 것이 좋음.
- 선형 조사법은 테이블의 크기에 따라 저장할 수 있는 요소들의 개수에 자연적으로 제한이 가해지게 됨.
- 그러나 선형 조사법은 적재 밀도가 작은 경우에는 이차 조사법이나 이중 해싱보다 효율적일 수 있음.
- 체이닝은 적재 밀도에 비례하는 성능을 보임.
- 성능을 저하시키지 않고 얼마든지 저장할 수 있는 요소의 수를 늘릴 수 있다는 것이 장점.
- 링크를 위한 메모리 낭비 문제는 저장되는 자료의 크기에 따라 달라짐.
- 배열을 이용하는 이진 탐색과 해싱을 비교하여보면 해싱이 일반적으로 빠름.
- 또한 삽입이 어려운 이진 탐색과는 달리 해싱은 삽입이 쉬움.
- 해싱을 이진 탐색 트리와 비교하여보면, 이진 탐색 트리는 현재 값보다 다음으로 큰 값이나 다음으로 작은 값을 쉽게 찾을 수 있는 장점이 있음.
- 또한 이진 탐색 트리에서는 값의 크기순으로 순회하는 것이 쉬움.
- 반면, 해싱은 그야말로 순서가 없음.
- 또한 해시 테이블의 크기를 얼마만큼 할당해야 되는지가 불명확함.
- 또한 해싱은 최악의 시간 복잡도는 아주 나쁨. 최악의 경우는 모든 값이 하나의 버켓으로 집중되는 것으로서 이 경우 시간 복잡도가 O(n)이 됨.
- 해싱은 사전, 맞춤법 검사기, 방문했던 웹페이지 기록 저장, 투표, 컴파일러의 심볼 테이블 등을 구현하는 데 유용하게 사용할 수 있음.
| 탐색 방법 | 탐색 | 삽입 | 삭제 | |
| 순차 탐색 | O(n) | O(n) | O(n) | |
| 이진 탐색 | O(log₂n) | O(log₂n+n) | O(log₂n+n) | |
| 이진 탐색 트리 | 균형 트리 | O(log₂n) | O(log₂n) | O(log₂n) |
| 경사 트리 | O(n) | O(n) | O(n) | |
| 해싱 | 최선의 경우 | O(1) | O(1) | O(1) |
| 최악의 경우 | O(n) | O(n) | O(n) | |
내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)
'Computer Science > Data Structure' 카테고리의 다른 글
| [C++] 인접 행렬을 이용하여 그래프 구현하기 (0) | 2021.05.19 |
|---|---|
| [C++] 이진 탐색 트리(Binary Search Tree) (0) | 2021.05.16 |
| [C++] 트리 순회(Tree Traversal) (0) | 2021.05.15 |
| [C] 탐색(Search) (0) | 2017.06.21 |
| [C] 그래프(Graph) (0) | 2017.06.19 |
| [C] 정렬(Sorting) (0) | 2017.06.18 |
| [C] 우선순위 큐(Priority Queue) (0) | 2017.06.17 |
| [C] 트리(Tree) (0) | 2017.06.01 |
