II-8 일반 Hashing의 목적·결정성·충돌 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
일반 hash table의 hash function은 key를 bucket 주소로 보내는 함수입니다. 압축 파일이나 암호문을 만드는 장치와 목적이 다릅니다.
도서관에서 책 제목을 서가 번호로 바꾸는 안내 규칙입니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. deterministic, bucket address, collision possibility 세 질문으로 각 보기를 검사합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
일반 hash table의 hash function은 key를 bucket 주소로 보내는 함수입니다. 압축 파일이나 암호문을 만드는 장치와 목적이 다릅니다.
이 문항에서 가장 먼저 붙잡을 문장은 '같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다.
- deterministic, bucket address, collision possibility 세 질문으로 각 보기를 검사합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다. 둘째, 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다.
셋째, 충돌은 chaining/open addressing 등으로 처리한다. 넷째, cryptographic hashing과 일반 table hashing의 목적을 구분한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다.
- 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다.
- 충돌은 chaining/open addressing 등으로 처리한다.
- cryptographic hashing과 일반 table hashing의 목적을 구분한다.
개념 3 · 강의 정의를 초보자 언어로 해체
스킵 리스트(skip list)는 여러 높이의 고속도로 진입 램프처럼 일부 노드를 건너뛰게 한다. 블룸 필터(Bloom filter)는 '확실히 없음' 또는 '아마 있음'만 말해 주는 스탬프 판과 같다.
스킵 리스트는 확률 p로 노드를 상위 레벨에 복제한다. 해시 테이블(hash table)은 결정적 해시 함수로 키를 버킷에 매핑한다. 블룸 필터는 k개 해시 함수가 지정한 비트를 사용해 포함 여부(membership)를 근사 판정한다.
수식으로 정확히 쓰기
핵심 규칙스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
이 절에서 꼭 기억할 것
- 기대값
- 기하급수
- 해시 충돌
- 비트 배열
개념 4 · 성립 조건·불변식·경계 사례
스킵 리스트의 기대 공간은 n/(1-p), 높이와 탐색 시간은 기대 \(\Theta(\log n)\)Θ(log n)이다. 표준 블룸 필터는 삭제하지 않는다면 거짓 음성(false negative)은 없지만 거짓 양성(false positive)은 가능하다.
완전 해싱(perfect hashing)과 일반 해싱, 카운팅 블룸 필터(counting Bloom filter)와 표준 블룸 필터를 구분한다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, C입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, C
이 절에서 꼭 기억할 것
- 일반 hashing, perfect hashing, 암호학을 구분한다.
- 결정성·버킷 주소·충돌 가능성 세 단어를 확인한다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
일반 Hashing의 목적·결정성·충돌
같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다. | 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다. | 충돌은 chaining/open addressing 등으로 처리한다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
해시 테이블과 해시 함수에 관한 옳은 설명 두 개를 고르시오.
핵심 규칙일반 Hashing의 목적·결정성·충돌
핵심 도구를 종이에 꺼낸다
deterministic, bucket address, collision possibility 세 질문으로 각 보기를 검사합니다.
핵심 규칙같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다. | 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다. | 충돌은 chaining/open addressing 등으로 처리한다.
선택지 A를 독립 판정한다
주목적은 키를 버킷에 매핑해 빠르게 찾는 것이다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
같은 함수와 같은 키는 같은 해시값을 반환해야 검색이 가능하다.
\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
강의의 일반 키 우주가 테이블보다 크다는 전제에서는 비둘기집 원리로 충돌이 가능하다.
\[선택지 C = 참\]선택지 C = 참선택지 D를 독립 판정한다
자료구조용 해싱(hashing)은 키를 테이블 위치에 빠르게 매핑하는 것이 목적이며, 암호학적 암호화(cryptographic encryption)와 목적이 다르다.
\[선택지 D = 거짓\]선택지 D = 거짓정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, C입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, C\]검증된 정답 = B, C
2. 이 문제를 실제로 끝까지 풀기
일반 hash table의 hash function은 key를 bucket 주소로 보내는 함수입니다. 압축 파일이나 암호문을 만드는 장치와 목적이 다릅니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다. (2) 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다. (3) 충돌은 chaining/open addressing 등으로 처리한다. (4) cryptographic hashing과 일반 table hashing의 목적을 구분한다.
선택지 A는 거짓입니다. 주목적은 키를 버킷에 매핑해 빠르게 찾는 것이다. 가장 작은 확인 예는 load factor를 낮추면 오히려 빈 슬롯을 많이 둔다.
선택지 B는 참입니다. 같은 함수와 같은 키는 같은 해시값을 반환해야 검색이 가능하다.
선택지 C는 참입니다. 강의의 일반 키 우주가 테이블보다 크다는 전제에서는 비둘기집 원리로 충돌이 가능하다.
선택지 D는 거짓입니다. 자료구조용 해싱(hashing)은 키를 테이블 위치에 빠르게 매핑하는 것이 목적이며, 암호학적 암호화(cryptographic encryption)와 목적이 다르다. 가장 작은 확인 예는 단순 modulo 해시는 암호화가 아니어도 해시 테이블에 쓸 수 있다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, C입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. deterministic, bucket address, collision possibility 세 질문으로 각 보기를 검사합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
주목적은 키를 버킷에 매핑해 빠르게 찾는 것이다.
빠른 확인법: load factor를 낮추면 오히려 빈 슬롯을 많이 둔다.
-
B참 — 정답 후보
같은 함수와 같은 키는 같은 해시값을 반환해야 검색이 가능하다.
빠른 확인법: 해시 함수는 결정적이다.
-
C참 — 정답 후보
강의의 일반 키 우주가 테이블보다 크다는 전제에서는 비둘기집 원리로 충돌이 가능하다.
빠른 확인법: 충돌을 완전히 피하는 해시 함수는 없다.
-
D거짓
자료구조용 해싱(hashing)은 키를 테이블 위치에 빠르게 매핑하는 것이 목적이며, 암호학적 암호화(cryptographic encryption)와 목적이 다르다.
빠른 확인법: 단순 modulo 해시는 암호화가 아니어도 해시 테이블에 쓸 수 있다.
4. 초보자가 가장 자주 틀리는 이유
- 일반 hashing, perfect hashing, 암호학을 구분한다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
deterministic, bucket address, collision possibility 세 질문으로 각 보기를 검사합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, C이다. 핵심 근거: 같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다. 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다. 충돌은 chaining/open addressing 등으로 처리한다. cryptographic hashing과 일반 table hashing의 목적을 구분한다.
6. 스스로 이해했는지 확인
II-8의 주제를 한 문장으로 설명하면?
정답: 일반 hash table의 hash function은 key를 bucket 주소로 보내는 함수입니다. 압축 파일이나 암호문을 만드는 장치와 목적이 다릅니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: deterministic, bucket address, collision possibility 세 질문으로 각 보기를 검사합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 같은 key는 같은 table 상태에서 같은 hash 값을 내므로 결정적이다.
핵심 사실 네 가지 중 두 번째는?
정답: 보통 key 공간이 bucket 수보다 커 pigeonhole principle로 충돌 가능성이 있다.
가장 위험한 함정은?
정답: 일반 hashing, perfect hashing, 암호학을 구분한다.
정답 label은?
정답: B, C
이 개념의 핵심 정의를 한 문장으로 말하라.
정답: Skip list는 확률 p로 상위 레벨에 복제한다. Hash table은 결정적 hash로 키를 버킷에 매핑한다. Bloom filter는 k개 hash 비트로 근사 membership을 답한다.
판정 전에 확인할 전제 세 가지는 무엇인가?
정답: 기대값, 기하급수, 해시 충돌, 비트 배열
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-8
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section, window 1
2025년 여름학기 객관식 복기 문구, 절 규칙, 문항 I-6·II-1·II-8과 배점입니다. 공식 정답지는 아닙니다.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).Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 25-34
해시 테이블은 해시 함수로 키를 배열 위치에 대응시키고 체이닝 등으로 충돌을 해결합니다. 기대 시간 분석에는 균등·독립 분포를 가정하며, 압축이나 암호화가 아니라 조회와 주소 지정에 쓰입니다.Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 35-45
블룸 필터는 k개의 해시 함수와 m비트 배열을 사용합니다. 확인한 비트 중 하나가 0이면 확실히 없고, 모두 1이면 있을 가능성이 있습니다. 표준 삽입 전용 블룸 필터에는 거짓 음성이 없지만 거짓 양성은 생길 수 있습니다.