Lecture 4: Hashing
이 전 강의에서 배운 Array, Sorted Array의 시간 복잡도를 아래처럼 다뤄보았다.
Idea! Want faster search and dynamic operations.
아이디어! 더 빠른 검색과 동적 연산을 하고 싶다.
이 전에 배운 자료구조 (Sorted Array)에서 find(k) 같은 검색 연산은 보통 O(log n) 시간에 동작한다.
Can we find(k) faster than Θ(log n)?
아이템 탐색(Search)인 find(k) 연산을 Θ(log n)보다 더 빠르게 할 수는 없을까?
Answer is no (lower bound)! (But actually, yes...!?)
답은 아니다 (최소한), 하지만 사실, 할 수 있다
비교 기반에서는 O(log n)보다 빠를 수 없다.
만약 비교 기반을 벗어나 다른 자료구조나 문제 조건이 주어지면
평균적으로 O(1) 또는 O(log log n) 같은 속도를 가지는 연산도 가능하다.
해시 테이블은 평균 O(1)으로 검색이 가능하다
그럼 일단 비교 기반 알고리즘에 대해 알아보고,
이 비교 기반 알고리즘보다 더 빠르게 아이템 검색 가능한 해시에 대해 알아보자.
1. Comparison-based Algorithm 비교 기반 알고리즘
1-1. Comparison Model 비교 모델
In this model, assume algorithm can only differentiate items via comparisons
이 모델에서는 알고리즘이 다른 아이템들을 비교 연산으로만 구별할 수 있다고 가정한다.
즉, 정렬 할 때 두 아이템을 비교해서만 차이를 알 수 있고,
항목의 내부 값이나 다른 정보에는 접근할 수 없다
다시 말하면 배열에서 숫자들끼리 비교할 수는 있지만,
숫자 자체를 직접 들여다볼 수는 없다
예를 들어, 만약 배열A [1, 2, 3] 이 있다면,
비교 기반 모델이 작동할 때는
허락된 건 비교하는 이런 질문들 뿐이다.
- A[0] < A[1]? - A[0]에 있는 값이 A[1]에 있는 값 보다 작아? 값은 못보고 참(True) 또는 거짓(False) 리턴 결과만 받음
- A[2] > A[1]?
- A[0] == A[2]?
3이라는 아이템을 A[2] 이렇게 인덱스를 이용해 꺼내서 보거나
if A[2] == 3 이런 식으로 숫자의 실제 값을 보지 않는다.
해시 테이블이나 radix sort 같은 알고리즘은
숫자 값의 내부 구조를 직접 보고 활용하기 때문에
비교 모델을 쓰지 않고 더 빠르다
Comparable items: black boxes only supporting comparisons between pairs
비교 가능한 항목들: 두 개씩 짝지어서 비교만 지원하는 블랙박스들
블랙박스(black box): 항목 안의 내용은 알 수 없고, 두 항목을 주면 비교 결과만 알려주는 역할
예: compare(A, B) → True or False
Comparisons are <, ≤, >, ≥, =, ≠ , outputs are binary: True or False
비교 연산은 <, ≤, >, ≥, =, ≠ 을 사용하며, 출력은 이진값 (참 또는 거짓)이다.
즉, 연산 결과는 “맞다” 또는 “틀리다”로만 나오고,
숫자 계산 결과 같은 건 받을 수 없다
비교의 종류는 다양하지만 결국 yes/no 질문이다
Goal: Store a set of n comparable items, support find(k) operation
목표: n개의 비교할 아이템들을 저장하고, find(k) 연산을 지원하는 것.
우리는 n개의 아이템을 저장할 자료구조를 만들고, 그 안에 있는 특정 키 k를 찾는 find(k) 연산을 할 수 있어야 함.
Running time is lower bounded by # comparisons performed, so count comparisons!
실행 시간은 수행된 비교의 개수로 하한이 결정되므로, 비교 횟수를 세어라!
이 모델에서는 비교 외에는 아이템을 구별할 방법이 없으므로,
전체 알고리즘의 실행 시간은 결국 비교 연산 횟수로 측정된다
그래서 비교 알고리즘 분석할 때는 총 몇 번 비교를 하였는가?로 성능을 따진다.
1-2. Decision Tree 결정 트리
결정 트리는 비교 모델에서 실행되는 알고리즘의 동작 과정을 보기 편하게 시각화한 도구이다
비교 모델로 짜인 알고리즘을 트리로 나타내면 결정 트리가 된다
- 각 노드 → 하나의 비교 연산 (예: A[i] < A[j]?)
- 각 가지 → 그 비교의 True/False 결과로 가는 경로
- 리프 노드 → 최종 결과 (예: 정렬된 순서, 탐색 결과)
Any algorithm can be viewed as a decision tree of operations performed
모든 알고리즘에서 실행되는 연산들은 결정 트리로 나타낼 수 있다
비교 기반 알고리즘에서도
- 어떤 비교를 하고
- 그 결과에 따라 다음 어디로 갈지 정하고
- 최종적으로 답을 찾아가는
이 과정을 트리 구조로 그릴 수 있다
For a comparison algorithm, the decision tree is binary (draw example)
비교 기반 알고리즘에서 이 결정 트리는 이진 트리를 쓴다
- 루트에서 A[0] < A[1]? 비교
- True면 왼쪽 가지, False면 오른쪽 가지
- 다음 노드에서 또 다른 비교…
- 이렇게 계속 내려가서 최종 답을 찾게 된다
A leaf represents algorithm termination, resulting in an algorithm output
트리의 리프(leaf), 즉 끝 노드는 알고리즘이 종료해서 최종 아웃풋을 내는 자리이다
A root-to-leaf path represents an execution of the algorithm on some input
루트에서 리프까지 내려가는 하나의 경로는 특정한 입력을 처리할 때 알고리즘이 수행하는 실행 과정을 나타낸다
즉, 어떤 입력값에서
- 어떤 비교를 거쳤고
- 그때마다 True/False로 어디로 내려갔는지
- 마지막에 어떤 결과를 냈는지
이걸 한 줄로 쭉 그린 게 루트-리프 경로이다
Need at least one leaf for each algorithm output, so search requires ≥ n + 1 leaves
만약 우리가 탐색(search)을 한다면 가능한 아웃풋(결과)마다 최소 하나의 리프가 더 필요하다
예를 들어, 길이가 n인 배열에서 “어떤 값이 있나?” 찾으려면 적어도 n + 1개의 리프가 필요하다
왜냐하면 n개의 값이 각각 있을 수 있는 경우 + 아무 값도 없는 경우 최소한 그 모든 경우를 구분할 수 있어야 하니까
이게 결국 비교 기반 탐색의 하한(lower bound) 증명으로 연결된다
1-3. Comparison Search Lower Bound
What is worst-case running time of a comparison search algorithm?
비교 기반 탐색 알고리즘의 최악 실행 시간은 얼마인가?
예: 정렬된 배열에서 이진 탐색 같은 걸 쓸 때, 최악의 경우 걸리는 시간은?
앞에서 언급했듯이 보통 몇 번 비교하는지로 측정한다
running time ≥ # comparisons ≥ max length of any root-to-leaf path ≥ height of tree
실행 시간 ≥ 비교 횟수 ≥ 루트에서 리프까지의 최장 경로 ≥ 트리 높이
결정 트리에서
- 루트부터 리프까지 내려가야 답을 구함.
- 최악의 경우 가장 긴 경로를 따라가야 하므로,
- 실행 시간은 트리 높이보다 클 수밖에 없다
What is minimum height of any binary tree on ≥ n nodes?
노드가 최소 n개인 이진 트리의 최소 높이는 얼마인가?
노드 개수가 n개 이상인 이진 트리를 만들 때, 트리 높이를 최소로 줄이려면 최적 구조가 뭘까?
그리고 그 최적 구조일 때 최소 높이는 얼마일까?
예: n = 7
우리가 7개의 노드를 가진 이진 트리를 만든다고 가정할 때
이진 트리니까:
- 한 노드는 최대 왼쪽과 오른쪽으로 두 개의 자식을 가질 수 있다
- 트리의 높이는 루트에서 리프까지 가장 긴 경로의 길이를 말한다
트리 높이를 최소로 줄이려면, 노드를 균등하게 채워야 함.
즉, 마지막 줄을 제외하고 다 채우는 완전 이진 트리가 최적이다
최적 이진 트리 - 완전 이진 트리
노드를 가능한 한 넓게 퍼뜨려서 루트에서 리프까지 거리를 최소로 만들
- 총 노드 수: 7
- 높이: 2 (루트에서 리프까지 경로 길이)
비최적 이진 트리
높이 6 (루트에서 리프까지)
높이가 거의 n-1까지 올라간 최악의 구조
Minimum height when binary tree is complete (all rows full except last)
최소 높이는 트리가 완전 이진 트리일 때 달성된다 (마지막 줄 빼고 다 채워짐).
완전 이진 트리가 최적 구조. 모든 레벨이 빽빽히 차 있고 마지막 레벨만 일부 비어 있으면, 높이를 최소화할 수 있다.
all rows full except last 는
- 마지막 줄 제외하고는 다 채워야 한다.
- 마지막 줄만 불완전해도 괜찮지만, 왼쪽부터 순서대로 차 있어야 한다.
예를 살펴보면
- 높이: 2 (루트 → 리프까지 최장 거리)
- 3번째 줄(마지막 줄)은 다 채워졌음 → perfect binary tree (완벽 이진 트리)
- 높이: 2
- 마지막 줄은 왼쪽부터 4, 5, 6까지만 채워짐
- complete binary tree 스타일
마지막 줄이 다 채워질 필요는 없지만, 채우는 순서는 왼쪽부터 채워야 한다
Height ≥ ⌈log(n + 1)⌉ − 1 = Ω(log n), so running time of any comparison sort is Ω(log n)
높이는 ⌈log(n + 1)⌉ − 1 이상 = Ω(log n), 따라서 비교 기반 탐색의 실행 시간은 Ω(log n) 이상
여기선 “sort”라고 적혀있지만 문맥상 search에 초점 맞추고 있다
이진 트리는 한 층 내려갈 때마다 남은 노드 수가 절반으로 줄어든다
완전 이진 트리에서 최대 노드 수 계산하는 법
완전 이진 트리에서 높이 h일 때, 가질 수 있는 최대 노드 수
예시 1 — 높이 h = 0
[1]
- 루트 노드 1개만 있음
- 계산: 2^{0+1} - 1 = 2 - 1 = 1
예시 2 — 높이 h = 1
- 루트와 그 아래 왼쪽, 오른쪽 자식 2개 → 총 3개
- 계산: 2^{1+1} - 1 = 4 - 1 = 3
예시 3 — 높이 h = 2
- 루트 + 2개 + 4개 → 총 7개
- 계산: 2^{2+1} - 1 = 8 - 1 = 7
예시 4 — 높이 h = 3
- 루트 + 2개 + 4개 + 8개 → 총 15개
- 계산: 2^{3+1} - 1 = 16 - 1 = 15
요약표
높이 h 최대 노드 수
| 0 | 1 |
| 1 | 3 |
| 2 | 7 |
| 3 | 15 |
| 4 | 31 |
높이(h) 계산하는 법
일 때 h=⌈log₂ (16)⌉−1=4−1=3
일 때 h=⌈log₂ (8)⌉−1=3−1=2
Sorted arrays achieve this bound! Yay!
정렬된 배열은 이 하한을 달성한다!
정렬된 배열에서 이진 탐색 → log n 시간 → 최적!
More generally, height of tree with Θ(n) leaves and max branching factor b is Ω(log_b n)
일반적으로, Θ(n) 리프와 최대 분기 b를 가진 트리의 높이는 Ω(log_b n)
- 2진 트리 → log₂ n
- 10진 트리 → log₁₀ n
- b진 트리 → log_b n
b 커질수록 높이가 낮아질 수 있다
To get faster, need an operation that allows super-constant ω(1) branching factor. How??
더 빠르게 하려면, 상수보다 큰 (ω(1)) 분기 수를 허용하는 연산이 필요하다. 어떻게?
이진 탐색은 2진 분기 → log₂ n
하지만 더 빠르게 하려면, 동시에 더 많은 분기로 한 번에 찾을 수 있어야 함
예: 해시 테이블, B-트리, 비트 연산 같은 것으로 속도를 높일 수 있다
constant
어떤 숫자가 입력 크기 n에 상관없이 항상 같은 값
branching factor
몇 갈래로 나뉘는 지
branching factor = 2
한 번 비교할 때 두 갈래로 나뉜다
→ 즉 이진 트리 구조
상수보다 크다
2보다 크고 n에 따라 더 커질 수 있음
매번 2개의 경우로 나뉘는 구조는 상수 2
constant branching 이라고도 함
상수보다 크다는 의미는 branching factor가 3, 4, 10, log n 등 입력 크기에 따라 더 커지는 것
즉 2보다 많은 분기를 만들 수 있다
ω(1) (오메가 1)
n이 커질수록 계속 증가하는 것. ex) log n, n
상수는 ω(1) 아님 ex) 1, 0.5, 100 (x)
super-constant ω(1)
상수 2보다 더 큰 값으로 점점 증가하는 것
한 번에 두 갈래(이진 분기)만 하지 말고,
그보다 더 많은 분기, 예를 들어 10갈래, 100갈래로 나누라는 것
2. Direct Access Array
Hash로 가기 전 단계
비교 연산으로 정렬하거나 검색하는 것보다 시간을 더 줄일 수 있다.
가지를 2개만 치는 게 아니라 root 에서 n만큼 쳐버리면 된다
Exploit Word-RAM O(1) time random access indexing! Linear branching factor!
Word-RAM 모델을 사용하면, 배열 인덱스를 통해 O(1) 시간에 랜덤 접근이 가능하다.
이것은 선형적인 분기(branching)를 가능하게 한다.
즉, 특정 인덱스로 바로 접근하므로 탐색 속도가 매우 빠르다.
Idea! Give item unique integer key k in {0, ..., u − 1}, store item in an array at index k
각 아이템마다 0부터 u−1 사이의 고유한 정수 키 k를 부여해서, 배열의 인덱스 k에 그 값을 저장한다.
이러면 찾을 때 그냥 array[k]를 조회하면 끝난다. 매우 빠름
Associate a meaning with each index of array
배열의 각 인덱스는 단순 숫자가 아니라, 의미 있는 "키" 역할을 하도록 설정한다.
예: 이름 “Alice” → key: 4,231 → array[4231] 에 Alice에 대한 정보 저장.
If keys fit in a machine word, i.e. u ≤ 2^w, worst-case O(1) find/dynamic operations! Yay!
키가 컴퓨터에서 다룰 수 있는 하나의 워드 크기(w 비트) 안에 들어간다면 (즉, u ≤ 2^w),
최악의 경우에도 탐색이나 삽입/삭제가 O(1) 시간에 가능하다.
- w: 컴퓨터의 워드 크기 (보통 64비트 또는 32비트)
- u: 키의 전체 가능한 개수 (key universe)
- 2^w: 워드 크기만큼 표현 가능한 최대 값 → 키가 이 범위 내에 있어야 단일 연산(O(1))이 가능
예) 32비트 컴퓨터에서 u = 2^32
- Key가 0부터 4,294,967,295 (약 43억) 사이의 정수라면,
- 각 키는 32비트 워드에 딱 들어간다
- 따라서 배열 인덱스로 바로 접근 가능 (A[k])
- 이 경우, O(1) 시간에 접근 가능
6.006: assume input numbers/strings fit in a word, unless length explicitly parameterized
이 자료구조를 설명하는 MIT 6.006 수업에서는, 숫자나 문자열이 워드 하나에 들어간다고 가정한다. 길이가 명시적으로 매개변수로 주어지지 않는 한. (예외: 문자열 길이를 따로 고려해야 할 경우는 명시적으로 나타냄)
* explicitly: 명시적으로, 분명히, 구체적으로
* parameterized: 매개변수를 사용하는
Anything in computer memory is a binary integer, or use (static) 64-bit address in memory
컴퓨터의 메모리 안에 있는 모든 정보는 결국 이진수 정수 형태이며,
메모리 주소도 일반적으로 64비트 정수로 표현된다.
But space O(u), so really bad if n ≪ u... :(
하지만 이 방식은 전체 공간이 키의 범위 u만큼 필요하다 → O(u)
만약 실제 데이터 수 n이 u보다 훨씬 작다면, 엄청나게 많은 낭비가 생긴다.
Example: if keys are ten-letter names, for one bit per name, requires 26^10 ≈ 17.6 TB space
예를 들어, 키가 영어 10글자로 구성된 이름이라면 가능한 조합이 26¹⁰개.
각 이름당 비트 하나만 써도 약 17.6 테라바이트의 공간이 필요
즉, 대부분 비어있는 어마어마한 공간을 만들게 된다
- 이름 "abcdefghij" → index 0
- 이름 "aaaaaaaaaa" → index 1
- 이름 "zzzzzzzzzz" → index
- 각각 존재 여부만 비트 하나로 저장
- 존재 → 1
- 없음 → 0
이렇게 이름당 비트 하나만 사용한다고 해도
전체 배열의 크기가 17.6TB로 어마어마하게 커진다
감당 불가능 ㅠ
이 이유로 Direct Access Array는 잘 쓰지 않음.
How can we use less space?
공간 낭비를 줄이려면 어떻게 해야 할까?
여기서 해시 테이블 같은 공간 효율적인 자료구조들이 등장한다.
3. 해시
3-1 해시 설명
Idea! If n ≪ u, map keys to a smaller range m = Θ(n) and use smaller direct access array
실제 데이터 수 n이 키의 전체 범위 u보다 훨씬 작을 경우,
직접 u 크기나 되는 메모리를 써서 배열을 미리 만들어 놓으면 공간이 너무 낭비되므로,
key들을 더 작은 범위 m (대략 n과 비슷한 크기) 정도의 메모리를 써서 배열을 만들어 놓고 매핑 한다
즉, m = Θ(n)인 작은 배열에 값을 저장하자는 전략 → 이 것이 해시 테이블
- u: 키의 전체 가능한 개수 (key universe)
Hash function: h(k) : {0, ..., u − 1} → {0, ..., m − 1} (also hash map)
이를 위해 해시 함수(hash function) h(k)를 정의한다.
k는 원래의 큰 키 (0 ~ u−1), 이걸 작은 정수 범위(0 ~ m−1)로 보내는 함수
이 과정을 해시맵(Hash Map) 이라고도 부른다
Direct access array called hash table, h(k) called the hash of key k
우리가 m 크기로 만든 배열을 해시 테이블(hash table) 이라고 부른다.
h(k)는 키 k의 해시(해시값)라고 한다.
이 해시값을 인덱스로 사용해서 해시 테이블에 값을 저장하거나 검색한다.
- k: 원래의 키 (예: 이름, 전화번호 등)
- u: 키의 전체 범위 (엄청 큼)
- m: 해시 테이블 크기 (보통 훨씬 작음)
- h(k): 키 k를 0부터 m-1 사이 숫자로 바꿔주는 함수
* hash function(해시 함수 h(k)): 입력값(예: 문자열, 숫자 등)을 고정된 범위의 정수 값으로 변환해 주는 함수
hash("apple") → 5 배열의 5번째 칸에 저장
hash(12345) → 2 배열의 2번째 칸에 저장
이렇게 표현하기도 함
h(k) : {0, ..., u−1} → {0, ..., m−1}
If m ≪ u, no hash function is injective by pigeonhole principle
만약 m이 u보다 훨씬 작다면, 어떤 해시 함수를 사용하든 모든 키를 서로 다르게 매핑할 수 없다.
(즉, 충돌이 생길 수밖에 없다.)
이것은 비둘기집 원리(pigeonhole principle) 때문이다.
* injective: 일대일 함수(one-to-one function) 를 의미하는 수학 용어
* pigeonhole principle:만약 100마리 비둘기를 10개의 집에 넣으면, 어떤 집엔 최소 10마리 이상 있음.
즉, 중복된 해시값(= 충돌)이 반드시 발생하게 된다.
Always exists keys a, b such that h(a) = h(b) → Collision! :(
항상 서로 다른 키 a, b 를 해시 함수에 넣었을 때 h(a) = h(b) 출력된 해시 값이 똑같은 경우가 생긴다.
충돌(Collision) 발생
Can’t store both items at same index, so where to store?
같은 인덱스에 두 개 이상의 데이터를 동시에 저장할 수 없기 때문에,
충돌이 발생하면 다른 위치에 저장해야 한다.
그럼 어디에 저장해야 하나?
‘Either:’
충돌을 처리하는 대표적인 두 가지 방식이 있다:
– store somewhere else in the array (open addressing)
해시 충돌이 일어나면 배열의 다른 빈 공간을 찾아서 저장하는 방식
* Open Addressing: 해시 테이블에서 충돌이 발생했을 때, 같은 배열 내의 다른 빈 칸에 데이터를 저장하는 방식
해시 함수로 계산한 위치가 이미 다른 키로 차 있는 경우, 그 다음 빈 자리를 찾아 “열린(open)” 다른 주소에 저장
예시) h(k1) = 5, h(k2) = 5인 경우
5번 칸이 이미 차 있으면, 6번 칸, 7번 칸…을 차례로 조사해서 빈 곳에 넣는다.
∗ complicated analysis, but common and practical
이 방식은 분석이 복잡하지만, 실제로 자주 쓰이며 실용적이다.
배열 내에서만 움직이므로 공간 효율이 좋으나
테이블이 꽉 차기 시작하면 빈자리를 찾기 어려워 충돌 해결이 느려지고
클러스터링 발생: 연속된 빈 칸이 줄어들어 성능 저하된다
– store in another data structure supporting dynamic set interface (chaining)
해시 테이블의 각 칸에 리스트(혹은 트리 등)를 두고, 충돌된 값을 리스트에 연결해서 저장한다.
이 방식은 체이닝(Chaining) 이라고 부른다.
3-2. Chaining 체인닝
• Idea! Store collisions in another data structure (a chain)
아이디어: 해시 충돌이 발생했을 때, 해당 인덱스에 값을 덮어쓰지 않고,
대신 그 위치에 다른 자료구조(예: 연결 리스트)로 충돌된 항목들을 저장한다.
이를 체이닝(Chaining)이라 한다.
• If keys roughly evenly distributed over indices, chain size is n/m = n/Ω(n) = O(1)!
키들이 해시 테이블의 인덱스들에 고르게 분포한다면, 각 체인에 들어갈 아이템 수는 평균적으로 n / m개가 된다.
해시 테이블 크기 m이 Ω(n)일 정도로 충분히 크면, 체인 길이는 평균적으로 O(1)이다.
예를 들어 아이템(n)이 10개 있는데 해시 테이블 칸(m)이 10칸 있으면
각 칸에 들어가니 충돌없이 O(1)으로 빨리 해결
- n: 저장된 전체 아이템 수
- m: 해시 테이블의 크기 (버킷 개수)
- n / m = O(1)이면, 평균적으로 각 체인이 매우 짧다 → 빠름
• If chain has O(1) size, all operations take O(1) time! Yay!
각 체인의 길이가 평균적으로 상수 시간 안에 처리 가능한 정도(O(1))이라면,
삽입, 탐색, 삭제 등 모든 연산도 평균적으로 O(1) 시간에 처리된다.
• If not, many items may map to same location, e.g. h(k) = constant, chain size is Θ(n) :(
하지만 많은 아이템들이 같은 위치로 매핑되면, 같은 해시값을 반환하게 되고 그럼 체인 사이즈는 Θ(n)이 된다
h(k) = constant 인 경우
해시 함수가 어떤 입력 키 k를 받아도 항상 같은 값을 반환한다. 아주 나쁜 해시 함수다
h(k) = k % m처럼, 키를 적절히 분산시켜야 하는데,
h(k) = 0처럼 항상 같은 값을 반환하면, 모든 키가 같은 해시 테이블 위치로 가게 되고,
그 위치의 체인이 길어져서 탐색/삽입/삭제가 O(n)이 된다. 그냥 리스트가 되어 버리는 셈 ㅠ
• Need good hash function! So what’s a good hash function?
그래서 중요한 건 좋은 해시 함수를 사용하는 것! 여기서 "좋은 해시 함수란 뭘까?"
3-3 해시 함수 Hash Functions
3-3-1 분배가 안좋은 해시 함수
Division (bad): h(k) = (k mod m)
해시 함수 중 하나는 키 k를 해시 테이블 크기 m으로 나눈 나머지를 사용하는 방식이다
* mod: modulo의 줄임말로, a를 b로 나누었을 때의 나머지
예시) h(k)=kmod 10 인 경우
- 해시 테이블 크기
- 넣고 싶은 키 값들: k= 1, 12, 23, 34, 45
키 k 해시 값 h(k) = k \mod 10
| 키 | 계산 k mod m | h(k) |
| 1 | 1 % 10 | 테이블 인덱스 1 번에 저장 |
| 12 | 12 % 10 | 테이블 인덱스 2 번에 저장 |
| 23 | 23 % 10 | 테이블 인덱스 3 번에 저장 |
| 34 | 34 % 10 | 테이블 인덱스 4 번에 저장 |
| 45 | 45 % 10 | 테이블 인덱스 5 번에 저장 |
Index: 0 1 2 3 4 5 6 7 8 9
Value: -- 1 12 23 34 45 -- -- -- --
이 경우는 해시 테이블에 균등하게 분포되기 때문에, 충돌이 적고 빠르게 검색할 수 있다
하지만 Key 들이 전부 10의 배수면
- 넣고 싶은 키 값들: k= 10, 20, 30, 40, 50
| 키 | 계산 k mod m | h(k) |
| 10 | 10 % 10 | 테이블 인덱스 0 번에 저장 |
| 20 | 20 % 10 | 테이블 인덱스 0 번에 저장 |
| 30 | 30 % 10 | 테이블 인덱스 0 번에 저장 |
| 40 | 40 % 10 | 테이블 인덱스 0 번에 저장 |
| 50 | 50 % 10 | 테이블 인덱스 0 번에 저장 |
모두 인덱스 0번에 저장됨. 그럼 해시 충돌 발생
Heuristic, good when keys are uniformly distributed!
이 방식은 단순하지만, 키들이 고르게 분포되어 있을 때는 잘 작동한다.
* Heuristic(휴리스틱) 문제를 완벽하게 해결하기보다, 완벽하지 않더라도 실용적으로 빠르게 해결책을 찾는 방법
m should avoid symmetries of the stored keys
하지만 m 값을 잘못 설정하면 충돌이 많이 생길 수 있다.
예: m = 10, 그리고 키들이 모두 짝수라면 (짝수 % 10)은 0, 2, 4, 6, 8에만 저장됨 → 절반은 낭비됨
* symmetry는 대칭적인 구조를 말하는 데 여기서 패턴이나 규칙적인 간격으로 반복되는 구조를 의미한다
예) keys = [100, 200, 300, 400, 500] 모두 100의 배수
Large primes far from powers of 2 and 10 can be reasonable
좋은 m의 예: 2나 10의 거듭제곱에서 먼 큰 소수 (예: 997, 1009) 선택
이런 값은 키들이 특정한 규칙을 따를 때도 충돌 가능성을 줄여준다
그래서 실전에서는 종종 m = 9973 같은 소수를 씀
* primes: 소수(素數), 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수
예: 2, 3, 5, 7, 11, 13, 17, ... 997, 1009, 10007, 65537
Python uses a version of this with some additional mixing
Python도 기본적으로 k % m 방식의 해시를 사용하지만,
해시 값이 더 잘 섞이도록 추가적인 섞기(mixing) 과정이 들어감.
예: 문자열 해싱에서는 내부적으로 랜덤 시드를 활용해서 충돌을 줄임.
If u ≫ n, every hash function will have some input set that will a create O(n) size chain
만약 가능한 키의 범위 u가 실제 저장할 개수 n보다 훨씬 크다면 (즉, u ≫ n)
어떤 해시 함수라도 반드시 O(n) 길이의 체인을 만드는 입력 집합이 존재한다.
이건 정보 이론적인 하한이다: 어떤 해시 함수라도 최악의 경우를 피할 수는 없다.
예시 상황
- 해시 테이블 크기 m = 10 (즉, 인덱스는 0~9)
- 저장할 데이터 수 n = 5
- 가능한 키의 범위 u = 100000 (예: 정수 0부터 99999까지 가능)
h(k) = k % 10 → 즉, 키를 10으로 나눈 나머지로 인덱스를 정할 때
만약 key로 k = {10, 20, 30, 40, 50} 이렇게 들어온다면
아무리 키의 범위(u)가 넓다고 해도 k 함수에 문제가 없음에도 충돌이 일어날 수 있다
모든 해시 함수는 최악의 경우를 피할 수 없다
Idea! Don’t use a fixed hash function! Choose one randomly (but carefully)
그래서 해결책 중 하나는 고정된 해시 함수를 쓰지 말고, 무작위로 선택하자! (하지만 조심히)
하지만 아무 해시 함수나 랜덤하게 쓰면 안 되고,
수학적으로 잘 설계된 "랜덤한 해시 함수 집합" 중에서 하나를 선택해야 한다.
그래서 유니버설 해싱(Universal Hashing)을 완전 해싱(Perfect Hashing)을 사용하면 유용하다
3-3-2 Universal 유니버셜 해싱
| 목적 | 평균적으로 충돌을 적게 발생시키기 위해 해시 함수 집합을 사용하는 것 |
| 기술 핵심 | 여러 해시 함수 중에서 무작위로 하나를 선택해 사용 |
| 충돌 보장 | 임의의 두 키가 충돌할 확률이 최대 1/m 이하임 |
| 성능 | 평균 시간복잡도 O(1) (기댓값 기준) |
| 사용 시점 | 온라인 상황 (데이터가 계속 들어오거나 삭제되는 경우) |
| 예시 함수 | h_{a,b}(k) = ((ak + b) mod p) mod m |
Universal (good, theoretically)
h_ab(k): 하나의 해시 함수. 함수들이 모이면 해시 함수 패밀리(hash function family)가 됨
a: 이상 이하의 정수. 랜덤 선택
b: 이상 이하의 정수 (더하기 계수). 랜덤 선택
a, b: 랜덤 선택하는 이유, 해시가 균등하게 퍼지도록 만들기 위해
k: key
p: prime number (소수 중에서 큰 수)
m: 해시 테이블의 크기
mod: modulo" (모듈로) 나누기 하고 나서 남은 나머지 구함
이 함수는 두 번 mod 연산을 함으로써 충돌을 줄이는 방법을 썼다
수식을 정리하면
어떤 숫자 키 가 주어지면,
그것에 무작위 숫자 를 곱하고 를 더한 다음,
큰 소수 로 나눈 후 그 나머지를 구하고,
그걸 다시 칸 수 으로 나눈 후 그 나머지로 바꿔서,
"이 데이터를 몇 번째 칸에 넣을지" 결정
예시) p = 7, m = 5, k ∈ {0, 1, 2, 3, 4, 5} 일 때
- a: a ∈ {1, 2, 3, 4, 5, 6} 가됨. 단, a ≠ 0 → a는 1~6 중 선택. 이상 이하의 정수
- b: b ∈ {0, 1, 2, 3, 4, 5, 6} 가됨
- 해시 결과는 0~4 중 하나가 됨
랜덤으로 a = 2, b = 3 경우 k = 0부터 5까지 해시 결과 계산
h_(2,3)(k) = (( 2k + 3 ) mod7) mod5
| k | (2k + 3) mod 7 수식에 대입 | 계산 | mod 5 에 대입 | 계산 | h₂₃(k) 해시 결과 |
| 0 | (0 + 3) mod 7 = 3 | 3 % 7 = 3 | 3 mod 5 = 3 | 3 % 5 = 3 | 3 |
| 1 | (2 + 3) mod 7 = 5 | 5 % 7 = 5 | 5 mod 5 = 0 | 5 % 5 = 0 | 0 |
| 2 | (4 + 3) mod 7 = 0 | 7 % 7 = 0 | 0 mod 5 = 0 | 0 % 5 = 0 | 0 |
| 3 | (6 + 3) mod 7 = 2 | 9 % 7 = 2 | 2 mod 5 = 2 | 2 % 5 = 2 | 2 |
| 4 | (8 + 3) mod 7 = 4 | 11 % 7 = 4 | 4 mod 5 = 4 | 4 % 5 = 4 | 4 |
| 5 | (10 + 3) mod 7 = 6 | 13 % 7 = 6 | 6 mod 5 = 1 | 6 % 5 = 1 | 1 |
계산 결과 이 함수는 키 k ∈ {0, 1, 2, 3, 4, 5}를 [0, 1, 2, 3, 4] 중 하나로 분산시킴
H(p, m): Universal Hash Family (해시 함수 패밀리), 가능한 모든 h_ab(k)를 모아 놓은 집합
a ≠ 0 조건은 충돌 방지를 위해 필요함
예시) 해시 패밀리 H(7, 5)에 해시 함수들은 몇 개 정도가 있을까?
H(7, 5)는 p = 7, m = 5
a: a ≠ 0, 이하의 정수라서 a ∈ {1, 2, 3, 4, 5, 6} - 총 6개
b: 이하의 정수라서 b ∈ {0, 1, 2, 3, 4, 5, 6} - 총 7개
그래서 총 가능한 조합은?
a 1개 고르면, b는 7개 중 하나 가능
a는 6개 × b는 7개 = 6×7=42
h_{a,b}(k) 해시 함수가 총 42개 나온다
Parameterized by a fixed prime p > u, with a and b chosen from range {0, ..., p − 1}
key 범위를 나타내는 수보다 큰 수를 prime으로 지정한 후, 이 p의 값에 따라 a, b의 값이 달라진다
a는 1부터 p - 1 사이의 값
b는 0부터 p - 1 사이의 값에서 무작위로 선택하는 것이기 때문이다.
p > u 조건은 모듈로 연산의 충돌을 줄이기 위해 필요하다.
p가 작으면 다른 키들이 동일한 해시 값을 가질 수 있다.
Pr: Probability, 확률
H: 해시함수 집합. 유니버샬 해시 패밀리. a와 b를 여러 값으로 바꿔가며 만든 해시 함수들 전부가 H에 들어간다. H는 수천 개, 수만 개의 해시 함수를 포함할 수 있는 큰 집합이다
해시 함수 모음 예시)
h₁(k) = (3k + 1) mod 17 mod m
h₂(k) = (5k + 2) mod 17 mod m
h₃(k) = (7k + 0) mod 17 mod m
해시 함수 이름 수식 표현
h_{1,0}(k) ((1⋅k+0)mod 17)mod 5
h_{2,3}(k) ((2⋅k+3)mod 17)mod 5
h_{5,10}(k) ((5⋅k+10)mod 17)mod 5
h_{16,16}(k) ((16⋅k+16)mod 17)mod 5
Pr_{h ∈ H}: h를 H라는 집합에서 무작위로 고를 때 확률. 많은 해시 함수 중 하나를 랜덤으로 고를 때 사용
{ h(k_i) = h(k_j) }: 해시 함수 h에 두 개의 키 k_i, k_j를 넣었는데, 결과가 같다 = 충돌(collision) 발생 시
≤ 1/m: 그런 일이 일어날 확률이 1/m보다 작거나 같다.
∀: for all, 모든 ~에 대해, 임의의 ~에 대해서도
∀k_i ≠ k_j ∈ {0, …, u − 1}: 0부터 u−1까지의 모든 숫자 중에서, 서로 다른 두 개의 값 kᵢ, kⱼ이 주어질 때
u: 키의 범위
해시 함수 모음에서 랜덤으로 해시 함수를 하나 골랐을 때,
키의 범위 안에 있고, 서로 다른 두 키가 같은 번호로 가는 확률은 1/m보다 작거나 같아야 한다
Why is universality useful? Implies short chain lengths! (in expectation)
유니버설 해시 함수가 왜 유용한가? 기댓값 상으로 짧은 체인 길이를 보장하기 때문이다
충돌 확률이 낮으면 해시 테이블에서 하나의 인덱스에 몰리는 값들(chain)이 적어지기 때문이다
X_ij: 두 키 k_i와 k_j가 어떤 해시 함수 h를 사용했을 때 충돌했는지를 나타내는 변수
i, j: 서로 다른 키를 구분하기 위한 인덱스(index) 번호
k_i, k_j: 해시 테이블에 넣는 서로 다른 두 키
h ∈ H: 해시 함수들의 집합 (hash function family), h는 그 중 하나의 해시 함수
Xij = 1이면 → h(ki) = h(kj) → 충돌이 발생
Xij = 0이면 → h(ki) ≠ h(kj) → 충돌이 발생하지 않음
이 X_ij 변수를 통해 예상 충돌 횟수를 수학적으로 분석할 수 있다
다음 수식을 이용해 kᵢ가 충돌할 수 있는 총 횟수를 예측할 수 있다
충돌 횟수 = 체인 길이
X_i: 키 k_i와 충돌하는 키수를 나타내는 변수
i: 알아볼 특정한 하나의 키
j: 그 외의 다른 키들. 모든 키 인덱스를 하나씩 돌면서 kᵢ와 비교하는 대상
X_{ij}:
- 1: k_i와 k_j가 충돌 (즉, h(k_i) = h(k_j))
- 0: 아니면 0
예시) 키가 총 4개 있다 가정 k₁, k₂, k₃, k₄
- 해시 함수 h를 적용했을 때:
- h(k₁) = 3
- h(k₂) = 1
- h(k₃) = 3
- h(k₄) = 5
여기서 k₁과 k₃는 해시 값이 같으므로 충돌.
그럼:
- X₁₃ = 1 (k₁와 k₃ 충돌)
- X₁₂ = X₁₄ = 0 (충돌 아님)
따라서:
X_1 = X_1,2 + X_1,3 + X_1,4 = 0+1+0 = 1
즉 k₁은 1번 충돌함
Expected size of chain at index h(k_i)
키 k_i가 해시되는 슬롯 h(k_i)에 연결된 체인의 평균 길이
* E: Expected value. 어떤 확률 변수 X가 있을 때, 그 값이 평균적으로 얼마가 될지를 나타내는 것
Since m = Ω(n), load factor α = n/m = O(1), so O(1) in expectation!
해시 테이블 크기 m이 n보다 크거나 같게 설정되어 있으므로, 로드 팩터 α = n/m은 상수 수준이다.
따라서 체인 길이도 기대값 상으로 O(1)이며, 모든 연산 (삽입/탐색/삭제)이 평균적으로 O(1) 시간에 수행됨.
* load factor: 평균적으로 하나의 버킷에 몇 개의 항목이 들어가는가
3-4. Dynamic 다이나믹
해시 테이블이 정적인 크기가 아니라, 키의 수(n)에 따라 크기(m)를 자동으로 늘리거나 줄이는 유동적인 구조
If n/m far from 1, rebuild with new randomly chosen hash function for new size m
만약 load factor가 α=n/m이 1에서 너무 멀어지면 (너무 작거나 너무 커지면),
테이블의 크기 을 새롭게 설정하고,
해시 함수도 새롭게 무작위로 골라서,
전체 해시 테이블을 재구성(rebuild) 해야 한다
키가 너무 많거나 적어져서 불균형해지면 테이블 크기와 해시 함수 모두 새로 설정해요.
Same analysis as dynamic arrays, cost can be amortized over many dynamic operations
다시 새롭게 재구성하려면 비용이 크지만, 동적 배열(Dynamic Array)에서 처럼,
한 번의 큰 작업(리사이즈) 비용을 여러 번의 삽입/삭제 연산에 분산시켜 계산할 수 있다
전체적으로 보면 큰 비용이 드는 것처럼 보여도, 한 연산당 평균 비용은 작다
So a hash table can implement dynamic set operations in expected amortized O(1) time! :)
그래서 결과적으로, 해시 테이블은 삽입, 삭제, 검색 같은 동적 집합 연산들을 평균적으로 기대 시간 O(1)에 처리할 수 있어요!
(기댓값 기반 + 분할 상환 기반)
* e: expected time 기대 시간 (확률적으로 평균적으로 걸리는 시간)
* a: amortized time 분할 상환 시간 (여러 연산에 걸쳐 평균적으로 나누어진 시간)
출처
자료: Lecture 4: Introduction Note - 6.006 Introduction to Algorithm - MIT Open Course
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec4/
강의: https://youtu.be/Nu8YGneFCWE?si=z7PWG0Ud6MwGXye4
'Computer Science > MIT Introduction to Algorithms 6.006' 카테고리의 다른 글
| Lecture 6: Binary Trees, Part 1 이진 트리 (2) | 2025.06.08 |
|---|---|
| Lecture 5: Linear Sorting (3) | 2025.06.06 |
| Lecture 3: Sorting 정렬 (0) | 2025.06.02 |
| Lecture 2: Data Structures (0) | 2025.05.30 |
| Lecture 1: Introduction - MIT Introduction to Algorithm 6.006 알고리즘 소개 (0) | 2025.05.28 |
댓글