B-트리·해시 테이블·스킵 리스트·블룸 필터

해싱·스킵 리스트·블룸 필터 (Hashing, skip lists, Bloom filters)

1타 강사식 학습 동선

직관 → 조작 → 예시 → 함정 → 답안

Hash table(Hashtabelle)은 key를 hash function h로 bucket index에 보내 exact dictionary operation을 빠르게 하려는 구조입니다. Skip list(Skip-Liste)는 정렬 linked list 위에 random shortcut levels를 쌓아 or...

\(해시 테이블(\text{Hash} \text{table}): h: U \rightarrow \{0,...,m-1\}\)해시 테이블(Hash table): h: U → {0,...,m-1}\(적재율(\text{load} \text{factor}): \text{alpha} = n / m\)적재율(load factor): alpha = n / m\(체이닝(\text{chaining}): 기대 버킷 길이 = \text{alpha}\)체이닝(chaining): 기대 버킷 길이 = alpha\(스킵 리스트(\text{skip} \text{list}): E[|L_{i}|] = p^{i} n\)스킵 리스트(skip list): E[|Lᵢ|] = p^i n\(스킵 리스트의 기대 높이: O(\log_{1/p} n)\)스킵 리스트의 기대 높이: O(log₁/p} n)

연습으로 이동 개인화 순서 보기

01 직관이 개념이 왜 필요한지 한 문장으로 잡기

02 손풀이그래프, 트리, 표, 문자열을 직접 움직이며 확인하기

03 단계별 예제시험 답안처럼 조건과 결론을 연결하기

04 함정 점검자주 틀리는 조건과 반례를 먼저 차단하기

출처에 근거한 강의

세 구조를 한 문장씩 분리하기

해시 테이블(Hash table, Hashtabelle), 스킵 리스트(skip list, Skip-Liste), 블룸 필터(Bloom filter, Bloom-Filter)는 모두 조회(lookup)를 빠르게 만들지만, 보장하는 성질은 서로 다릅니다.

해시 테이블(Hash table)

키(key)를 해시 함수(hash function) h로 버킷 배열(bucket array) T[0..m-1]의 인덱스에 보냅니다. 목표는 정확한 사전 연산(exact dictionary operation), 즉 넣은 키를 정확히 다시 찾는 것입니다.

스킵 리스트(Skip list)

맨 아래에는 모든 키가 정렬 연결 리스트(sorted linked list)로 있고, 위에는 일부 키만 무작위로 올라간 빠른 길(express list)이 있습니다. 목표는 순서를 보존하는 정확한 탐색(ordered exact search)입니다.

블룸 필터(Bloom filter)

값 자체를 저장하지 않고 비트 증거(bit evidence)만 저장합니다. 목표는 메모리를 아끼는 소속 여부 사전 검사(membership pre-check)입니다. 그래서 ‘예’와 ‘아니요’의 의미가 정확한 사전과 다릅니다.

출처: Vorlesung\05RandomizedDataStructures-wi.pdf 9, 20, 25~31, 34, 39~45쪽; Übung\AuD26_Sheet08.pdf G4~G5; Übung\AuD26_Sheet08-Sol.pdf 7~12쪽; 같은 파일의 구간을 담은 \(\text{data}/\text{aud}_{\text{chunks}}.\text{jsonl}\)data/aud(chunks).jsonl.

기호부터 이해하기

시험 전에 눈에 고정해야 할 공식

공식은 계산용이기 전에 말로 설명할 수 있어야 합니다.

해시 함수와 적재율

해시 테이블은 키의 전체 집합(key universe)에서 버킷 번호로 값을 보냅니다.

\[h:U\to\{0,\ldots,m-1\},\qquad \alpha=\frac{n}{m}\]h: U → {0,…,m−1}, 적재율 α = n/m

n: 저장된 원소 수
m: 버킷 수이며, 보통 T.length
alpha: 적재율(load factor, Lastfaktor)

alpha가 커지면 충돌 가능성이 커지고, 체이닝 목록(chaining list)의 기대 길이도 커집니다.

체이닝의 기대 비용

균등하고 독립적인 해싱(uniform and independent hashing)을 가정하면 한 버킷의 기대 원소 수가 alpha입니다.

\[\mathbb{E}[|B|]=\frac{n}{\operatorname{length}(T)}=\alpha\]기대 버킷 길이 E[|B|] = n / 테이블 길이 = α

탐색·삭제는 해당 버킷 목록을 훑으므로 기대 비용(expected cost)이 버킷 길이와 연결됩니다.

기댓값과 최악의 경우

해시 테이블의 \(O(1)\)O(1)은 항상 최악의 경우(worst case)에도 성립한다는 뜻이 아닙니다.

\[\mathbb{E}[T]=\Theta(1+\alpha),\qquad T_{\max}=\Theta(n)\]기대 시간 E[T] = Θ(1+α), 최악 시간 Tₘₐₓ = Θ(n)

강의 슬라이드 34의 표는 평균(im Durchschnitt) 성능을 별표로 표시합니다. 체이닝의 맨 앞 삽입은 최악의 경우에도 \(\Theta(1)\)Θ(1)이지만, 탐색·삭제 보장은 분포 가정(distribution assumption)에 의존합니다.

스킵 리스트의 레벨 크기

각 원소가 확률 p로 한 레벨 위에 다시 등장한다고 생각합니다.

\[\mathbb{E}[|L_{i}|]=p^{i}n\]i번째 레벨의 기대 크기 E[|Lᵢ|] = pⁱn

레벨이 올라갈수록 기대 노드 수가 기하급수적으로 줄어 빠른 길(express lane)이 됩니다.

스킵 리스트의 높이와 공간

위 레벨로 승격(promotion)이 계속 성공할 확률은 작아집니다.

\[\mathbb{E}[h]=O\!\left(\log_{1/p}n\right),\qquad n+pn+p^{2}n+\cdots=\frac{n}{1-p}\]기대 높이 E[h] = O(log₁⁄ₚ n), 기대 공간 합 = n/(1−p)

고정된 p에서는 기대 공간이 \(\Theta(n)\)Θ(n)입니다. 중요한 표현은 결정적 최악의 경우가 아니라 기댓값(expected, im Durchschnitt)입니다.

블룸 필터 삽입

블룸 필터는 값을 직접 넣지 않고 k개의 비트 위치(bit position)만 켭니다.

\[\forall j\in\{0,\ldots,k-1\}:\quad \mathrm{BF}[H_{j}(x)]\leftarrow 1\]모든 j=0,…,k−1에 대해 BF[Hⱼ(x)] 비트를 1로 설정합니다.

이미 1인 비트를 다시 1로 만들 수 있습니다. 이러한 비트 공유가 나중에 거짓 양성(false positive)을 만듭니다.

블룸 필터 질의

탐색은 모든 증거 비트가 1인지 논리곱(AND)으로 확인합니다.

\[\operatorname{result}=\bigwedge_{j=0}^{k-1}\mathrm{BF}[H_{j}(y)]\]결과 = BF[H₀(y)] ∧ ⋯ ∧ BF[Hₖ₋₁(y)]

결과가 0이면 확실히 없음(definitely absent), 1이면 있을 수도 있음(may be present)입니다. 이 방향을 뒤집으면 객관식에서 바로 틀립니다.

블룸 필터 매개변수 힌트

강의 자료 39쪽은 흔히 권장되는 다음 관계를 제시합니다.

\[k=\frac{m}{n}\ln 2,\qquad \varepsilon\approx 2^{-k}\]권장 해시 수 k = (m/n) ln 2, 오류율 ε ≈ 2⁻ᵏ

계산보다 중요한 시험 핵심은 거짓 양성이 생길 수 있음과 기본 삽입 전용 블룸 필터에는 거짓 음성이 없음입니다.

1. 해시 테이블: 정확한 사전을 위한 빠른 주소 계산

해시 테이블의 첫 아이디어는 목록이나 트리처럼 비교하며 내려가는 대신, 키에서 버킷 번호를 바로 계산하는 것입니다. 강의 자료 25쪽의 그림처럼 데이터 집합의 원소 x, y, z가 해시 함수 h를 지나 배열 T의 칸(slot)으로 들어갑니다. 이때 좋은 해시 함수는 값을 균등하고 독립적으로(uniform and independent) 퍼뜨려야 합니다.

하지만 버킷 수는 유한하고 키의 전체 집합은 보통 훨씬 큽니다. 따라서 서로 다른 키 x와 y가 같은 버킷에 도착할 수 있습니다. 이것이 충돌(collision, Kollision)입니다. 충돌은 오류가 아니라 정상 상황입니다. 자료구조는 충돌이 생겨도 나중에 탐색이 삽입 때 사용한 경로를 다시 따라가도록 불변식(invariant)을 유지해야 합니다.

체이닝(Chaining, Verkettung)

각 버킷이 연결 리스트의 머리 포인터(head pointer)를 저장합니다. 같은 해시값을 가진 모든 원소는 그 목록에 들어갑니다. Sheet08 해설 8쪽은 새 원소를 목록의 맨 앞에 넣는다고 설명합니다.

개방 주소법(Open addressing, offene Adressierung)

이 페이지의 연습문제는 체이닝을 쓰지만, 개념적으로는 탐사 순서(probing sequence)를 따라 빈 칸을 찾는 방식도 있습니다. 탐색과 삭제는 탐사 순서를 끊지 않아야 하므로 삭제 표시(tombstone 또는 deleted marker)가 필요할 수 있습니다.

해시는 암호화가 아닙니다

강의 자료 31쪽은 암호학적 해시 함수(cryptographic hash function)를 언급하지만, AUD 해시 테이블의 핵심은 비밀성(secrecy)이 아니라 버킷으로의 분배입니다. MD5/SHA 이야기를 사전 연산의 실행 시간 보장과 섞지 마세요.

Sheet08 방식의 풀이 예시

Sheet08 해설 G4는 \(T.\text{length} = 8\)T.length = 8과 곱셈 방식의 해시 함수를 사용한 뒤 키 16, 34, 50, 7, 22, 14, 49, 33, 40, 11, 3, 2를 삽입합니다. 예를 들어 해설은 \(h(16)=7\)h(16)=7, \(h(34)=0\)h(34)=0, \(h(50)=7\)h(50)=7, \(h(7)=2\)h(7)=2를 계산합니다. 따라서 맨 앞 삽입 뒤 버킷 7에는 50과 16의 체인이 생깁니다. 50을 삭제하면 머리 포인터 T[7]은 16으로 이동합니다. 55는 버킷 7에 없는 키이므로 삭제해도 아무것도 바뀌지 않습니다.

삭제(delete)는 먼저 h(key)를 다시 계산하고 해당 버킷 목록만 확인합니다. 없는 키를 삭제하려고 해도 테이블 전체를 망가뜨리지 않습니다. 객관식 함정은 “삭제가 실패했으니 상태가 어떻게든 변한다”가 아니라, 해당 체인에 키가 없으면 아무 작업도 하지 않는다는 점입니다.

2. 스킵 리스트: 정렬 목록 위의 무작위 빠른 길

스킵 리스트는 정렬 연결 리스트의 단점에서 출발합니다. 정렬 목록에서 탐색·삭제·삽입은 최악의 경우 \(\Omega(n)\)Ω(n)입니다. 강의 자료 5쪽은 일부 원소만 담은 빠른 목록(express list)을 위에 하나 얹는 아이디어를 보여 줍니다. 7~12쪽은 이 아이디어를 반복해 여러 레벨을 만들고, 각 원소가 확률 p로 위 레벨에 선택된다고 설명합니다.

탐색 알고리즘은 강의 자료 9쪽의 의사코드를 기준으로 이해하면 됩니다. 현재 노드에서 시작해 현재 키가 목표값이면 반환합니다. 다음 노드가 있고 \(\text{next}.\text{key} \le k\)next.key ≤ k이면 오른쪽으로 갑니다. 그렇지 않으면 아래로 내려갑니다. 마지막에 nil이면 해당 키가 없다는 뜻입니다.

\[\begin{aligned}\operatorname{next}(u)\ne\mathrm{nil}\ \land\ \operatorname{key}(\operatorname{next}(u))\le k &\Longrightarrow \text{오른쪽으로 이동},\\ \operatorname{next}(u)=\mathrm{nil}\ \lor\ \operatorname{key}(\operatorname{next}(u))>k &\Longrightarrow \text{아래로 이동}.\end{aligned}\]다음 키가 k 이하이면 오른쪽, 다음 노드가 없거나 다음 키가 k보다 크면 아래로 이동합니다.

이 규칙이 목표값을 건너뛰지 않는 이유는 간단합니다. 오른쪽으로 갈 때 다음 키는 여전히 목표값 이하입니다. 다음 키가 목표값보다 크면 그 오른쪽의 값들도 정렬 순서상 더 크므로, 같은 레벨에서는 더 갈 수 없습니다. 따라서 아래 레벨로 내려가 더 촘촘한 목록에서 계속 찾습니다.

삽입 레벨 결정

먼저 맨 아래 레벨에서 정렬된 위치를 찾아 삽입합니다. 그다음 난수가 p보다 작으면 위 레벨에도 복사본을 올립니다. 이 과정을 처음 실패할 때까지 반복합니다.

Sheet08의 난수

Sheet08은 \(p=1/2\)p=1/2과 난수열 0.43, 0.59, 0.87, 0.49, 0.12, 0.26, 0.69를 사용합니다. 난수가 p보다 작은 동안 해당 값을 위 레벨로 승격합니다.

결정적 보장이 아닌 기댓값

강의 자료 21쪽은 로그 실행 시간이 평균(im Durchschnitt)에만 해당한다고 명시합니다. 23쪽은 완전한 결정적 스킵 리스트와 무작위 스킵 리스트를 비교합니다.

Sheet08 탐색 경로 연습

주어진 스킵 리스트에서 해설 9쪽은 78 탐색에 6단계, 10 탐색에 3단계, 63이 없음을 확인하는 데 7단계가 걸린다고 설명합니다. 비교 횟수만 무작정 세지 마세요. 다음 키가 목표값을 넘지 않는 동안 오른쪽으로 가고, 넘을 것 같으면 아래로 내려가며, 맨 아래 위치에서 부재가 확인되면 nil로 끝나는 경로를 추적해야 합니다.

33 삽입은 승격 과정을 보여 주는 좋은 예입니다. 33은 31과 34 사이에 들어갑니다. 난수 0.49, 0.12, 0.26은 모두 p보다 작으므로 33이 여러 빠른 목록에 삽입되고, \(0.69 > p\)0.69 > p에서 승격이 멈춥니다. 기존 최상위 레벨이 없다면 목록이 위로 한 층 늘어납니다.

3. 블룸 필터: 정확한 저장이 아닌 압축된 증거

강의 자료 35쪽은 블룸 필터를 “작은 오류를 허용하는 메모리 절약형 사전(speicherschonende Wörterbücher mit kleinem Fehler)”이라고 부릅니다. 이 표현은 오해하기 쉽습니다. 이 구조는 소속 여부를 미리 검사한다는 점에서 사전과 비슷하지만 원래 원소를 저장하지 않고, 길이 m의 비트 배열에 증거 비트만 저장합니다.

초기화는 모든 비트를 0으로 만듭니다. Insert(x)는 \(H_{0}(x),\ldots,H_{k-1}(x)\)H₀(x),…,Hₖ₋₁(x)를 계산하고 그 위치를 모두 1로 만듭니다. Search(y)는 같은 k개 위치를 계산해 비트의 논리곱을 반환합니다. 강의 자료 42쪽은 거짓 음성이 없음을 증명합니다. 실제로 y를 삽입했다면 삽입 과정에서 y에 필요한 모든 비트를 켰기 때문입니다. 43쪽은 삽입하지 않은 y의 모든 비트 위치를 다른 값들이 우연히 켜서 생기는 거짓 양성을 보여 줍니다.

‘아니요’는 확실한 부재

확인한 비트 중 하나라도 0이면 y는 삽입된 적이 없습니다. y를 삽입했다면 그 비트가 반드시 1이 되었어야 하기 때문입니다. 따라서 결과 0은 확실히 없음(definitely absent)을 뜻합니다.

‘예’는 존재 가능성

확인한 비트가 모두 1이면 y가 있을 수도 있습니다. 다른 원소들이 같은 비트를 켜서 만든 거짓 양성일 수도 있습니다.

삭제 함정

강의 자료 45쪽과 Sheet08 G5(c)는 삭제를 묻습니다. 비트를 단순히 0으로 되돌리면 다른 원소의 증거까지 지워서 거짓 음성이 생길 수 있습니다. 계수 블룸 필터(Counting Bloom filter)는 단일 비트 대신 계수기를 사용하므로 삭제가 가능하지만 메모리 사용량이 늘어납니다.

Sheet08 블룸 필터 계산 유형

Sheet08 G5는 16비트 블룸 필터와 ASCII 코드에 기반한 세 해시 함수를 사용합니다. 해설 11쪽은 [A,u,D]에 대해 \(H1=10\)H1=10, \(H2=4\)H2=4, \(H3=2\)H3=2를 계산한 뒤 10, 4, 2번 비트를 켭니다. 이어서 [B,l,o,o,m]과 [B,a,u,m]을 삽입하고 [H,a,s,h]와 [G,r,a,p,h]를 질의합니다.

중요한 시험 답은 “비트 배열이 …가 된다”에서 끝나지 않습니다. 질의 뒤에는 결과의 의미를 말해야 합니다. 세 위치가 모두 1이면 ‘있을 가능성이 있음’이지 존재가 보장되는 것은 아닙니다. 하나라도 0이면 그 문자열은 표현된 집합에 확실히 없습니다.

4. 세 자료구조 한눈에 비교하기

자료구조	실제 원소 저장 여부	순서·범위 질의 지원	핵심 실행 시간	주요 함정
해시 테이블	예. 정확한 키·레코드를 저장	정렬된 이웃 순회는 자연스럽지 않으며, 범위 질의에는 트리가 더 적합	좋은 해싱과 `n`에 가까운 테이블 크기에서 평균·기댓값 \(\Theta(1)\)`Θ(1)`	최악의 경우 \(\Theta(n)\)`Θ(n)`이 될 수 있음
스킵 리스트	예. 정확한 정렬 키를 저장	예. 정렬 순서를 보존	탐색·삽입·삭제의 기댓값 \(\Theta(\log_{1/p}n)\)`Θ(log₁⁄ₚ n)`	무작위 스킵 리스트는 결정적 최악의 경우 \(O(\log n)\)`O(log n)`을 보장하지 않음
블룸 필터	아니요. 비트 증거만 저장	아니요. 소속 여부 사전 검사만 지원	`k`번의 해시와 `k`번의 비트 검사, 적은 메모리	‘예’는 있을 수도 있음, ‘아니요’는 확실히 없음

5. 객관식 함정과 바로잡기

함정 1

주장: 해시 테이블 탐색은 항상 \(O(1)\)O(1)이다.
바로잡기: 기대·평균 \(O(1)\)O(1)에는 좋은 분포와 통제된 alpha가 필요하며, 최악의 경우 \(\Theta(n)\)Θ(n)도 가능합니다.

함정 2

주장: 충돌은 해시 함수가 실패했다는 뜻이다.
바로잡기: 충돌은 정상입니다. 자료구조는 체이닝, 개방 주소법 또는 다른 충돌 해결 전략으로 이를 처리해야 합니다.

함정 3

주장: 암호학적 해시를 쓰면 자동으로 좋은 해시 테이블이 된다.
바로잡기: AUD 실행 시간 분석은 비밀성이 아니라 버킷으로의 분포를 봅니다. 강의는 주의 조건과 함께 암호학적 해시를 가능한 해시 함수로 언급할 뿐입니다.

함정 4

주장: 스킵 리스트의 \(O(\log n)\)O(log n)은 결정적 최악의 경우 성능이다.
바로잡기: 무작위 스킵 리스트의 로그 성능은 평균·기댓값(im Durchschnitt)입니다.

함정 5

주장: 스킵 리스트의 기대 공간은 \(\Theta(n \log n)\)Θ(n log n)이다.
바로잡기: 기대 공간은 n/(1-p)이므로 고정된 p에서 \(\Theta(n)\)Θ(n)입니다.

함정 6

주장: 블룸 필터의 ‘예’는 원소가 확실히 있다는 뜻이다.
바로잡기: ‘예’는 있을 수도 있다는 뜻이며, 거짓 양성이 가능합니다.

함정 7

주장: 블룸 필터의 ‘아니요’는 거짓 음성일 수 있다.
바로잡기: 기본 삽입 전용 블룸 필터에서 ‘아니요’는 확실한 부재를 뜻하며 거짓 음성이 없습니다.

함정 8

주장: 블룸 필터에서 k개 비트를 0으로 만들면 삭제할 수 있다.
바로잡기: 다른 원소와 공유한 증거까지 지워 거짓 음성을 만들 수 있습니다. 삭제가 필요하면 계수 블룸 필터를 사용합니다.

함정 9

주장: 어떤 두 블룸 필터든 논리합(OR)하면 합집합이 된다.
바로잡기: 두 필터의 m과 해시 함수가 같아야 합니다. 그렇지 않으면 같은 비트 위치가 서로 다른 뜻을 가집니다.

6. 능동 회상: 입으로 답하기

해시 테이블을 \(h: U \rightarrow \{0,...,m-1\}\)h: U → {0,...,m-1}, 버킷 배열, 충돌이라는 단어로 정의하세요.
체이닝의 충돌 처리 불변식을 말하세요. 탐색이 삽입 때 놓은 키를 다시 찾을 수 있는 이유는 무엇인가요?
\(\text{alpha} = n/m\)alpha = n/m이 무엇이고, 기대 버킷 길이와 어떻게 연결되는지 설명하세요.
“해시 테이블 연산은 \(\Theta(1)\)Θ(1)이다”라는 문장을 기댓값, 평균, 최악의 경우로 나누어 정확히 고쳐 말하세요.
스킵 리스트의 맨 아래 레벨 불변식과 위 레벨 탑(tower) 불변식을 말하세요.
스킵 리스트 탐색에서 언제 오른쪽으로 가고 언제 아래로 내려가나요? 목표값을 건너뛰지 않는 이유는 무엇인가요?
\(\mathbb{E}[|L_{i}|]=p^{i}n\)E[|Lᵢ|]=pⁱn을 무작위 승격으로 설명하세요.
Sheet08의 \(p=1/2\)p=1/2 난수열에서 33이 여러 레벨로 올라가는 이유를 설명하세요.
블룸 필터의 삽입과 질의 의사코드를 \(\mathrm{BF}[H_{j}(x)]\)BF[Hⱼ(x)] 표기법으로 쓰세요.
블룸 필터에서 거짓 양성이 생기는 정확한 상황을 비트 증거로 설명하세요.
기본 삽입 전용 블룸 필터에 거짓 음성이 없는 이유를 한 문단으로 증명하세요.
계수 블룸 필터가 삭제를 가능하게 하는 방법과 메모리 비용이 늘어나는 이유를 설명하세요.
세 구조를 정확성, 정렬 순서, 기대·최악 성능 보장, 메모리 절충의 관점에서 비교하세요.

심화 연습용 AI 프롬프트

Vorlesung/05RandomizedDataStructures-wi.pdf, Übung/AuD26_Sheet08.pdf, Übung/AuD26_Sheet08-Sol.pdf와 data/aud_chunks.jsonl의 관련 구간을 첨부하세요.

AUD 시험을 대비해 해싱, 스킵 리스트, 블룸 필터를 한국어로 가르치고 중요한 독일어·영어 용어는 괄호에 병기하세요. 먼저 보장의 차이를 설명하세요. 해시 테이블은 정확한 사전(exact dictionary), 스킵 리스트는 순서를 보존하는 정확한 무작위 구조, 블룸 필터는 근사 소속 여부 사전 검사입니다. 이어서 다음 내용을 연습하세요.
- 해시 함수 h: U -> {0,...,m-1}, 충돌 처리, 체이닝, 개방 주소법의 주의점, 적재율 alpha = n/m, 기대 버킷 길이, 기대 실행 시간과 최악의 경우 실행 시간
- 스킵 리스트 레벨, 오른쪽·아래 방향 탐색, 승격 확률 p, E[|L_i|] = p^i n, 기대 높이·탐색·공간, Sheet08의 p=1/2 삽입·탐색 예시
- 블룸 필터의 m비트 배열, k개 해시 함수, 삽입·질의 의사코드, 예·아니요의 의미, 거짓 양성·거짓 음성, 삭제와 계수 블룸 필터
- 객관식 함정과 능동 회상 문제를 한 번에 하나씩 제시

엄격하게 채점하고, 교정할 때는 출처 파일명과 페이지 구간을 인용하세요.

수식 표기

읽는 순서가 보이는 핵심 공식

정의, 수식, 시험 판정 문장을 분리해서 공식이 답안에서 어떻게 쓰이는지 바로 확인합니다.

해시 테이블 적재율(Hash table load factor)

Hash table이 얼마나 찼는지 보는 값입니다. Collision과 chaining list 길이를 예측할 때 먼저 봅니다.

\[\alpha = \frac{n}{m}\]\alpha = \frac{n}{m}

n은 저장된 원소 수, m은 bucket 수입니다. alpha가 커지면 평균 bucket length와 collision cost가 커집니다.

기대 버킷 길이(Expected bucket length)

Uniform hashing 가정에서는 한 bucket에 들어가는 원소 수의 기대값이 load factor와 같습니다.

\[\mathbb{E}[\text{bucket length}] = \frac{n}{T.\text{length}} = \alpha\]\mathbb{E}[\text{bucket length}] = \frac{n}{T.length} = \alpha

Chaining에서 search/delete는 bucket list를 따라가므로 이 값이 성능 직관입니다.

해시 테이블 연산 시간(Hash table operation time)

Bucket을 계산하는 상수 비용과 bucket 내부를 보는 비용을 합칩니다.

\[\Theta(1 + \alpha)\ \text{expected};\quad \Theta(n)\ \text{worst case}\]\Θ(1 + \alpha)\ \text{expected};\quad \Θ(n)\ \text{worst case}

시험에서는 \(O(1)\)O(1)이 worst-case guarantee인지 expected statement인지 반드시 구분합니다.

스킵 리스트 레벨 크기(Skip-list level size)

각 원소가 확률 p로 한 level 더 올라간다고 보면 i번째 level에 남는 원소 수가 기하급수적으로 줄어듭니다.

\[\mathbb{E}[|L_{i}|] = p^{i} n\]\mathbb{E}[|Lᵢ|] = p^{i} n

이 감소가 express lane intuition이고, 높은 level이 sparse해지는 이유입니다.

스킵 리스트의 높이와 공간(Skip-list height and space)

Random promotion이 계속 성공할 확률이 줄어들기 때문에 높이는 logarithmic, 공간은 linear expectation입니다.

\[\mathbb{E}[h] = O(\log_{1/p} n),\quad n + \text{pn} + p^{2}n + \cdots = \frac{n}{1-p}\]\mathbb{E}[h] = O(\log₁/p} n),\quad n + pn + p²n + \cdots = \frac{n}{1-p}

고정된 p에서는 expected space가 \(\Theta(n)\)Θ(n)입니다. Standard skip list의 log bound는 expected/im Durchschnitt입니다.

블룸 필터 삽입(Bloom filter insert)

Bloom filter는 값을 저장하지 않고 여러 hash 위치의 bit를 evidence로 켭니다.

\[\forall j \in \{0,\dots,k-1\}: \mathrm{BF}[H_{j}(x)] \leftarrow 1\]\forall j \in \{0,\dots,k-1\}: \mathrm{BF}[Hⱼ(x)] \leftarrow 1

같은 x를 나중에 query하면 insert 때 켠 모든 위치가 1이므로 insert-only 구조에서 false negative가 나오지 않습니다.

블룸 필터 질의(Bloom filter query)

Query는 모든 evidence bit가 1인지 AND로 확인합니다.

\[\bigwedge_{j=0}^{k-1} \mathrm{BF}[H_{j}(y)]\]\bigwedgeⱼ=0}ᵏ-1} \mathrm{BF}[Hⱼ(y)]

하나라도 0이면 definitely absent입니다. 모두 1이면 may be present일 뿐이며, 다른 원소들이 같은 bit를 켠 false positive일 수 있습니다.

블룸 필터 매개변수 힌트(Bloom filter parameter hint)

세부 유도는 강의 자료의 표기법을 다시 확인해야 하지만, 일반적으로 사용하는 최적 해시 함수 개수 관계는 다음과 같습니다.

\[k = \frac{m}{n}\ln 2,\quad \Pr[\text{거짓 양성}] \approx 2^{-k}\]k = \frac{m}{n}\ln 2,\quad \Pr[\text{거짓 양성}] \approx 2^{-k}

출처 확인 필요: 슬라이드의 정확한 표기는 다를 수 있습니다. 시험에서는 '예/아니요'의 의미와 거짓 양성이 가능한 방향을 정확히 말하는 것이 핵심입니다.

선수 개념과 필수 용어 (Prerequisites and Vocabulary)

사전 연산(Dictionary operations): 탐색·삽입·삭제와 정확한 소속 질의·근사 소속 질의의 차이.
확률 용어: 기대 실행 시간(expected Laufzeit), 무작위 승격(random promotion), 거짓 양성(false positive)과 거짓 음성(false negative).
배열·목록 기초: 버킷 배열(bucket array), 연결 리스트 체이닝(linked-list chaining), 정렬 연결 리스트(sorted linked list).
전제를 포함한 점근 표기: 기대 \(O(1)\)O(1), 기대 \(O(\log n)\)O(log n), 최악의 경우 \(\Theta(n)\)Θ(n).

핵심 학습 항목 (Active Recall With Hints)

1

h, 키 전체 집합(key universe), 버킷 배열, 충돌을 사용해 해시 테이블(Hashtabelle)을 정의하세요.

2

체이닝과 개방 주소법 각각의 충돌 처리 불변식을 말하세요.

3

α=n/m을 설명하고 기대 버킷 길이 및 탐색·삭제 실행 시간과 연결하세요.

4

해시 테이블 \(O(1)\)O(1)이 최악 보장이 아님을 보여 주는 반례를 드세요.

5

스킵 리스트(Skip-Liste)를 정의하고 맨 아래 레벨의 정렬 불변식을 말하세요.

6

오른쪽·아래 탐색 규칙과 그 규칙이 목표를 건너뛰지 않는 이유를 설명하세요.

7

\(E[|L_{i}|]=p^{i} n\)E[|Lᵢ|]=p^i n과 기대 공간 n/(1-p)를 말로 유도하세요.

8

\(p=0.33\)p=0.33이고 난수가 0.09, 0.18, 0.39일 때 새 키가 몇 레벨에 나타나는지 말하세요.

9

\(\text{BF}[H_{j}(x)]\)BF[Hⱼ(x)]표기로 블룸 필터의 삽입과 질의를 쓰세요.

10

블룸 필터가 언제 '확실히 없음(definitely absent)'이라고 답할 수 있는지 설명하세요.

11

비트 배열 예시로 거짓 양성(false positive)을 설명하세요.

12

기본 삽입 전용 블룸 필터에 거짓 음성이 없는 이유를 증명하세요.

13

단순 삭제가 블룸 필터의 정확성을 깨뜨리는 이유를 설명하세요.

14

구두시험: 세 구조를 정확성, 순서 지원, 실행 시간, 메모리 절충으로 비교하세요.

15

구두시험: '블룸 필터가 예라고 했으니 원소가 집합에 있다'라는 문장을 바로잡으세요.

초보자 강의 확인

그림으로 이해하고 말로 확인하기

해시 테이블 그림

키는 해시 함수 h(key)를 거쳐 하나의 버킷으로 이동합니다. 충돌은 그 버킷 안의 연결 구조나 탐사 순서에서 처리합니다.

스킵 리스트 그림

정렬된 맨 아래 길 위에 무작위로 만든 급행 차선이 놓여 있다고 생각합니다. 찾는 값을 지나치기 직전까지 오른쪽으로 가고, 지나칠 것 같으면 아래로 내려갑니다.

블룸 필터 그림

이 구조는 원소 자체가 아니라 비트로 된 흔적만 저장합니다. 확인한 비트 중 하나라도 0이면 확실히 없고, 모두 1이면 있을 가능성만 있습니다.

말로 확인하기: 정확한 사전 조회, 순서를 유지하는 무작위 조회, 확률적 소속 사전 검사를 1분 안에 서로 비교해 보세요.

다음 튜터 프롬프트

마지막 생성: 2026-08-03 03:24