1. 딕셔너리를 순차적으로 저장하면 불편한 점
학번으로 학생을 찾는 것처럼 키와 값을 짝지어 저장하는 자료형을 딕셔너리라고 합니다. 이를 리스트나 연결 리스트에 들어온 순서대로 쌓으면 구조는 단순합니다.
+----------+----------+----------+----------+
| 18: 김 | 25: 이 | 7: 박 | 33: 최 |
+----------+----------+----------+----------+문제는 탐색입니다. 키 33을 찾으려면 앞에서부터 하나씩 비교해야 해서 O(n)입니다. 삭제도 먼저 찾아야 하므로 같습니다. 정렬해 두고 이진 탐색을 하면 조회는 빨라지지만, 이번에는 삽입할 때 자리를 만드느라 O(n)이 듭니다.
원소가 늘어날수록 느려지는 구조인데, 딕셔너리는 원래 조회가 가장 잦은 용도입니다. 여기서 해시 테이블이 나옵니다. 해시 테이블은 삽입, 삭제, 탐색을 평균적으로 매우 빠르게 처리합니다.
2. 키를 인덱스로 바꾸면 된다
배열의 인덱스 접근은 O(1)이었습니다. 키가 그대로 인덱스라면 탐색은 이미 끝난 문제입니다. 문제는 키가 학번, 문자열, 전화번호처럼 인덱스로 쓸 수 없는 값이라는 점입니다.
그래서 특정한 함수를 써서 키를 인덱스로 매핑하고, 그 자리에 저장합니다. 이 함수를 해시 함수라고 하고, 테이블의 각 칸을 슬롯(slot)이라고 합니다. 순서대로 쌓는 대신 규칙에 따라 자리를 정하는 것입니다.
h(k) = k % 7 m = 7 (슬롯 개수)
18 -> 18 % 7 = 4
7 -> 7 % 7 = 0
33 -> 33 % 7 = 5
slot 0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| 7 | | | | 18 | 33 | |
+-----+-----+-----+-----+-----+-----+-----+키를 알면 계산 한 번으로 자리를 알 수 있으므로, 탐색이 곧 계산입니다.
3. 충돌
이 방식에는 곧바로 문제가 따라옵니다. 서로 다른 키가 같은 슬롯으로 갈 수 있습니다.
25 -> 25 % 7 = 4 이미 18이 앉아 있는 자리저장하려는 슬롯에 이미 값이 있는 상황을 충돌(collision)이라고 하고, 이를 처리하는 방법을 충돌 해결 방법(collision resolution method)이라고 합니다.
슬롯이 m개인데 키가 그보다 많으면 충돌은 반드시 생깁니다. 서랍보다 넣을 물건이 많으면 한 서랍에 둘이 들어갈 수밖에 없습니다.
4. 이상적인 해시 함수
충돌이 아예 없고 키와 슬롯이 1대1로 대응하는 함수를 완전 해시 함수(perfect hash function)라고 합니다. 다만 저장할 키 집합을 미리 전부 알아야 만들 수 있어서, 일반적인 상황에서는 비현실적입니다.
현실적인 목표는 충돌을 없애는 것이 아니라 고르게 흩뿌리는 것입니다. 서로 다른 두 키가 충돌할 확률이 1/m이면 슬롯에 완벽히 균등하게 퍼진 것이고, 이것이 이상적인 기준입니다. 확률이 c/m 이하로 유지되면 c-universal 해시 함수라고 합니다.
여기서 확률은 키가 아니라 함수 선택에 대한 것입니다. 해시 함수를 하나로 고정하면 그 함수에 최악인 키 집합이 존재하고, 공격자가 그런 키만 골라 넣으면 모두 한 슬롯에 몰립니다. 함수의 모음에서 하나를 임의로 골라 쓰면 그런 최악을 피할 수 있습니다.
5. 자주 쓰이는 해시 함수들
| 방식 | 아이디어 |
|---|---|
| division | 키를 m으로 나눈 나머지. m을 소수로 잡음 |
| multiplication | 키에 상수를 곱한 뒤 소수부만 취해 m배 |
| folding | 키를 여러 조각으로 잘라 더함 |
| extraction | 키에서 일부 자릿수만 뽑아 씀 |
| additive | 문자 코드 값을 모두 더함 |
| rotating | 더하면서 비트를 회전시켜 섞음 |
각 방식의 세부는 보강입니다. 흐름만 보면, 나누거나 곱해서 섞는 쪽에서 시작해 긴 키를 다루려고 자르고 더하는 방식이 나오고, 단순히 더하기만 하면 잘 섞이지 않아 비트를 돌리는 방식이 붙습니다.
6. 좋은 해시 함수의 조건
좋은 해시 함수의 조건은 두 가지입니다. 충돌이 적을 것(less collision), 계산이 빠를 것(fast computation). 그런데 이 둘은 일종의 트레이드오프입니다.
잘 섞으려면 연산을 더 해야 하고, 계산을 줄이면 분포가 나빠집니다. 조회할 때마다 해시 함수를 호출하므로, 함수가 느리면 충돌을 줄여서 번 시간을 계산으로 다시 까먹습니다.
7. 시간복잡도
| 연산 | 순차 저장 평균 | 순차 저장 최악 | 해시 테이블 평균 | 해시 테이블 최악 |
|---|---|---|---|---|
| 탐색 | O(n) | O(n) | O(1) | O(n) |
| 삽입 | O(1) | O(n) | O(1) | O(n) |
| 삭제 | O(n) | O(n) | O(1) | O(n) |
해시 테이블의 최악 O(n)은 모든 키가 한 슬롯에 몰린 경우입니다. 그래서 해시 테이블의 성능은 해시 함수와 충돌 해결 방법에 달려 있습니다.
