해시 테이블의 충돌과 확장

해시 테이블의 빠른 조회는 해시 계산만으로 완성되지 않습니다. 후보 슬롯을 찾은 뒤 동등성 비교, 충돌 경로 보존, 삭제 표식, 확장 중 세대 전환이 함께 맞아야 하며, 이 노트는 그 상태 변화를 기준으로 구현 선택과 실패를 진단합니다.

해시 기반 후보 위치와 동등 비교

해시 함수는 키를 숫자로 변환하고 테이블은 그 숫자로 후보 위치를 고릅니다. 해시가 같아도 키는 다를 수 있으므로 실제 동등 비교가 필요합니다. 동등한 키가 같은 해시를 가져야 한다는 계약과 모든 해시가 서로 다르다는 주장은 다릅니다.

키를 넣은 뒤 동등성·해시 계산에 사용하는 필드를 바꾸면 항목이 남아 있어도 조회가 다른 버킷으로 가서 못 찾을 수 있습니다. 안정적인 불변 키를 쓰거나 변경 전에 삭제하고 재삽입합니다.

두 가지 충돌 해결 방식

선택 기준은 평균 복잡도 하나가 아니라 키 입력의 공격 가능성, 삭제 비율, 메모리 지역성, 최악 탐사 지연, 동시 갱신 계약입니다. open addressing을 택했다면 capacity가 가득 차는 경우와 tombstone 누적을 별도 상태로 측정하고, chaining을 택했다면 긴 버킷의 비교 비용과 할당 패턴을 확인해야 합니다.

방식	저장	장점	비용
Chaining	버킷마다 목록·트리 등	버킷별 관리가 직관적	포인터·할당·긴 버킷 탐색
Open addressing	테이블의 다른 슬롯을 탐사	연속 메모리·지역성	높은 점유율·군집·삭제 처리

평균 O(1)에 가까운 비용은 좋은 분포와 적절한 부하율의 조건입니다. 모든 키가 충돌하면 최악에는 선형 탐색이 될 수 있습니다. 네트워크·문자열 해시·할당까지 포함한 전체 요청 지연이 상수라는 뜻도 아닙니다.

선형 탐사의 검색과 삭제

find(key):
    start = hash(key) mod capacity
    for step = 0 .. capacity - 1:
        slot = table[(start + step) mod capacity]
        if slot is NEVER_USED: return not-found
        if slot is LIVE and slot.key == key: return slot.value
        // tombstone이면 멈추지 않음
    return not-found

중간 항목을 삭제하며 NEVER_USED로 바꾸면 뒤의 충돌 키를 찾기 전에 검색이 멈춥니다. tombstone은 삭제됐지만 탐사는 이어가야 한다는 표식입니다. 삽입 때 재사용할 수 있어도 같은 키가 뒤에 있는지 충분히 확인해 중복을 막아야 합니다.

실제 원소 수/용량과 tombstone을 포함한 탐사상 점유율을 나눠 봅니다. 삭제가 많으면 원소 수는 적어도 탐색이 느릴 수 있습니다.

삭제 표식 통과와 검색 경로 보존

용량 5의 테이블에 정수 키를 넣고, 설명을 위해 hash(key)=key로 두겠습니다. 1·6·11은 모두 나머지가 1이라 같은 슬롯에서 탐색을 시작합니다. 실제 서비스용 해시 함수를 권장하는 예가 아니라 충돌을 손으로 만들기 위한 설정입니다.

연산	슬롯 1	슬롯 2	슬롯 3	이유
1 삽입	1	미사용	미사용	시작 슬롯 사용
6 삽입	1	6	미사용	1이 있으므로 다음 칸
11 삽입	1	6	11	두 칸을 지나 다음 칸
6 삭제	1	삭제 표식	11	뒤의 탐색 경로 보존
11 조회	1을 비교	표식을 통과	11 발견	미사용 칸이 아니므로 계속 탐색

그림을 글로 읽기

• 슬롯 1 · 키 1: 11 mod 5 = 1 · 키가 다르므로 계속
• 슬롯 2 · 삭제 표식: 비어 있지만 탐색은 계속
• 슬롯 3 · 키 11: 동등 비교 성공

1. 슬롯 1 · 키 1 → 슬롯 2 · 삭제 표식: 다음 슬롯
2. 슬롯 2 · 삭제 표식 → 슬롯 3 · 키 11: 표식 통과

삭제 표식은 삽입 후보로 기억해 둘 수 있습니다. 다만 키 11을 갱신할 때 표식에 곧바로 새 11을 넣으면 기존 11과 중복됩니다. 먼저 탐색을 끝내 같은 키가 있는지 확인하고, 없다면 기억한 삭제 칸을 재사용해야 합니다. 모든 칸이 사용됐거나 삭제 표식이어도 슈도코드가 최대 capacity번 뒤 끝나는 이유는 미사용 칸을 만날 수 없는 경우까지 처리하기 위해서입니다.

확장과 점진 재해시

재해시의 상태를 old+new, new only, retired처럼 명시하면 조회와 쓰기의 우선순위를 설명하기 쉽습니다. 한 키의 갱신이 어느 세대에 기록되는지, 이동 중 삭제가 어떤 버전으로 표시되는지, 독자가 옛 배열을 더 이상 참조하지 않는 시점을 각각 관찰할 수 있어야 합니다.

용량이 바뀌면 같은 해시의 슬롯 계산도 바뀌므로 원소를 새 테이블에 다시 배치해야 합니다. 한 번에 옮기면 O(n)의 지연과 옛·새 저장소 동시 보유가 생깁니다.

점진적 재해시는 한 번에 모든 항목을 옮기지 않고 일부 버킷이나 항목을 옮기면서 새 테이블과 옛 테이블을 함께 조회합니다. 조회에서 두 세대에 같은 키가 보이면 어느 세대의 값이 최신인지 정해야 하고, 이동 중 갱신·삭제가 끼어들어 옛 값이 새 테이블에 되살아나지 않게 해야 합니다.

이동 완료를 기록하는 시점과 옛 배열을 읽던 독자가 끝난 시점도 달라서, 둘을 확인한 뒤에만 옛 배열을 회수할 수 있습니다. 읽기만 계속되는 시스템이라도 조회 경로가 이동을 조금씩 진행할지 별도 작업이 맡을지 정하지 않으면 재해시가 끝나지 않을 수 있습니다.

버킷 하나에 충돌 키가 매우 많으면 요청마다 한 버킷을 옮기는 방식도 한 요청의 지연 상한을 보장하지 않습니다. 한 번에 이동할 원소 수와 시간 예산을 별도로 제한해야 합니다.

삭제·이동 경합과 양쪽 테이블의 원자 갱신 규칙

두 세대를 같은 잠금으로 보호하는 단순 모형을 생각해 보겠습니다. 새 테이블을 우선 조회하고, 없으면 옛 테이블을 조회합니다. 갱신은 새 테이블에 쓰고 옛 테이블의 같은 키를 제거합니다. 삭제는 양쪽에서 지웁니다. 이동은 그 잠금 안에서 옛 항목을 읽어 새 테이블에 없을 때만 옮긴 뒤 옛 항목을 제거합니다. 이 전 과정이 원자적이면 삭제 뒤 옛값이 다시 나타나는 경합을 막을 수 있습니다.

반대로 이동자가 잠금 밖에서 옛 값 v1을 복사한 뒤, 삭제자가 양쪽을 지우고, 이동자가 새 테이블에 v1을 넣으면 값이 되살아납니다. 잠금 밖 복사를 허용하려면 현재 버전·삭제 tombstone과 비교하는 별도 규칙이 필요합니다. 단순 set-if-absent도 삭제로 빈 상태가 된 것과 아직 옮기지 않은 상태를 구분하지 못합니다. 옛 테이블 회수는 이동 완료뿐 아니라 그 테이블을 읽는 독자 종료까지 기다려야 합니다.

부하율과 1차 군집의 분리

선형 탐사에서는 긴 연속 점유 구간에 새 충돌 키가 붙어 구간이 더 길어지는 1차 군집이 생길 수 있습니다. 다른 시작 버킷의 키도 같은 점유 구간에 들어오면 탐사 길이가 함께 늘어납니다. 부하율을 낮추면 보통 빈칸을 빨리 찾지만 메모리·캐시 footprint·재해시 피크가 증가합니다. 같은 부하율이어도 해시 분포와 삭제 표식 비율에 따라 최대 탐사는 다르므로 평균만 비교하지 않습니다.

동시성과 보안

일반 map과 concurrent map의 계약을 구분합니다. concurrent 구조도 get → 계산 → put의 복합 연산이나 value 객체 내부 변경까지 자동 원자화하지는 않습니다.

공개 입력에는 예측하기 어려운 해시 시드·키 길이·항목 수·실행 예산을 검토합니다. 보안용 무작위 해시를 서버 간 영구 샤드 배정 함수로 쓰면 같은 키가 다른 위치로 갈 수 있으므로 안정적인 분산 해시는 별도 계약으로 둡니다.

충돌·삭제·키 mutation·재해시 경합 테스트

충돌 키, 동일 키 갱신, 삭제 뒤 검색, 가득 찬 테이블, tombstone 재사용, 키 mutation을 테스트합니다. resize 중 삭제·재삽입을 기준 map과 대조하고 평균뿐 아니라 최대 탐사·재해시 p99·메모리 피크를 기록합니다.