64상태 collision·probe·rehash Gold lab

1. 01

   먼저 생각하기 · 기초

   ht64 predict · 64상태 collision·probe·rehash Gold lab: “결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다.” 조건에서 probe·chain·load·lookup 결과를 실행 전에 봉인한다.

   상황

   capacity 5, h(k)=k mod 5인 language-neutral unique-key map은 각 bucket에 insertion-order chain을 둔다. put 2:A, put 7:B, put 12:C, get 7, put 7:B2, remove 2, get 12를 수행한다.

   문제

   각 operation 뒤 bucket 2 chain, 반환값, size와 equality comparison 수를 예측하세요. collision과 duplicate update가 왜 서로 다른 사건인지 설명하고 전체 map이 상수 시간이라고 단정하지 마세요.

   제공 자료

   • put은 home bucket chain을 앞에서부터 equality 검사하고 equal key가 있으면 value를 바꾸고 old value를 반환한다.
   • equal key가 없으면 chain 뒤에 새 entry를 붙이고 size를 1 늘리며 NEW를 반환한다.
   • get과 remove도 chain 앞에서부터 equality 검사하며 remove는 찾은 node만 연결에서 제외한다.
   • 서로 다른 key 2, 7, 12는 모두 bucket 2로 hash되지만 equal하지 않다.
   • operation 비용은 전체 size가 아니라 실제 검사한 chain 길이로 기록한다.

   비교표 · 외운 답에 기대지 않았는지 밝히고, 내 까닭과 “항상 맞다”는 말을 깨는 장면까지 쓰기20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   연습과 같은 문제를 다시 풀어 보는 시간이에요. 힌트 없이 먼저 생각해 보세요. 지금 적은 답은 바로 합격으로 기록되지 않아요.

   내 답과 맞춰 볼 기준 보기움직임과 비교
2. 02

   내 말로 설명하기 · 익힌 것을 써보기

   ht64 explain · 64상태 collision·probe·rehash Gold lab: workload 4개, collision policy 4개, scale 4개의 64상태에서 key identity·probe/chain·delete continuity·capacity·rehash·claim level을 비교한다.이 필요한 이유와 64셀 workload·policy·scale matrix, ordered gate evidence, source ledger와 human verdict memo가 보장하지 못하는 runtime·security·concurrency 범위를 설명한다.

   상황

   P03의 capacity 7 linear-probing table [38:D,EMPTY,EMPTY,10:A,17:B,24:C,31:E]에서 remove 17, get 24, get 45, put 45:F를 수행한다. h(45)=3이다.

   문제

   EMPTY로 지우는 AI 제안이 왜 lookup을 깨는지 설명하고 DELETED tombstone trace를 작성하세요. put이 first tombstone을 즉시 쓰지 않고 probe를 계속해야 하는 duplicate/update 이유와 tombstone 누적 경계도 포함하세요.

   제공 자료

   • remove 성공은 해당 slot을 DELETED로 바꾸고 size를 줄이지만 뒤의 cluster를 이동하지 않는다.
   • lookup은 DELETED에서 멈추지 않고 계속 probe하며 EMPTY에서만 absent를 확정한다.
   • put은 처음 본 DELETED index를 기억하지만 뒤에서 equal key가 발견될 수 있어 EMPTY 또는 full-cycle까지 탐색한다.
   • equal key를 찾지 못하고 EMPTY를 만나면 기억한 first DELETED를 재사용한다.
   • probe는 capacity개 step에서 끝나며 tombstone 수와 occupied size를 별도 관측한다.

   까닭을 함께 쓰는 설명 · 외운 답에 기대지 않았는지 밝히고, 내 까닭과 “항상 맞다”는 말을 깨는 장면까지 쓰기20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   연습과 같은 문제를 다시 풀어 보는 시간이에요. 힌트 없이 먼저 생각해 보세요. 지금 적은 답은 바로 합격으로 기록되지 않아요.

   내 답과 맞춰 볼 기준 보기설명 기준과 비교
3. 03

   틀린 곳 고치기 · 익힌 것을 써보기

   ht64 debug · 64상태 collision·probe·rehash Gold lab: AI가 만든 구현에 “결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다.”를 주입하고 최초 잘못된 hash-table state transition만 수정한다.

   상황

   AI가 separate-chaining map의 put을 `bucket.append(Node(key,value)); size += 1; return NEW`로 작성했다. 계약은 unique-key map이며 put은 equal key value를 replace하고 old value를 반환한다. 공개 trace는 put alpha:1, put beta:2, put alpha:3, putIfAbsent alpha:9, remove alpha, get alpha다.

   문제

   AI 초안의 duplicate bug를 최소 수정하고 각 operation의 반환값·size·mapping 집합을 추적하세요. hash collision인 non-equal beta와 equal alpha를 구분하고 multimap이 필요한 경우를 별도 계약으로 제시하세요.

   제공 자료

   • put(k,v)는 equal key가 있으면 value를 replace하고 old value를 반환하며 size를 바꾸지 않는다.
   • putIfAbsent(k,v)는 equal key가 있으면 existing value를 반환하고 mapping을 바꾸지 않는다.
   • remove(k)는 equal mapping 하나를 제거하고 old value를 반환하며 성공할 때만 size를 줄인다.
   • alpha와 beta는 이 synthetic trace에서 같은 bucket으로 hash되지만 equal하지 않다.
   • map은 equal key마다 mapping 하나만 허용하며 multimap의 duplicate-value semantics는 별도 ADT다.

   컴퓨터 안내와 나온 결과 · 외운 답에 기대지 않았는지 밝히고, 내 까닭과 “항상 맞다”는 말을 깨는 장면까지 쓰기20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   연습과 같은 문제를 다시 풀어 보는 시간이에요. 힌트 없이 먼저 생각해 보세요. 지금 적은 답은 바로 합격으로 기록되지 않아요.

   내 답과 맞춰 볼 기준 보기답과 설명 함께 비교
4. 04

   새 문제에 써보기 · 새 문제

   ht64 transfer · 64상태 collision·probe·rehash Gold lab: 교차 언어 hash-table shiproom·AI 생성 구현 감사로 판단을 옮겨 보존할 계약과 달라지는 collision·cost·security 경계를 방어한다.

   상황

   AI가 unique-key hash table 초안과 설명을 냈다. 초안은 hash가 같으면 key가 같다고 보고, linear-probing delete를 EMPTY로 바꾸며, resize 때 old slot을 같은 index로 복사하고, 모든 put에서 size를 늘린다. 설명은 worst-case O(1)과 hash-flood 면역을 주장한다.

   문제

   AI 초안의 claim inventory를 만들고 P01~P07 공개 trace로 각 결함을 재현하세요. 최소 수정 순서, 독립 AI-off oracle, accept·revise·reject 판정과 잔여 위험을 작성하되 private fixture나 외부 accepted 결과를 증거로 요구하지 마세요.

   제공 자료

   • correctness oracle은 equal→same-hash, collision 뒤 equality, probe reachability, one-key-one-mapping과 rehash mapping 보존이다.
   • 공개 audit trace는 same-hash non-equal pair, tombstone 뒤 key, capacity 변경으로 bucket이 바뀌는 key와 equal-key update를 포함한다.
   • security oracle은 expected와 worst case를 구분하고 untrusted key에 quota·budget·fallback·redacted telemetry를 요구한다.
   • AI가 만든 expected output이나 같은 초안의 test는 독립 oracle이 아니며 사람이 먼저 계산한 model과 대조한다.
   • 이 공개 specification은 self-review material이며 hidden tests, private seed와 server-authoritative 판정값을 포함하지 않는다.

   까닭을 함께 쓰는 설명 · 외운 답에 기대지 않았는지 밝히고, 내 까닭과 “항상 맞다”는 말을 깨는 장면까지 쓰기20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   연습과 같은 문제를 다시 풀어 보는 시간이에요. 힌트 없이 먼저 생각해 보세요. 지금 적은 답은 바로 합격으로 기록되지 않아요.

   내 답과 맞춰 볼 기준 보기설명 기준과 비교

4개 답이 남았습니다.