Map and Hash

 이 단원은 사실 하나의 큰 이야기로 연결되어 있다. 요약하면:

Map이라는 추상적인 자료구조를 정의하고 → 가장 단순한 구현(배열 기반)의 한계를 보고 → Hash Table로 "정확한 key 조회"를 O(1)에 해결하지만 → 그 과정에서 "순서 정보"를 잃어버려서 → Sorted Map이 필요해지고 → Sorted Map도 여전히 insert/delete가 O(n)이라는 한계가 남는다.

 

 이 마지막 한계를 해결하는 게 바로 다음 단원(BST, AVL Tree)의 주제다. 그러니 이 글을 읽고 나면 "왜 BST가 필요한가?"에 대한 답이 자연스럽게 나와야 한다.

---

1. Map ADT — 기본 인터페이스

 Map은 key-value 쌍을 저장하는 자료구조다. Python의 dict가 정확히 이 Map ADT를 구현한 것이라고 보면 된다.

1.1 핵심 메서드 정리

메서드	설명	비고
M[k]	key k의 value 반환	없으면 KeyError
M[k] = v	(k,v) 추가/갱신	이미 있으면 덮어씀
del M[k]	key k인 item 제거	없으면 KeyError
len(M)	item 개수
k in M	key 존재 여부	True/False
M.get(k, d=None)	M[k] 있으면 반환, 없으면 d (기본 None)	KeyError 안 남
M.setdefault(k, d)	k 있으면 M[k] 반환; 없으면 M[k]=d로 설정 후 d 반환	부작용 있음(삽입)
M.pop(k, d=None)	k의 value 제거+반환; 없으면 d (d가 None이면 KeyError)
M.popitem()	임의의(arbitrary) (k,v) 제거+반환	빈 맵이면 KeyError
M.keys(), .values(), .items()	view 반환
M.update(M2)	M2의 모든 항목을 M에 반영

 

1.2 get, setdefault, pop의 "default 인자"는 다 다르게 동작한다

 

 이 세 메서드는 모두 "두 번째 인자로 default 값을 받는다"는 공통점 때문에 헷갈리기 쉽다. 하지만 동작 방식은 전부 다르다.

메서드	키 k가 있을 때	키 k가 없을 때	부작용(side effect)
M.get(k, d)	M[k] 반환	d 반환	없음
M.setdefault(k, d)	M[k] 반환 (그대로 유지)	M[k]=d로 삽입 후 d 반환	있음 (삽입)
M.pop(k, d)	M[k] 제거 후 반환	d 반환 (d 없으면 KeyError)	있음 (제거)

 

특히 setdefault가 가장 헷갈리는데, "읽기"처럼 보이는 이름인데 실제로는 맵을 수정할 수 있다는 게 핵심이다.

M = {'A': 5}
M.setdefault('A', 1)  # 'A' 있음 → 5 반환, M = {'A':5} (변화 없음)
M.setdefault('B', 1)  # 'B' 없음 → M에 'B':1 삽입! → 1 반환, M = {'A':5, 'B':1}

 

 "그냥 값 좀 확인해 보는" 메서드처럼 보이지만, 실제로는 키가 없으면 그 키를 맵에 새로 추가해 버리는 부작용이 있다. 단순히 "값이 있는지 확인만 하고 싶었던" 코드에서 setdefault를 잘못 쓰면, 의도치 않게 맵에 새 키들이 계속 쌓이는 버그가 생길 수 있다.

1.3 직접 손으로 따라가보는 예제

다음 연산을 순서대로 수행했을 때 M의 최종 상태와 각 연산의 반환값을 표로 정리하면:

초기 M = {}
M['A'] = 5
M['B'] = 10
M['C'] = 15
M.get('D', -1)
M.setdefault('B', 100)
M.setdefault('D', 100)
del M['A']
M.pop('C')
M.pop('Z', 0)
len(M)

연산	반환값	연산 후 M
M['A'] = 5	(없음)	{'A':5}
M['B'] = 10	(없음)	{'A':5, 'B':10}
M['C'] = 15	(없음)	{'A':5, 'B':10, 'C':15}
M.get('D', -1)	-1	변화 없음
M.setdefault('B', 100)	10	변화 없음 (B는 이미 있으므로 100은 무시됨)
M.setdefault('D', 100)	100	{'A':5, 'B':10, 'C':15, 'D':100}
del M['A']	(없음)	{'B':10, 'C':15, 'D':100}
M.pop('C')	15	{'B':10, 'D':100}
M.pop('Z', 0)	0	변화 없음 (Z가 없지만 default가 있어서 에러 안 남)
len(M)	2	{'B':10, 'D':100}

 

여기서 가장 많이 하는 실수 두 가지:

1. M.setdefault('B', 100)을 호출했을 때 "100이 반환되거나 100으로 덮어쓰일 것"이라고 생각하는 것 — 틀렸다. 'B'는 이미 존재하므로 100은 완전히 무시되고 기존 값 10이 반환된다.
2. M.pop('Z', 0)이 KeyError를 낼 거라고 생각하는 것 — 틀렸다. default 값(0)이 주어졌으므로 에러 없이 0을 반환한다.

1.4  M['X'] vs M.get('X')

• M['X'] — 'X'가 없으면 KeyError 발생. "이 키는 반드시 있어야 한다"는 전제로 동작.
• M.get('X') — 'X'가 없어도 에러 없이 None 반환 (default를 안 주면 None이 기본값).

get은 "키가 있는지 확신할 수 없을 때, 에러 없이 안전하게 조회하고 싶을 때" 쓰고, M['X']는 "이 키는 당연히 있을 것"이라고 전제할 때 쓴다.

1.5 popitem()이 던지는 힌트 — Map에는 "순서"가 없다

M.popitem()은 "arbitrary", 즉 임의의(특정 기준 없는) (k,v) 쌍을 제거한다. "가장 작은 key를 가진 항목을 제거한다"가 아니다. 이게 왜 중요한가 하면, "최솟값/최댓값 key", "key들 사이의 대소 비교" 같은 개념이 일반 Map ADT에는 아예 없다는 걸 보여주기 때문이다. 이 사실이 뒤에서 Sorted Map이 왜 필요한지에 대한 motivation이 된다.

---

2. Map의 단순한 구현 — Unsorted Table & Sorted Search Table

2.1 두 가지 구현과 시간복잡도

Operation	Unsorted Table	Sorted Search Table
Find (key 탐색)	O(n)	O(log n)
Insert	O(1)	O(n)
Delete	O(n)	O(n)

• Unsorted Table: 순서 없이 저장. 삽입은 그냥 끝에 추가하면 되니까 O(1). 하지만 탐색/삭제는 어디 있는지 모르니 처음부터 끝까지 봐야 함 → O(n).
• Sorted Search Table: key 기준으로 정렬된 배열. Binary search로 탐색은 O(log n)이지만, 삽입/삭제 시 나머지 원소들을 shift해야 해서 O(n).

2.2 함정: "위치(position)가 주어졌는가, key만 주어졌는가"

 표에서 Unsorted Table의 Delete가 O(n)이라는 부분이 직관에 안 맞을 수 있다. 배열 자료구조 일반론에서는 "unsorted array의 삽입/삭제는 O(1)"이라고 배우기 때문이다.

 이 둘이 모순되지 않는 이유는, 그 O(1) 주장은 "위치(index/pointer)가 이미 주어졌다고 가정"한 것이기 때문이다 (Note: Assume we know the index for Add and Remove). 하지만 Map의 del M[k]는 index가 아니라 key만 주어진다. Unsorted table은 순서가 없으므로, key k를 가진 항목을 찾으려면 처음부터 끝까지 다 봐야 한다 → 이 탐색만으로 이미 O(n). 일단 찾고 나면 제거 자체는 O(1)이지만, 탐색이 dominant해서 전체 del M[k]는 O(n)이다.

즉, "위치가 주어졌는지 vs key만 주어졌는지"를 구분하는 게 이 단원의 숨은 핵심 포인트다.

2.3 Binary Search 복습 — mid은 항상 내림(floor)이다

Sorted Search Table의 핵심 도구는 binary search다.

def binary_search(data, target, low, high):
    if low > high:
        return False  # 빈 구간 → 못 찾음
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid - 1)   # 왼쪽 절반
        else:
            return binary_search(data, target, mid + 1, high)  # 오른쪽 절반

 

여기서 자주 헷갈리는 두 가지를 짚고 넘어가자.

(1) mid = (low+high)//2는 항상 내림(floor)이다. low+high가 홀수든 짝수든 //(정수 나눗셈)는 무조건 소수점 아래를 버린다. "홀수면 mid를 어떻게 잡지?"라는 고민은 필요 없다 — 그냥 더해서 2로 나누고 버리면 끝.

(2) 구간을 줄일 때는 반드시 ±1을 붙인다. 오른쪽으로 갈 때는 low = mid + 1, 왼쪽으로 갈 때는 high = mid - 1이다. 절대 low = mid나 high = mid로 두면 안 된다 — 이미 비교가 끝난 A[mid]를 또 비교 범위에 포함시키게 돼서 무한루프나 잘못된 결과로 이어진다.

2.4 직접 손으로 따라가보는 binary search 예제

배열 A (인덱스 0~8, n=9):

인덱스:  0   1   2   3   4   5   6   7   8
값(key): 3   7   11  15  19  23  27  31  35

 

(a) target = 23인 경우

단계	low	high	mid = (low+high)//2	A[mid]	비교	다음 행동
1	0	8	(0+8)//2 = 4	19	23 > 19	오른쪽 → low = mid+1 = 5
2	5	8	(5+8)//2 = 6	27	23 < 27	왼쪽 → high = mid-1 = 5
3	5	5	(5+5)//2 = 5	23	23 == 23	찾음! index 5

 

(b) target = 24인 경우 (배열에 없는 값)

단계	low	high	mid	A[mid]	비교	다음 행동
1	0	8	4	19	24 > 19	오른쪽 → low = 5
2	5	8	6	27	24 < 27	왼쪽 → high = 5
3	5	5	5	23	24 > 23	오른쪽 → low = mid+1 = 6
4	6	5	—	—	low(6) > high(5) → 종료	못 찾음

 low > high가 된 시점에서 low = 6이라는 게 바로 "24가 들어가야 할 위치"다. 즉 index 5(값 23)와 index 6(값 27) 사이, 삽입한다면 index 6 자리에 들어간다. Binary search는 단순히 True/False만 알려주는 게 아니라, "없으면 어디에 들어가야 하는지"까지 알려준다 — 이걸 inexact search라고 부르고, 이게 뒤에서 다룰 Sorted Map의 핵심 능력이다.

2.5 Sorted Map이 주는 추가 능력 (vs Hash Table)

정렬돼 있다는 건 "key들 사이의 대소 비교가 가능하다"는 뜻이다. 그래서 다음과 같은 연산들이 가능해진다:

• find_max: 정렬된 배열의 맨 끝 원소 A[n-1]을 보면 끝 → binary search도 필요 없이 O(1)
• find_lt(19) ("19보다 작은 가장 큰 key"): binary search로 19가 (있다면) 있는 위치 또는 들어갈 위치를 찾고, 그 바로 왼쪽 원소가 답이 된다 → O(log n)

 이게 가능한 이유는 "배열에서의 위치 순서 = key의 대소 순서"이기 때문이다.

반면 Hash Table에서는 이게 불가능하다. Hash table의 key 자체는 비교 가능하지만(예: 정수라면 19 < 23 비교 가능), key의 값과 그 key가 저장되는 위치(bucket index) 사이에는 순서 관계가 없다. Hash function이 18과 19처럼 값이 거의 붙어있는 key들도 완전히 다른, 멀리 떨어진 bucket에 저장할 수 있다. 즉 "저장 구조 자체가 key의 순서 정보를 보존하지 않는다." 그래서 "19보다 작은 가장 큰 key"나 "최댓값"을 찾으려면, 모든 bucket을 다 뒤져서 모든 key를 일일이 비교해야 함 → O(n).

---

3. Hash Table — Hash Function과 Compression Function

3.1 동기: 만약 key가 그냥 인덱스로 쓸 수 있는 정수라면?

 만약 모든 key가 0부터 N-1 사이의 정수라면, 그냥 key를 배열의 인덱스로 직접 써버리면 된다. M[k]를 A[k]로 바로 접근 → 모든 연산이 O(1). 이건 사실 h(k) = k (항등함수)라는 가장 단순한 hash function을 쓰는 특수한 경우다. 우연히 항등함수라서 순서도 그대로 보존된다 (k1 < k2 ⟺ h(k1) < h(k2)).

 하지만 일반적으로는 key가 0~N-1 범위를 벗어나거나(예: 학번, SSN처럼 큰 수) 정수가 아닐 수 있다(예: 문자열). 이때는 h(k)=k를 쓸 수 없으니 다른 hash function이 필요하다. 예를 들어 h(k) = k mod 10이라면:

key 19 → h(19) = 9
key 23 → h(23) = 3
key 100 → h(100) = 0

 

 19 < 23인데 h(19)=9 > h(23)=3이다. "hash table에서는 key의 순서와 저장 위치의 순서가 무관하다"는 게 바로 이런 의미다 — h(k)=k라는 운 좋은 특수 케이스가 아니면, 일반적인 hash function은 순서를 보존하지 않는다.

 

3.2 Hash Function의 2단계 구조

Hash function h(k)는 사실 두 단계로 나눠서 생각한다:

1. Hash code: key k → 임의의 정수 (범위 제한 없음, 음수 가능)
2. Compression function: 그 정수 → 0 ~ N-1 범위로 압축 ← 이게 실제 인덱스를 결정

주의: hash code 자체가 인덱스를 정하는 게 아니다. Hash code는 key를 어떤 정수로 바꾸는 단계일 뿐이고, 그 정수는 0~N-1 범위 밖일 수도 있어서 이대로는 배열 인덱스로 못 쓴다. 실제로 "인덱스를 결정"하는 건 compression function이다.

왜 굳이 두 단계로 나누는가? 구체적인 예로 보자:

key = "Bob"
hash code: "Bob"라는 문자열을 어떤 정수로 변환 → 예: 3,482,910,556
   (이 숫자는 N=10인 테이블의 인덱스로 쓸 수 없음 — 너무 큼)

compression function: 3,482,910,556 mod 10 = 6  ← 이게 실제 인덱스!

 

이제 테이블이 N=10에서 N=20으로 resize된다면:

• hash code (3,482,910,556)는 여전히 그대로 — key "Bob"의 hash code는 테이블 크기와 무관하므로 다시 계산할 필요 없음
• compression function만 다시 계산: 3,482,910,556 mod 20 = 16 ← 새로운 인덱스

즉, hash code는 N에 의존하지 않고, compression function만 N에 의존한다. 그래서 resize할 때 (특히 hash code 계산이 비용이 큰 경우) 모든 key의 hash code를 다시 계산할 필요 없이, 이미 계산해둔 hash code에 새로운 N으로 mod만 다시 해주면 된다는 게 이 2단계 구조의 핵심 장점이다.

 

3.3 Compression Function ① — Division Method (i mod N)

가장 단순한 방법: i mod N. 결과가 자동으로 0~N-1에 들어간다.

문제는 N을 어떻게 고르느냐에 따라 충돌 패턴이 완전히 달라진다는 것이다.

예제 1: key = {200, 205, 210, ..., 600} (5씩 증가, 총 81개)

key	mod 100	mod 101
200	0	99
205	5	3
210	10	8
295	95	...
300	0 (200과 충돌!)	...

• N=100: 100을 5로 나눈 값(20)마다 나머지가 반복돼서, 200/300/400/500/600이 전부 같은 칸(0번)에 몰린다.
• N=101: 101은 소수라서 5의 배수 관계가 전혀 없다. 81개의 key가 다 들어가도 나머지가 한 번도 안 겹친다 → 충돌 없음.

예제 2: key = {12, 44, 76, 108} (32씩 증가)

key	mod 8	mod 11
12	4	1
44	4	0
76	4	10
108	4	9

• N=8: 32 = 4×8, 즉 32는 8의 배수다. 어떤 key에 32를 더해도 mod 8 값은 전혀 안 바뀐다 (32를 더하는 건 mod 8 입장에서 0을 더하는 것과 같음). → 4개 key 전부 같은 나머지(4) → 전원 충돌.
• N=11: 32 mod 11 = 10 ≡ -1 (mod 11). key에 32를 더할 때마다 나머지는 10씩(=1씩 감소) 바뀐다: 1 → 0 → 10 → 9. gcd(32,11)=1(서로소)이라서 11개를 다 거치기 전엔 절대 반복 안 됨 → 충돌 없음.

일반화: key들이 일정한 간격(여기선 32)으로 배치되어 있을 때, 그 간격이 N의 배수면(=N이 그 간격을 나누면) 충돌이 시스템적으로 발생한다. N을 소수로 잡으면, 어떤 간격을 가진 key 집합이라도 그 간격과 우연히 약수 관계를 가질 확률이 낮아진다.

3.4 Compression Function ② — MAD (Multiply-Add-Divide)

h(i) = [(a·i + b) mod p] mod N (p는 N보다 큰 소수, a>0과 b는 [0,p-1]에서 랜덤 선택)

division method만으로는, key들이 어떤 규칙적인 패턴(예: 모두 32씩 증가)을 가질 때 N을 잘못 고르면 충돌이 시스템적으로 발생한다는 게 문제였다. MAD는 mod 하기 전에 값을 한번 "섞어버려서" 이 문제를 줄인다.

예제: key = {12, 44, 76, 108}, N=8 (앞서 본 것처럼 그냥 mod 8을 쓰면 전부 충돌했던 케이스)

MAD를 a=3, b=2, p=11로 적용: h(k) = [(3k+2) mod 11] mod 8

k	3k+2	mod 11	mod 8
12	38	5	5
44	134	2	2
76	230	10	2
108	326	7	7

 결과: 5, 2, 2, 7 → 44와 76만 충돌 (1쌍). mod 8로는 4개 다 충돌했는데, MAD로는 1쌍으로 줄었다.

 

MAD가 하는 일을 정확히 이해하기: MAD는 충돌을 0개로 만든다는 보장은 없다 (실제로 1쌍은 여전히 충돌했다). 대신 MAD가 주는 건, 원래 key들이 가지고 있던 "N과 정확히 맞아떨어지는 규칙적인 패턴"을 깨뜨려서, 두 key가 충돌할 확률이 대략 1/N에 가까운, 균등한(random-like) 확률이 되도록 만들어주는 것이다. Division method처럼 "특정 패턴의 key 집합이면 100% 충돌"이라는 예측 가능한 최악의 경우를 피할 수 있게 해주는 셈이다.

3.5 Load Factor (α) — worst case가 아니라 average case를 위한 장치

α = n / N (n = 저장된 item 개수, N = 테이블 크기). 보통 α < 0.9를 유지하려고 한다.

예제: n=18, N=20이면 α = 18/20 = 0.9. 이건 "이미 위험한 상태"가 아니라 정확히 경계선이다 — 여기서 하나만 더 넣으면 0.9를 넘으니, 지금이 resize를 고려할 타이밍이라는 신호다.

 

Worst case (O(n))는 언제 발생하는가? hash function이 모든 key를 단 하나의 bucket으로 몰아넣을 때다. 예를 들어 h(k)=0처럼 극단적으로 나쁜 hash function이면, n개의 item이 하나의 bucket의 linked list에 전부 들어있게 되고, 그 bucket 안에서의 탐색은 O(n)이다.

여기서 중요한 건, 이건 α 값이 크든 작든 일어날 수 있는 일이라는 것이다. N=1000인데 n=10개뿐이어도(α=0.01), 그 10개가 전부 같은 칸에 몰리면 그 칸은 여전히 O(10)=O(n)이다. 즉 worst case는 "hash function의 품질"에 관한 문제고, α는 직접적인 원인이 아니다.

 

 그럼 왜 average case는 O(1)인가? hash function이 "좋다"고 가정하면, n개의 item이 N개 bucket에 고르게(균등하게) 분산된다. 이때 bucket 하나당 평균 item 개수는 n/N = α다. 만약 α가 어떤 상수(예: 0.9 이하)로 유지된다면, bucket당 평균 item 개수도 그 상수 수준으로 유지되고, 한 bucket 안에서의 탐색은 평균적으로 O(α) = O(1)이 된다.

 즉, resize(α를 일정 이하로 유지하는 것)는 "worst case를 막기 위한 것"이 아니라, "average case의 O(1) 보장을 유지하기 위한 장치"다. n이 계속 늘어나는데 N을 안 키우면, α=n/N이 커지면서 bucket당 평균 item 개수도 n에 비례해서 커지고, 평균조차 O(n)에 가까워진다.

	Worst case O(n)	Average case O(1)
발생 조건	hash function이 나빠서 모든 key가 한 bucket에 몰림	hash function이 좋고, α가 상수로 유지됨
α와의 관계	무관	resize로 α를 유지하는 게 직접적인 보장 장치

 

---

4. Collision Handling — 충돌이 나면 어떻게 처리할까?

 Hash function이 아무리 좋아도, key 개수가 N보다 많아지면 충돌은 피할 수 없다(pigeonhole principle). 충돌 처리에는 두 가지 큰 접근법이 있다.

4.1 Separate Chaining vs Open Addressing

• Separate Chaining: 각 bucket A[j]가 자체적으로 작은 컨테이너(linked list)를 가지고, h(k)=j인 모든 항목을 그 안에 저장한다.
  • Worst case: O(n/N) = O(α) (hash function이 좋다고 가정)
  • α > 1도 가능 (bucket의 리스트는 얼마든지 길어질 수 있음)
  • 단점: 배열 외에 추가 메모리(linked list 노드들) 필요
• Open Addressing: 배열 칸 자체에 직접 저장한다. 충돌 시 다른 빈 칸을 찾아서(probe) 넣는다.
  • α ≤ 1로 강제됨 (item 개수가 테이블 크기를 넘을 수 없음 — 모든 item이 칸 안에 직접 들어가야 하니까)
  • 추가 메모리는 배열(N칸)뿐

핵심 차이: separate chaining은 구조적으로 α>1을 "허용"하지만(그렇다고 좋은 건 아님 — 여전히 α를 적정 수준으로 유지하는 게 좋음), open addressing은 물리적으로 α≤1이 강제된다.

4.2 Open Addressing 세 가지 방식 — 같은 예시로 비교

같은 key 집합 18, 41, 22, 44, 59, 32, 31, 73을 N=13, h(k) = k mod 13으로 처리해보자.

key	18	41	22	44	59	32	31	73
h(k)	5	2	9	5	7	6	5	8

 

 18, 44, 31이 모두 h=5로 충돌한다는 게 핵심이다. 이 3개가 각 방식에서 어떻게 다르게 흩어지는지 보자.

(참고) Separate Chaining이라면

probing 없이 그냥 해당 bucket의 리스트에 쌓는다:

• bucket 5: [18, 44, 31] / bucket 2: [41] / bucket 6: [32] / bucket 7: [59] / bucket 8: [73] / bucket 9: [22]

Linear Probing (f(i) = i)

probe 순서: A[h(k)+0], A[h(k)+1], A[h(k)+2], ... (mod 13)

순서	key	h(k)	probe 과정	최종 위치
1	18	5	A[5] 비어있음	5
2	41	2	A[2] 비어있음	2
3	22	9	A[9] 비어있음	9
4	44	5	A[5]참(18) → A[6] 비어있음	6
5	59	7	A[7] 비어있음	7
6	32	6	A[6]참(44) → A[7]참(59) → A[8] 비어있음	8
7	31	5	A[5]참→A[6]참→A[7]참→A[8]참→A[9]참→A[10] 비어있음	10
8	73	8	A[8]참→A[9]참→A[10]참→A[11] 비어있음	11

인덱스: 0  1  2  3  4  5  6  7  8  9  10 11 12
값:    -  -  41 -  -  18 44 59 32 22 31 73 -

 

clustering: 31을 넣을 때 6번이나 probe해야 했다 (5→6→7→8→9→10). 5~9가 이미 빽빽하게 채워진 "덩어리(cluster)"가 형성돼 있었기 때문이다. 이게 primary clustering이고, 충돌이 쌓일수록 덩어리가 커져서 다음 충돌의 probe도 더 길어지는 악순환이 생긴다.

Quadratic Probing (f(i) = i²)

probe 순서: A[h(k)+0], A[h(k)+1], A[h(k)+4], A[h(k)+9], ... (mod 13)

순서	key	h(k)	probe 과정	최종 위치
1	18	5	A[5] 비어있음	5
2	41	2	A[2] 비어있음	2
3	22	9	A[9] 비어있음	9
4	44	5	A[5]참(18) → i=1: A[6] 비어있음	6
5	59	7	A[7] 비어있음	7
6	32	6	A[6]참 → i=1: A[7]참 → i=2: A[6+4=10] 비어있음	10
7	31	5	A[5]참→i=1:A[6]참→i=2:A[5+4=9]참→i=3:A[5+9=14mod13=1] 비어있음	1
8	73	8	A[8] 비어있음	8

인덱스: 0  1  2  3  4  5  6  7  8  9  10 11 12
값:    -  31 41 -  -  18 44 59 73 22 32 -  -

 

Linear과 비교: 31이 linear에서는 index 10이었는데, quadratic에서는 index 1로 갔다. +1, +4, +9로 점점 멀리 점프하면서 클러스터를 건너뛴 것이다. 하지만 secondary clustering은 여전히 남는다 — h(k)값이 같은 key들(18,44,31, 모두 h=5)은 항상 똑같은 probe 경로(5→6→9→1)를 따른다.

주의: quadratic probing은 offset이 +1, +4, +9, ...로 빠르게 커지므로, 테이블 크기 N을 쉽게 넘어간다. 이때 반드시 mod N으로 wrap-around해야 한다. 예를 들어 N=7인 테이블에서 3+4=7이 나오면, 인덱스 7은 존재하지 않으므로(인덱스는 0~6) 7 mod 7 = 0으로 wrap해야 한다.

Double Hashing (h'(k) = 7 - (k mod 7))

probe 순서: A[h(k) + i·h'(k)] (mod 13)

key	k mod 7	h'(k)
18	4	3
41	6	1
22	1	6
44	2	5
59	3	4
32	4	3
31	3	4
73	3	4

순서	key	h(k)	h'(k)	probe 과정	최종 위치
1	18	5	3	A[5] 비어있음	5
2	41	2	1	A[2] 비어있음	2
3	22	9	6	A[9] 비어있음	9
4	44	5	5	A[5]참 → i=1: A[5+5=10] 비어있음	10
5	59	7	4	A[7] 비어있음	7
6	32	6	3	A[6] 비어있음	6
7	31	5	4	A[5]참→i=1:A[5+4=9]참→i=2:A[5+8=13mod13=0] 비어있음	0
8	73	8	4	A[8] 비어있음	8

인덱스: 0  1  2  3  4  5  6  7  8  9  10 11 12
값:    31 -  41 -  -  18 32 59 73 22 44 -  -

 

 double hashing의 장점: h(k)=5로 충돌한 18, 44, 31이 각각 5, 10, 0으로 전부 다른 곳에 흩어졌다 (h'(k)가 3, 5, 4로 서로 다르기 때문). 같은 h(k)를 가진 key들끼리도 서로 다른 probe 경로를 따르게 되어 secondary clustering까지 줄어든다.

 

정리

방식	충돌 시 다음 위치	같은 h(k)인 key들의 probe 경로
Separate chaining	(probing 없음, 리스트에 추가)	다 같은 bucket의 리스트
Linear probing	+1, +2, +3, ...	모두 동일 (→ primary clustering)
Quadratic probing	+1, +4, +9, ...	모두 동일 (→ secondary clustering)
Double hashing	+h'(k), +2h'(k), ...	h'(k)가 다르면 경로도 다름

 

4.3 Linear Probing의 Deletion 문제와 "Deleted" 플래그

 

작은 예시로, N=7, h(k)=k mod 7인 테이블에 10, 22, 17, 3, 16을 linear probing으로 순서대로 넣으면:

key	h(k)	probe 과정	최종 위치
10	3	A[3] 비어있음	3
22	1	A[1] 비어있음	1
17	3	A[3]참(10) → A[4] 비어있음	4
3	3	A[3]참(10) → A[4]참(17) → A[5] 비어있음	5
16	2	A[2] 비어있음	2

인덱스: 0  1  2  3  4  5  6
값:    -  22 16 10 17 3  -

 

 이제 key 17 (index 4)을 그냥 지워서 빈 칸으로 만든다고 하자. 그 상태에서 key 3을 search하면 어떻게 될까?

search 알고리즘은 "h(k)부터 시작해서, (1) 찾는 key를 발견하거나, (2) 빈 칸(empty)을 만나거나, (3) 모든 칸을 다 볼 때까지" probe를 계속한다.

• h(3)=3 → A[3]을 봄 → 값은 10 (3이 아니고, 비어있지도 않음) → 계속 진행
• A[4]를 봄 → 17을 지워서 비어있으니, "빈 칸을 만남" → search는 여기서 "못 찾음"으로 결론내려버림

 하지만 실제로 3은 A[5]에 있다! search는 A[5]까지 가보지도 못하고 A[4]의 빈 구멍에서 잘못된 결론을 내린 것이다.

해결책 — "deleted" 플래그(tombstone): A[4]를 "완전히 빈 칸(None)"이 아니라 "DELETED"라는 특수 표시로 남겨둔다. search 알고리즘이 A[4]에서 "DELETED" 표시를 보면 → "이건 빈 칸이 아니라 건너뛸 칸"이라고 판단하고 계속 probe → A[5]에서 3을 발견한다.

 즉, DELETED 칸은 "search 입장에서는 건너뛰지만(skip), insert 입장에서는 그 자리에 새로 써도 되는(writable)" 이중적인 상태다. 이 덕분에 search는 "진짜 빈 칸(한 번도 안 쓰인 칸)"에서만 멈추고, "한때 썼다가 지운 칸"은 통과해서 그 너머까지 계속 찾을 수 있다.

4.4 Double Hashing에서 h'(k) ≠ 0이어야 하는 이유

h'(k)=0이면 i·h'(k) = i·0 = 0이 되어, 모든 i에 대해:

i=0: A[(h(k) + 0) mod N] = A[h(k)]
i=1: A[(h(k) + 0) mod N] = A[h(k)]
i=2: A[(h(k) + 0) mod N] = A[h(k)]
...

 

 모든 probe가 똑같이 A[h(k)]만 가리킨다. 이미 A[h(k)]가 차있어서(충돌이 나서) probing을 시작한 건데, 모든 probe가 똑같이 A[h(k)]만 다시 확인하니 그 사실은 절대 바뀌지 않는다.

이건 단순히 "이름이 double hashing이 아니게 된다" 수준의 문제가 아니다. 테이블의 나머지 칸들이 다 비어있어도 상관없이, search/insert가 절대 종료되지 않는 무한루프에 빠지는 치명적인 버그다. 그래서 h'(k)≠0은 반드시 지켜야 하는 제약이다.

---

5. 다시 Sorted Map — 그리고 다음으로

5.1 Hash Table vs Sorted Map: "전반적으로 더 나은 쪽"은 없다

다음 세 연산을 hash table과 sorted search table에서 각각 비교해보면:

연산	Hash Table	Sorted Search Table
M[k] (정확한 key 조회)	O(1) 평균 — hash table의 본업!	O(log n) — binary search
find_min()	O(n) — 순서 정보 없어서 전부 훑어봐야 함	O(1) — A[0]
find_ge(k) (k 이상의 최소 key)	O(n)	O(log n) — binary search

 

중요한 포인트: "hash table이 전반적으로 더 나쁘다"가 아니다. "정확한 key 조회"는 hash table이 압도적으로 빠르고(O(1)), "순서 기반 조회"는 sorted map만 효율적으로 가능하다(hash table은 O(n)) — 이건 trade-off다. 어느 쪽을 쓸지는 "어떤 연산을 더 자주 하느냐"에 따라 결정된다.

5.2 실전 예시: 항공편 검색 시스템

key = (출발지, 도착지, 날짜, 출발시간), value = (항공편 번호, 좌석수, 가격 등)인 항공편 데이터베이스를 생각해보자. 사용자가 "ORD→PVD, 5월 5일, 9:30~20:00 사이의 항공편을 모두 보여줘"라고 요청한다.

key는 튜플이고, 사전식(lexicographic) 순서로 비교된다 — 첫 번째 요소(출발지)부터 비교하고, 같으면 다음 요소(도착지)를, 또 같으면 다음(날짜)을... 이런 식이다. 그래서 정렬된 배열에서는:

... (ORD, PVD, 05May, 09:53) (ORD, PVD, 05May, 13:29) (ORD, PVD, 05May, 17:39) (ORD, PVD, 05May, 19:50) (ORD, PVD, 06May, ...) ...

 

ORD→PVD, 5월 5일 항공편들이 시간 순서대로 한 덩어리(연속된 구간)로 모여있다.

find_range(k1, k2) 동작 과정:

1. find_ge(k1) — k1=(ORD,PVD,05May,09:30)보다 크거나 같은 첫 key를 binary search로 O(log n)에 찾는다 (정확히 09:30짜리가 없어도, inexact search로 09:53짜리를 찾아준다)
2. 그 위치부터 순서대로 읽어나가면서, key가 k2=(...,20:00)을 넘어가기 전까지 결과에 포함시킨다

시작 위치 → (ORD,PVD,05May,09:53): AA1840  ✓
다음      → (ORD,PVD,05May,13:29): AA600   ✓
다음      → (ORD,PVD,05May,17:39): AA416   ✓
다음      → (ORD,PVD,05May,19:50): AA1828  ✓
다음      → (ORD,PVD,06May,...): ...       ✗ (20:00 넘어감 → 멈춤)

시간복잡도: 1단계 O(log n) + 2단계 O(s) (s=결과 개수) = O(log n + s).

 

왜 hash table로는 안 되는가: hash table에서는 (ORD,PVD,05May,09:53)과 (ORD,PVD,05May,13:29)이 전혀 다른, 멀리 떨어진 bucket에 있을 수 있다. "비슷한 key들이 배열에서 흩어져 있어서", 범위 검색을 하려면 전체를 O(n)으로 훑어서 각 항목의 key가 범위 안에 드는지 일일이 확인하는 수밖에 없다.

5.3 전체 흐름 정리

Map의 가장 단순한 구현(unsorted/sorted table)은 항상 어딘가에서 O(n)이 발생한다는 한계가 있다. Hash Table은 hash function을 이용해 key를 배열 인덱스로 직접 연결함으로써, "정확한 key로 조회/삽입/삭제"에 대해 평균 O(1)을 달성한다. 하지만 그 과정에서 key들 사이의 순서 정보를 완전히 잃어버려서, 최소/최대값이나 특정 범위의 key를 찾는 연산은 여전히 O(n)이다. Sorted Map(sorted search table)은 key를 정렬된 순서로 저장해 binary search를 활용함으로써 이런 순서 기반 연산을 O(log n)에 처리할 수 있게 한다. 하지만 배열 기반이라는 한계 때문에 insert/delete는 여전히 O(n)이다(shifting).