64상태 collision·probe·rehash Gold lab

1. 01

   찾아보기 · 기초

   ht64 recognize · 64상태 collision·probe·rehash Gold lab: 64-state hash lab·workload-policy-scale·final-only rehash audit 단서에서 “workload 4개, collision policy 4개, scale 4개의 64상태에서 key identity·probe/chain·delete continuity·capacity·rehash·claim level을 비교한다.”을 만족하는 hash-table 판정을 고른다.

   상황

   회원 설정 map의 합성 key는 region과 memberId로 같은 회원을 판정하고 displayLabel은 화면 표시용이다. region은 ASCII lowercase로 정규화하고 memberId는 원문을 보존한다. 세 hash 후보를 비교한다.

   문제

   후보 A=hash(lower(region),memberId), B=hash(lower(region),memberId,displayLabel), C=hash(lower(region)) 중 key equality와 일치하는 후보를 고르세요. equal key update, collision, 저장 중 key mutation을 표로 분류하고 보장할 수 없는 구현 세부도 적으세요.

   제공 자료

   • 두 key는 lower(region)과 memberId가 모두 같을 때만 equal이며 displayLabel은 equality에 참여하지 않는다.
   • equal인 두 key는 같은 hash value를 가져야 하지만 같은 hash value인 두 key가 반드시 equal일 필요는 없다.
   • map은 hash로 후보 위치를 좁힌 뒤 equality로 실제 key 일치를 판정한다.
   • equality 또는 hash에 참여하는 field는 key가 map에 저장된 동안 바뀌지 않는 계약으로 봉인한다.
   • hash width, seed, bucket index 계산과 iteration order는 별도 runtime 계약 없이는 추론하지 않는다.

   비교표 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기정답과 비교
2. 02

   먼저 생각하기 · 기초

   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자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기움직임과 비교
3. 03

   순서 따라가기 · 익힌 것을 써보기

   ht64 trace · 64상태 collision·probe·rehash Gold lab: hash → index → collision strategy → equality → result 순서로 64셀 workload·policy·scale matrix, ordered gate evidence, source ledger와 human verdict memo를 완성한다.

   상황

   capacity 7, h(k)=k mod 7인 open-addressed unique-key map은 linear probe index=(home+step) mod 7을 사용한다. insert 10:A, 17:B, 24:C, get 17, get 31, insert 31:E, insert 38:D를 수행한다.

   문제

   각 operation의 probe index sequence, equality 결과, 반환값과 최종 slot 배열을 추적하세요. get miss가 first EMPTY에서 끝나는 이유, wraparound와 최대 7회 probe 종료 조건을 설명하세요.

   제공 자료

   • 각 slot은 이 문제에서 EMPTY 또는 OCCUPIED(key,value)이며 deletion은 아직 수행하지 않는다.
   • lookup은 OCCUPIED slot의 key를 equality 검사하고 EMPTY를 만나면 MISSING으로 종료한다.
   • insert는 equal key를 만나면 update하고, first EMPTY를 만나면 그 slot에 새 entry를 둔다.
   • probe는 최대 capacity개 서로 다른 step만 확인하고 그 뒤 TABLE_FULL 또는 MISSING으로 종료한다.
   • iteration order나 다른 probing formula는 이 synthetic linear-probing 계약에 포함하지 않는다.

   순서대로 적기 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기움직임과 비교
4. 04

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

   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자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

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

   빈칸 채우기 · 익힌 것을 써보기

   ht64 complete · 64상태 collision·probe·rehash Gold lab: 누락된 hash/equality·bucket·probe·slot-state·load-factor 칸을 채워 “각 셀의 contract, bucket topology, collision trace, equality/probe/rehash work와 final-only gate 판정을 완성한다.”을 완성한다.

   상황

   separate-chaining unique-key map은 capacity 4, maxLoadFactor 0.75이고 h(k)=k다. 현재 mappings는 1:A, 5:B, 2:C로 size=3이다. put 9:D와 그 뒤 put 5:B2를 처리할 incomplete resize pseudocode를 완성한다.

   문제

   projected load factor 검사, capacity 8 allocation, rehash, insertion과 duplicate update 순서를 완성하세요. old bucket index를 그대로 복사하는 오류를 반례로 깨고 최종 buckets·size·load factor를 제시하세요.

   제공 자료

   • 새 distinct key를 넣을 때 projected=(size+1)/capacity가 maxLoadFactor보다 크면 insertion 전에 capacity를 2배로 늘린다.
   • projected가 임계값과 정확히 같으면 이 synthetic policy에서는 resize하지 않는다.
   • resize는 모든 occupied mapping의 hash를 새 capacity에 다시 적용해 새 bucket을 계산한다.
   • equal key update는 size를 늘리지 않으므로 projected distinct insertion 검사를 실행하지 않는다.
   • resize 뒤에도 key-value mapping 집합은 같아야 하며 bucket iteration order는 공개 요구가 아니다.

   컴퓨터 안내와 나온 결과 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

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

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

   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단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

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

   직접 만들기 · 새 문제

   ht64 implement · 64상태 collision·probe·rehash Gold lab: 각 셀의 contract, bucket topology, collision trace, equality/probe/rehash work와 final-only gate 판정을 완성한다.을 frozen synthetic key stream에 적용해 64셀 workload·policy·scale matrix, ordered gate evidence, source ledger와 human verdict memo를 생성한다.

   상황

   외부 client가 문자열 key를 보내는 합성 request counter는 공개된 weakHash에서 공격자가 선택한 12개 distinct key를 모두 bucket 0으로 만들 수 있다. 서비스 목표는 collision-free가 아니라 요청 비용을 제한하고 degradation을 관측하는 것이다.

   문제

   12-key hash-flood trace의 successful/unsuccessful comparison 수를 계산하고 language-neutral 방어 pseudocode를 작성하세요. runtime이 제공하는 검토된 randomized/keyed default, 입력 quota·rate limit, probe/chain telemetry와 fallback을 계층화하고 보장하지 않는 범위를 명시하세요.

   제공 자료

   • separate chaining miss는 bucket 0의 12개 non-equal key를 모두 equality 검사한 뒤 MISSING이 된다.
   • 공격자가 선택 가능한 key에 공개·고정 weakHash만 사용하는 설계는 expected O(1)을 worst-case O(1) 보장으로 바꿔 주지 않는다.
   • 검토된 runtime의 randomized/keyed default가 있으면 직접 만든 비밀 hash보다 우선하되 algorithm·seed·성능은 runtime 계약을 따른다.
   • key 길이·요청당 distinct key·map size·rate에 quota를 두고 초과는 명시적 reject 또는 bounded fallback으로 처리한다.
   • chain/probe histogram, rejected count와 latency를 관측하되 secret seed·raw private payload를 telemetry에 기록하지 않는다.

   컴퓨터 안내와 나온 결과 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기정답과 비교
8. 08

   새 문제에 써보기 · 새 문제

   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단계 힌트 보기

   1. 관찰

      결정론적 direct-slot/chaining/linear-tombstone/quadratic-eager-clear 추상 정책을 언어별 내부 layout·성능·보안·thread 보장으로 복사한다. 직전까지 참이었던 key→bucket/probe 관계와 처음 달라진 state·result를 찾으세요.

   2. 개념

      64-state hash lab·workload-policy-scale·final-only rehash audit를 ADT·collision strategy·source-level로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

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

8개 답이 남았습니다.