Skip-Listen, Hashing und Bloom-Filter
확률적 리스트, hashing, Bloom filter
중요한 독일어·영어 용어는 유지하되 설명과 학습 동선은 한국어 중심으로 제공합니다.
이 챕터의 문항별 독립 학습 페이지
단원 페이지에는 개요와 학습 순서만 둡니다. 각 문항의 용어·비유·수식·단계별 풀이·실제 채점은 아래 독립 페이지에서 이어집니다.
I-6 · 1개 선택
표준 Bloom filter 검색에서 가능한 오류는 무엇인가?
독립 개념 강의와 실제 채점 열기 →II-1 · 2개 선택
n개 원소와 승격 확률 p를 갖는 skip list에 관한 옳은 설명 두 개를 고르시오.
독립 개념 강의와 실제 채점 열기 →II-8 · 2개 선택
해시 테이블과 해시 함수에 관한 옳은 설명 두 개를 고르시오.
독립 개념 강의와 실제 채점 열기 →
30초 핵심 요약
스킵 리스트(skip list)는 확률 p로 노드를 상위 레벨에 복제한다. 해시 테이블(hash table)은 결정적 해시 함수로 키를 버킷에 매핑한다. 블룸 필터(Bloom filter)는 k개 해시 함수가 가리키는 비트로 원소의 포함 여부를 근사 판정한다.
스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
평균·최악·기대 중 무엇을 묻는지, 확률 p의 역할, 충돌 처리 전제, 거짓 양성(false positive)과 거짓 음성(false negative)의 방향을 확인한다.
시험 연결
- I-6
- II-1
- II-8
I부는 정확히 1개(exactly one), II부는 정확히 2개(exactly two)를 고른다. 복기 오류 가능성은 별도 경고로 표시한다.
정답 위치가 아니라 정의, 전제, 반례를 이용해 새 문장을 판정한다.
먼저 알아야 할 용어와 전제
- 기대값
- 기하급수
- 해시 충돌
- 비트 배열
개념 강의
스킵 리스트(skip list)는 여러 높이의 고속도로 진입 램프처럼 일부 노드를 건너뛰게 한다. 블룸 필터(Bloom filter)는 '확실히 없음' 또는 '아마 있음'만 말해 주는 스탬프 판과 같다.
스킵 리스트는 확률 p로 노드를 상위 레벨에 복제한다. 해시 테이블(hash table)은 결정적 해시 함수로 키를 버킷에 매핑한다. 블룸 필터는 k개 해시 함수가 지정한 비트를 사용해 포함 여부(membership)를 근사 판정한다.
- 기대값
- 기하급수
- 해시 충돌
- 비트 배열
스킵 리스트의 기대 공간은 n/(1-p), 높이와 탐색 시간은 기대 \(\Theta(\log n)\)Θ(log n)이다. 표준 블룸 필터는 삭제하지 않는다면 거짓 음성(false negative)은 없지만 거짓 양성(false positive)은 가능하다.
스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
완전 해싱(perfect hashing)과 일반 해싱, 카운팅 블룸 필터(counting Bloom filter)와 표준 블룸 필터를 구분한다.
- immer
- nur
- jede
- keine
- best case
- average case
- worst case
- implementation
- direction
- necessary vs. sufficient
Skip List·Hash·Bloom Filter 실험실
다음 상태를 먼저 예측한 뒤 한 단계 실행하여 확인하세요.
새 문장 판별 체크리스트
- immer, nur, jede, keine, stets 같은 강한 양화사를 먼저 표시한다.
- best/average/worst/expected/amortized 중 어느 경우인지 확인한다.
- 정의의 필요조건과 충분조건을 서로 바꾸지 않았는지 검사한다.
- 구현·표현·가중치·방향성 전제를 문장 옆에 적는다.
- 거짓으로 의심되면 가장 작은 구조나 입력으로 반례를 만든다.
- 평균/최악, p의 역할, 충돌 전제, false positive/negative 방향을 확인한다.
능동 회상
- 이 개념의 핵심 정의를 한 문장으로 말하라. — Skip list는 확률 p로 상위 레벨에 복제한다. Hash table은 결정적 hash로 키를 버킷에 매핑한다. Bloom filter는 k개 hash 비트로 근사 membership을 답한다.
- 판정 전에 확인할 전제 세 가지는 무엇인가? — 기대값, 기하급수, 해시 충돌, 비트 배열
- 중요한 시간·공간 경계를 말하라. — skip list search/insert/delete 기대 \(\Theta(\log n)\)
Θ(log n), 공간 \(\Theta(n)\)Θ(n). Hash table은 좋은 분포에서 기대 \(O(1)\)O(1), 최악 \(O(n)\)O(n). - 대표적인 최소 반례 하나를 말하라. — 삽입한 키를 바로 조회한다.
- 10초 판정 절차를 말하라. — 평균/최악, p의 역할, 충돌 전제, false positive/negative 방향을 확인한다.
구두시험 질문
- 정의를 말하고 원문 선택지 하나를 독립적으로 증명하라.
- 거짓 보편 명제 하나에 최소 반례를 제시하고 참이 되도록 최소 수정하라.
- 구현 또는 표현이 바뀔 때 runtime이나 참/거짓이 어떻게 달라지는가?
시험 직전 요약
스킵 리스트는 확률 p로 상위 레벨을 만들고, 해시 테이블은 해시 함수로 키를 버킷에 보낸다. 블룸 필터는 여러 해시 비트로 포함 여부를 근사 판정한다.
스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
완전 해싱(perfect hashing)과 일반 해싱, 카운팅 블룸 필터(counting Bloom filter)와 표준 블룸 필터를 구분한다.
평균·최악·기대 중 무엇을 묻는지, p의 역할, 충돌 처리 전제, 거짓 양성·거짓 음성의 방향을 확인한다.
출처
- 출처 파일: AuD Gedächtnisprotokoll SoSe 2025.md; 근거 페이지·구간: MC section, window 1; 뒷받침하는 내용: 2025년 여름학기 객관식 복기 문구, 절 규칙, 문항 I-6·II-1·II-8과 배점입니다. 공식 정답지는 아닙니다.; 검증 상태: reconstructed; 자료의 역할: reconstructed_exam; 추출 품질: \(\text{clean}_{\text{text}}\)
clean(text) - 출처 파일: Vorlesung\05RandomizedDataStructures-wi.pdf; 근거 페이지·구간: pp. 10-20; 뒷받침하는 내용: 스킵 리스트의 승격 확률 p, 층별 기대 크기, 평균 높이 \(O(\log_{1/p} n),\)
O(log₁/p} n),검색·삽입·삭제의 평균 시간 \(\Theta(\log_{1/p} n)\)Θ(log₁/p} n), 평균 공간 n/(1-p).; 검증 상태: verified; 자료의 역할: current_lecture; course term: Skip-Listen; 추출 품질: \(\text{clean}_{\text{text}}\)clean(text) - 출처 파일: Vorlesung\05RandomizedDataStructures-wi.pdf; 근거 페이지·구간: pp. 25-34; 뒷받침하는 내용: 해시 테이블은 해시 함수로 키를 배열 위치에 대응시키고 체이닝 등으로 충돌을 해결합니다. 기대 시간 분석에는 균등·독립 분포를 가정하며, 압축이나 암호화가 아니라 조회와 주소 지정에 쓰입니다.; 검증 상태: verified; 자료의 역할: current_lecture; course term: Hashtabellen und Hashfunktionen; 추출 품질: \(\text{clean}_{\text{text}}\)
clean(text) - 출처 파일: Vorlesung\05RandomizedDataStructures-wi.pdf; 근거 페이지·구간: pp. 35-45; 뒷받침하는 내용: 블룸 필터는 k개의 해시 함수와 m비트 배열을 사용합니다. 확인한 비트 중 하나가 0이면 확실히 없고, 모두 1이면 있을 가능성이 있습니다. 표준 삽입 전용 블룸 필터에는 거짓 음성이 없지만 거짓 양성은 생길 수 있습니다.; 검증 상태: verified; 자료의 역할: current_lecture; course term: Bloom-Filter; 추출 품질: \(\text{clean}_{\text{text}}\)
clean(text) - 출처 파일: Übung\AuD26_Sheet08.pdf; 근거 페이지·구간: pp. 2-4; 뒷받침하는 내용: \(p=1/2\)
p=1/2인 스킵 리스트 삽입·검색과 블룸 필터 삽입·질의·삭제 변형에 관한 공식 연습문제.; 검증 상태: verified; 자료의 역할: exercise_sheet; course term: Skip-Listen; Bloom-Filter; 추출 품질: \(\text{clean}_{\text{text}}\)clean(text) - 출처 파일: Übung\AuD26_Sheet08-Sol.pdf; 근거 페이지·구간: pp. 7-8; 뒷받침하는 내용: 공식 해시 테이블 체이닝 예제: 같은 해시값은 연결 리스트에 저장하고, 새 항목은 앞에 삽입하며, 삭제는 계산된 버킷만 확인합니다.; 검증 상태: verified; 자료의 역할: official_solution; course term: Hash Tables; 추출 품질: \(\text{clean}_{\text{text}}\)
clean(text) - 출처 파일: Übung\AuD26_Sheet08-Sol.pdf; 근거 페이지·구간: pp. 8-10; 뒷받침하는 내용: \(p=1/2\)
p=1/2인 공식 스킵 리스트 검색 경로와 무작위 승격 예제.; 검증 상태: verified; 자료의 역할: official_solution; course term: Skip-Listen; 추출 품질: \(\text{clean}_{\text{text}}\)clean(text) - 출처 파일: Übung\AuD26_Sheet08-Sol.pdf; 근거 페이지·구간: pp. 10-12; 뒷받침하는 내용: 공식 블룸 필터 연습문제: 거짓 양성 가능성, 질의 해석, 그리고 삭제를 위해 더 많은 메모리를 쓰는 카운팅 변형이 필요하다는 내용.; 검증 상태: verified; 자료의 역할: official_solution; course term: Bloom-Filter; 추출 품질: \(\text{clean}_{\text{text}}\)
clean(text)
AI 후속 학습 프롬프트
마지막 생성: 2026-08-03 03:24