해시 테이블 (Hash Table) 알아보기
해시 테이블(hash table)에 대해 알아보기 전에 Direct address table에 대해 알아보도록 하겠습니다.
Direct Address Table
Direct address table은 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다.
Direct address table은 키 k가 테이블 slot T[k]에 저장되기 때문에 테이블의 크기는 전체 키(U) 개수가 됩니다.
위 특징 때문에 direct address table은 중복 키가 없고, 테이블의 크기가 작은 경우에 사용할 수 있습니다.
구현 방법
- 전체 키 집합(U = {0,1 ... ,9})의 크기만 한 테이블(T)을 배열로 만듭니다.
- 실제 사용하는 키 집합(K = {2,3,5,7})을 slot T[k]에 저장합니다.
(T[k]에 저장된 값은 key-value 또는 key-value를 가리키는 주소입니다. 상황에 따라 value만 저장될 수 있습니다. key는 배열의 index로 표현되기 때문입니다.) - 사용하지 않는 키는 공백 처리합니다.(NIL)
기본 연산은 다음과 같습니다.
DIRECT-ADDRESS-SEARCH(T,k)
- return T[k]
DIRECT-ADDRESS-INSERT(T,x)
- T[x.key] = x
DIRECT-ADDRESS-DELETE(T,x)
- T[x.key] = NIL
key값을 배열 index로 사용하기 때문에 direct로 value에 접근할 수 있어 기본 연산의 시간 복잡도는 O(1)입니다.
Direct address table은 연산속도가 매우 빠릅니다 하지만 다음과 같은 제한사항이 있습니다.
제한사항
- 전체 키(U)를 예측해야 테이블 사이즈를 정할 수 있습니다.
- 전체 키(U)가 크다면 테이블에 저장하는 것은 비실용적이거나 불가능할 수 있습니다.
- 전체 키(U) 대비 사용하는 키(K)가 훨씬 적을 경우 메모리 공간을 낭비하게 됩니다.
이러한 제한사항을 개선한 자료구조가 해시 테이블(hash table)입니다.
해시 테이블(Hash Table)
해시 테이블(Hash table)이란 검색하고자 하는 키값을 입력받아서 해쉬 함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다.
direct address table은 key k가 slot k에 저장되지만 hash table은 해싱(hasing)을 통해 key k가 slot h(k)에 들어가게 됩니다.
해쉬 함수(h)는 전체 키 U를 해시 테이블 T[0.. m-1]의 slot에 맵핑시키기 위해 사용됩니다.
h: U → {0,1, ..., m-1}
이것을 키 k가 slot h(k)에 해시되었다고 말합니다. h(k)는 키 k에 해시 값이라고 합니다.
해시 테이블은 해시함수를 사용하여 배열 인덱스의 범위를 줄일 수 있기 때문에 전체 키(U)를 m사이즈의 테이블로 처리가 가능해지고 그만큼 테이블 사이즈도 direct address table보다 줄어들게 됩니다.
- table size
- direct address table : U
- hash table : m ( < U)
충돌 (Collision)
해시 테이블 크기보다 키의 개수가 많기 때문에 두 개의 키가 동일한 slot에 해시될 수 있습니다. 이것을 해시 충돌(hash collison)이라고 합니다.
위 hash table 그림에서 k2, k5가 동일 slot에 맵핑되어 충돌(collision)이 일어난 것을 볼 수 있습니다.
충돌에 대해서 이해하기 위해선 먼저 적재율(Load Factor)을 이해해야 합니다.
적재율이란 해시 테이블의 크기 대비, 키의 개수를 말합니다.
- 적재율(\(\alpha\)) = n/m (n: 키의 개수, m: 테이블의 크기)
Direct address table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 됩니다.
해시 테이블은 테이블의 크기가 키의 개수보다 작기 때문에 적재율이 1이 초과합니다. 그렇기 때문에 해시 충돌이 발생할 수밖에 없습니다.
만약, 충돌이 발생하지 않는다면 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 수행되지만 충돌이 발생할 경우 충돌에 대한 추가 작업이 필요하게 됩니다.
충돌은 해시 테이블 연산 효율을 떨어트리기 때문에 충돌을 줄이는 것이 해시 테이블의 핵심입니다.
해시 함수를 개선하여 충돌을 줄일 수 있습니다.
해시 함수 (Hash function)
해시 함수 (Hash function)는 임의의 길이의 키값을 고정된 길이의 해시로 변환해주는 맵핑 함수입니다.
Key
- 해쉬 함수에서 key는 자연수로 가정합니다. (N={0,1,2,...})
- 만약 자연수가 아닌 character나 string의 형태라면 자연수 형태로 변형하여 사용합니다.
Hash
- 해시 함수를 통해 작아진 값을 해시(hash), 해시 값(hash value), 해시 코드(hash code)라고 합니다.
- 해시 테이블의 버킷을 가리키는 주소로 사용됩니다.
Hasing
- 키 값을 해시함수를 통해 해시로 변환해주는 작업을 해싱(Hasing)이라고 합니다.
어떤 해시 함수를 사용하느냐에 따라 해시 검색의 성능이 결정되기 때문에 좋은 해시 함수를 사용해야 합니다.
좋은 해시 함수의 조건은 다음과 같습니다.
- 키를 고르게 분포시킬 수 있어야 함.
- 충돌 발생 빈도가 적어야 함.
- 빠른 연산.
해시 함수에는 다양한 알고리즘이 있습니다.
나눗셈 방법 (Division method)
나눗셈 방법(Division method)은 나머지 연산을 이용하여 해시를 만드는 방법입니다.
검색키 k를 해시 테이블의 크기 m으로 나눈 나머지를 해시로 사용합니다.
- h(k) = k mod m (k: key, m: table size)
ex)
m : 7 , k : 124
h(k) = 124 % 7 = 5해시테이블 크기(m)에 따라 충돌 빈도가 달라지기 때문에 효율적인 m의 크기를 정해야 합니다.
효율적인 m 선택 방법
- m=\(2^p\) 인 경우는 피합니다
- m =\(2^p\)가 되면 해시 함수 h(k)는 키 k의 하위 p비트가 됩니다.
- 해쉬 함수가 key값 전체에 따라 바뀌지 않고 하위 p 비트에만 영향을 받습니다. 하위 p비트가 고르게 나온다면 괜찮겠지만 대부분 그렇지 않기 때문에 m=\(2^p\)인 경우는 피해야 합니다.
하위 p(=4)비트에 영향을 받는 것을 볼 수 있음
- m =\(2^p\)에 너무 가깝지 않은 소수를 선택합니다.
- 예를 들면 키의 수가 2000인 경우 테이블 크기(m)는 701로 하는 게 좋습니다.
접기 방법 (Fording Method)
접기(Fording)는 검색 키를 분해하고 조합하여 해시를 만드는 방법입니다.
접기에는 이동 접기(Shift folding)와 경계 접기(Boundary folding)가 있습니다.
이동 접기 (Shift folding)
이동 접기 과정은 다음과 같습니다.
- 해시 테이블 크기의 자릿수로 키를 분해한다.
- 분해된 키들을 더한다.
- 더한 값이 테이블 크기를 초과한다면 초과한 자릿수는 버린다.
경계 접기 (Boundary fording)
경계 접기 과정은 다음과 같습니다.
- 해시테이블 크기의 자릿수로 키를 분해한다.
- 나누어진 각 부분의 경계 부분 값을 역으로 정렬한다.
- 분해된 키들을 더한다.
- 더한 값이 테이블 자릿수를 초과한다면 초과한 자릿수는 버린다.
중간 제곱 법(Mid-Square Method)
키 값을 제곱한 후 결과 값의 중간 부분에 있는 몇 비트만 선택하여 해시로 사용하는 방법입니다.
테이블 크기의 자릿수만큼 중간값을 가져옵니다.
숫자 분석 방법
키 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합하게 조합하여 사용하는 방법입니다.
학번을 가지고 해시를 구하는 경우
| 학번 | 해시 값 |
| 2021-1023 | 1023 |
| 2021-1024 | 1024 |
| 2021-1031 | 1031 |
| 2021-1052 | 1052 |
앞에 4자리(2021)는 입학 연도이고 뒤에 4자리는 학과 번호 2자리, 개인번호 2자리입니다.
처음 4자리는 입학 연도이기 때문에 하나의 값으로 편중되어있고 뒤에 4자리는 학과 및 개인번호이기 때문에 고르게 분포되어 있습니다.
그렇기 때문에 고르게 분포되어있는 뒤에 4자리 수로 해시 값을 사용합니다.
아무리 좋은 해시함수를 사용하더라도 전체 키 (U)보다 테이블의 크기(m)가 작기 때문에 충돌을 완전히 피할 수는 없습니다.
따라서 충돌을 해결하기 위한 방법은 여전히 필요합니다.
Collision Handling
충돌 해결 방법으로 두 가지가 있습니다.
- 체이닝 (Chaining)
- 개방 주소법 (Open Addressing)
체이닝 (Separate Chaining)
체이닝은 충돌이 일어났을 때 동일 slot에 연결 리스트로 저장하는 방법입니다.
각 해시 테이블 slot T[j]는 해시 값이 j인 모든 키를 연결 리스트로 저장하여 충돌을 해결합니다.
- h(k1) = h(k4), h(k2)=h(k5)=h(k6)
체이닝 기본 연산은 다음과 같습니다.
CHAINED-HASH-INSERT(T,x)
- T[h(x.key)] 리스트에 x를 삽입합니다.
CHAINED-HASH-SEARCH(T, k)
- T[h(k)] 리스트에 키 k를 찾습니다.
CHAINED-HASH-DELETE(T,x)
- T[h(x.key)] 리스트에 x를 삭제합니다.
다음은 체이닝 동작 예입니다.
장점
- 구현이 단순합니다.
- 연결 리스트로 저장하기 때문에 테이블이 가득 차지 않습니다.
- 해시 함수 및 적재율(load factor)에 영향을 덜 받습니다.
- 키의 삽입 또는 삭제 횟수와 빈도를 알 수 없을 때 주로 사용됩니다.
단점
- 연결 리스트를 사용해 키를 저장하므로 캐시 성능은 떨어지게 됩니다.
- 사용하지 않는 slot이 생길 수 있어 공간 낭비가 발생하게 됩니다.
- 한 slot에 계속해서 저장된다면 체인이 길어져 최악의 경우 검색 시간이 O(n)이 될 수 있습니다.
- 링크 주소를 저장하기 위해 추가 메모리 공간이 필요합니다.
시간 복잡도 (Time complexity)
- 최악의 경우
- O(n)
- 모든 key가 하나의 slot으로 해싱되는 경우 길이가 n인 연결 리스트가 생성될 수 있기 때문입니다.
- 평균 수행 시간
- O(1+\(\alpha\)) (\(\alpha\) = 적재율(Load factor))
- 테이블 slot에 접근하기 위해 O(1)의 시간이 걸리고 해당 슬롯에 있는 리스트를 검색하기 위해 O(\(\alpha\))의 시간이 걸리기 때문입니다.
개방 주소법 (Open Addressing)
개방 주소법(Open Addressing)이란 충돌이 일어난 키 값을 비어 있는 다른 주소를 찾아 저장하는 방법입니다.
모든 요소를 해시 테이블 자체에 저장하기 때문에 테이블의 크기는 키의 개수보다 크거나 같아야 합니다.
기본 연산은 다음과 같습니다.
- insert(key)
- 빈 슬롯을 찾을 때까지 계속 조사(probing)하고 빈 슬롯을 찾으면 키를 삽입합니다.
- search(key)
- 슬롯의 키가 찾고자 하는 키와 동일하거나 빈 슬롯에 도달할 때까지 계속 조사(probing)합니다.
- delete(key)
- 삭제된 키의 슬롯에 삭제 표시를 합니다.
- 삽입은 삭제된 슬롯에 삽입할 수 있지만 검색은 삭제된 슬롯에서 멈추지 않습니다.
개방 주소법에는 다음과 같은 방식이 있습니다.
- 선형 탐색 (Linear Probing)
- 제곱 탐색 (Quadratic Probing)
- 이중 해시 (Double Hashing)
선형 탐색 (Linear probing)
선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈 slot을 찾는 방식입니다.
h(k)→ 충돌 → h(k)+1→충돌→ h(k)+2→...
h`: U→{0,1,..., m-1} 이라면 선형 탐색에서 사용하는 해시함수는 다음과 같습니다.
- h(k, i) = (h`(k) + i) mod m ( i=0,1...m-1 , m : table size)
Insert
충돌이 발생할 경우 empty or deleted slot을 발견할 때까지 탐색을 진행합니다.
empty or deleted slot을 발견하면 그곳에 key를 삽입합니다.
Delete
삭제하기 위한 slot을 찾고 slot의 상태를 deleted로 변경합니다.
만약 deleted표시를 하지 않고 삭제만 한다면 search를 못하는 경우가 발생할 수 있습니다.
- 예를 들어 아래 그림에서 8번 slot을 empty 상태로만 둔다면 62 키 값은 찾을 수 없게 됩니다.
Search
검색은 키를 찾거나 빈 slot에 도달할 때까지 탐색을 계속합니다.
중간에 삭제된 slot이 있어도 탐색을 멈추지 않습니다.
장점
- 구현이 쉽습니다.
단점
- primary clustering 문제가 있습니다.
- 연속된 데이터 그룹이 생기는 현상을 클러스터링(clustering)이라고 합니다. 클러스터링은 탐색 시간을 오래 걸리게 하여 해싱 효율을 떨어트리게 됩니다.
- 탐색 간격을 1 이외에 다른 값으로 정할 수 있는데 테이블의 크기 값과 서로소 관계에 있는 소수로 정해야 클러스터링 현상을 줄일 수 있습니다.
Primary clustering
제곱 탐색 (Quadratic Probing)
충돌이 발생하면 2차 함수 꼴로 증가하면서 빈 slot을 찾는 방식입니다.
h(k)→ 충돌 → h(k)+\(1^2\)→충돌→ h(k)+\(2^2\)→충돌→h(k)+\(3^2\)→...
h`: U→{0,1,..., m-1} 이라면 제곱 탐색에서 사용하는 해시함수는 다음과 같습니다.
- h(k,i) = (h(k)+c1i+c2\(i^2\))mod m (h:보조 해시 함수, c1, c2: 0이 아닌 상수, i=0,1...m-1 )
Insert
delete, search는 선형 프로빙과 비슷하기 때문에 생략하겠습니다.
장점
- 선형 탐색보다 클러스터링이 적게 일어남.
단점
- Secondary clustering 문제가 있음.
- 만약 두 key의 처음 probe 값이 동일하다면 빈 slot을 찾는 과정이 동일하므로 같은 slot을 탐색합니다.
- 즉 처음 충돌한 위치가 같다면 다음 충돌할 위치에서도 반복적으로 계속 충돌이 나게 됩니다.
Secondary clustering
이중 해시 (Double Hashing)
이중 해싱은 탐사할 해시값의 규칙성을 제거해 clustering을 방지하는 기법입니다.
두 개의 해시 함수를 준비해서 하나(h1)는 최초의 해시값을 얻을 때 사용하고 다른 하나(h2)는 해시 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용합니다.
h1(k)→ 충돌 → h1(k)+1*h2(k)→충돌→ h1(k)+2*h2(k)→충돌→h1(k)+3*h2(k)→...
h1,h2: U→{0,1,..., m-1} 이라면 이중 해시에서 사용하는 해시함수는 다음과 같습니다
- h(k, i)=(h1(k)+i*h2(k)) mod m (h2(k) ≠ 0, h2≠h1)
탐색 과정
- 처음 탐색하는 위치는 T[h1(k)]입니다.
- 그다음부터는 h2(k) 만큼 이동하면서 탐색합니다.
- 즉 충돌이 발생했을 때, 이동하는 거리가 hash 함수에 의해 계산되고 무작위로 빈 slot을 찾게 되어 클러스터링(clustering)을 피할 수 있게 됩니다.
Insert
delete, search는 선형 프로빙과 비슷하기 때문에 생략하겠습니다.
주의점
h2(k) 함수는 해쉬 테이블의 크기 m과 서로소 관계여야 합니다.
- m을 2의 지수승으로 하고 h2가 항상 홀수가 되도록 한다.
- m을 소수로 하고 h2를 m보다 작은 양수로 정한다.
장점
- 클러스터링이 다른 두 방식보다 적게 발생함.
단점
- 연산이 다른 두 방식에 비해 오래 걸림
시간 복잡도 (Time complexity)
open addressing의 적재율(Load factor)은 1 이하입니다. 배열의 크기가 한정되어 있기 때문입니다.
open addressing에서 계산 복잡성은 탐사(probing) 횟수에 비례합니다. 따라서 search 횟수로 시간 복잡도를 나타낼 수 있습니다.
적재율을 \(\alpha\)라고 했을 때 선형 탐색(Linear probing)에서 시간 복잡도는 다음과 같습니다.
- successful search : \(1/2 * {1+1/(1-\alpha)}\)
- unsuccessful search : \(1/2 * {1+1/(1-\alpha)^2}\)
선형 탐색에서 적재율이 0.5 이상이 되면 unsuceessful search 횟수는 급격히 늘어나게 됩니다.
따라서 적재율이 0.5 이상이 되면 해시 테이블의 크기를 늘리는 등의 작업으로 적재율을 0.5 미만이 되도록 해야 합니다.
제곱 탐색, 이중 해시도 적재율을 0.5 미만으로 유지하는게 좋습니다.
