해시 비용을 가르는 충돌 뒤처리

같은 해시 함수를 써도, 배치하지 못하고 밀려난 키의 비율과 지운 자리를 다루는 방식에 따라 공간과 질의 시간, 정확성이 달라집니다.

해시 구조를 비교할 때는 보통 해시 함수의 품질과 탐사 규칙의 프로브 수를 봅니다. 2026년에 나온 두 논문은 해시 함수를 고정해도 비용이 크게 달라지는 지점을 보여 줍니다. 정적 구조에서는 배치하지 못하고 다음 레벨로 밀려난 키의 비율이, 동시성 구조에서는 삭제한 슬롯을 다루는 방식이 그 지점입니다.

두 사례를 하나의 선택 기준으로 묶는 것은 판단입니다. 탐사 규칙의 이론적 프로브 상한과 실전 구현의 격차는 자료구조 이론과 라이브러리 사이의 격차에서 다뤘습니다. 체이닝과 개방 주소법의 기본 구조는 자료구조에 있습니다.

정적 구조에서 비용이 모이는 범핑

최소 완전 해시 함수(Minimal Perfect Hash Function, MPHF)는 고정된 n개 키를 0부터 n−1까지의 번호에 겹침 없이 대응시킵니다. 키 집합이 바뀌지 않으므로 충돌은 모두 구축 단계에서 처리합니다.

PHast 계열은 키를 버킷으로 나누고, 버킷마다 S비트 시드를 골라 버킷의 키를 각자의 슬라이스 안 빈 슬롯에 놓습니다. 시드 s와 키의 해시 h로 슬라이스 안 위치를 정하는 함수를 배치 함수 p(s, h)라고 합니다.

시드 0을 뺀 $2^S - 1$개 시드 가운데 어느 것도 버킷의 키를 겹침 없이 놓지 못하면 그 버킷을 범핑(bumping)합니다. 범핑한 버킷은 시드 0으로 표시하고, 그 키는 다음 레벨에서 다시 배치합니다. 첫 레벨에 남은 빈 슬롯은 Elias-Fano 배열로 다음 레벨의 결과와 연결합니다.

flowchart TD
    K["키"] --> H["64비트 해시"]
    H --> S["첫 레벨 시드 읽기"]
    S -->|"시드 ≠ 0"| P["슬라이스 안 슬롯 계산"]
    S -->|"시드 = 0, 범핑"| N["다음 레벨 시드 읽기"]
    N --> R["Elias-Fano 재매핑 읽기"]
    P --> OUT["0부터 n-1까지의 번호"]
    R --> OUT

범핑된 키의 질의는 다음 레벨의 시드와 재매핑 구조를 차례로 읽으며, 이 접근은 앞 단계 결과에 의존하는 캐시 미스입니다. PHastR 논문은 10⁹개 키에서 범핑된 키의 질의가 첫 레벨 키보다 약 220~260 ns 더 걸린다고 보고합니다. 이 규모에서는 범핑 비율 1%마다 평균 질의 시간이 2 ns 넘게 늘어납니다.

공간도 같은 변수에 묶입니다. 논문은 키당 비트 수를 다음 식으로 근사합니다. β는 범핑된 키의 비율, λ는 버킷당 평균 키 수입니다.

$$\frac{S}{\lambda(1-\beta)} + \beta\left(2 + \log_2\frac{1}{\beta}\right)$$

시드 폭 S와 λ를 정하면 남는 변수는 β뿐입니다. 저자도 이 조건에서 초과 공간과 느린 질의가 모두 범핑에서 나온다고 적습니다.

첫 레벨 질의는 거의 같습니다

PHastR 논문은 첫 레벨 키만 질의한 시간과 전체 키를 질의한 시간을 따로 측정했습니다. 세 구조 모두 같은 해시 함수 GxHash를 쓰고, 10⁹개 64비트 정수 키를 대상으로 했습니다. PHast+ wrapping은 시드에 작은 정수 δ를 곱해 더하고, 슬라이스 끝을 넘은 키를 처음으로 되돌리는 변형입니다.

첫 레벨 질의의 차이는 0.6 ns 안에 있고, 전체 질의의 차이는 범핑 비율 순서를 따릅니다. 저자는 PHast+ wrapping과 PHastR의 차이를 범핑된 키로 설명하고, PHast는 첫 레벨 질의가 조금 느린 점도 차이의 일부라고 적습니다.

측정 기계는 AMD EPYC 9R45 한 개를 쓴 Amazon EC2 m8a.metal-24xl입니다. 이 표는 별도 실행에서 잰 값이라, 전체 키 질의 시간이 뒤의 전체 비교에 나오는 15.3 ns와 조금 다릅니다.

배치 레이아웃이 줄인 자기 충돌

PHast+는 시드를 더하기만 하는 가산 배치를 씁니다. 시드가 바뀌면 버킷의 모든 키가 같은 거리만큼 함께 움직이므로, 비트 연산으로 여러 시드를 한 번에 검사할 수 있습니다. PHast 논문은 이 방식으로 구축을 한 자릿수 배 빠르게 했다고 적습니다.

대가는 자기 충돌(self-collision)입니다. 한 시드에서 겹친 두 키는 함께 움직이므로 거의 모든 시드에서 계속 겹칩니다. PHastR 논문에 따르면 PHast+ wrapping(δ=3, λ=5)이 10⁷개 키의 첫 레벨에서 범핑한 버킷의 35%에 자기 충돌이 있었습니다.

PHastR는 시드의 하위 2비트로 레이아웃 4개 중 하나를 고르고, 나머지 비트로 회전량을 정합니다. 레이아웃마다 버킷 계산에서 남은 64비트 값의 서로 다른 비트를 오프셋으로 쓰므로, 자기 충돌이 레이아웃마다 독립적으로 일어납니다.

한 레이아웃 안에서는 배치가 여전히 가산이라 비트 병렬 탐색을 유지합니다. 원문은 표의 세 구조가 주로 배치 함수 p(s, h)에서 다르다고 적습니다. 레이아웃은 배치 함수를 바꾸며, 범핑된 키를 다음 레벨과 Elias-Fano 재매핑으로 보내는 경로는 세 구조가 같은 틀을 씁니다.

레이아웃 수만 바꾼 절제 실험이 이 효과를 분리합니다. 조건은 10⁹개 키, S=8, 슬라이스 길이 L=1024, λ=4.25, 단일 스레드 구축입니다.

질의 시간은 레이아웃 수와 관계없이 같은 공통 코드로 측정한 값입니다. 반면 4개 레이아웃의 구축 시간에는 전용 코드의 효과도 포함됩니다. 원문에 따르면 레이아웃이 4개일 때만 키의 링 비트가 한 워드에 들어가고, 구축이 이 구성에 맞춘 코드를 씁니다.

해시 함수와 시드 폭, 버킷 크기를 고정한 채 레이아웃만 늘렸는데 범핑과 공간, 질의 시간이 함께 줄었습니다. 10⁷개 키에서 레이아웃이 1개일 때 자기 충돌이 있는 버킷은 키의 1.28%만 담았지만, 범핑된 키의 71%를 차지했습니다.

전체 비교에서도 결과는 같은 방향입니다. 10⁹개 키에서 PHastR(λ=4.25)는 1.942 bits/key로 PHast+ wrapping δ=7(λ=5)의 1.939와 거의 같습니다. 첫 레벨 범핑은 0.5%와 3.9%이고, 질의는 15.3 대 23.2 ns로 34% 빠릅니다.

단일 스레드 구축 시간은 44 대 113 ns/key이며, 저자는 이를 38% 수준으로 적습니다(계산값 38.9%). 8스레드 구축은 6.3 대 17.9 ns/key입니다. PHastR의 구축 시간에는 앞에서 설명한 4개 레이아웃 전용 코드의 효과도 들어 있습니다.

이 비교는 구현(sux 크레이트 대 ph 크레이트)과 λ가 다른 구조 사이의 비교이며, 저자는 질의 차이를 범핑 차이로 설명합니다. 앞의 절제 실험은 같은 구현 안에서 레이아웃 수만 바꿨다는 점에서 이 설명을 보완합니다.

범핑에는 바닥이 있습니다

범핑을 0으로 만들 수는 없습니다. PHast 계열에서 키는 슬라이스 시작점부터 W개 슬롯 안에만 놓일 수 있으며, 이 구간을 도달 범위(reach)라고 합니다. PHastR에서는 W가 슬라이스 길이 L과 같습니다.

논문의 명제 1~3은 키 수와 슬롯 수가 같고 슬라이스 시작점이 독립·균등하다고 봅니다. 이 가정에서 키가 많으면 어떤 배치든 일정 비율의 키를 범핑해야 합니다. 논문은 기대 범핑 비율의 점근 하한을 약 0.1/W로 유도하고, 포아송 모델에서 최선의 배치가 약 1/(2W)를 범핑한다고 증명합니다.

PHastR의 W=1024에서 이 바닥은 0.049%이고, 10⁹개 키에서 탐욕 배치로 계산한 최솟값은 0.050%였습니다. 바닥 자체의 공간 비용은 약 0.006 bits/key이고, PHastR의 범핑 0.51%는 바닥의 약 10배입니다. 슬롯이 (1+ε)n개이면 이 손실은 εW에 대해 지수적으로 줄어듭니다.

저자는 남은 차이가 주로 도달 범위보다 시드 제약에서 온다고 해석합니다. 버킷 하나가 고를 수 있는 배치가 $2^S - 1$개뿐이기 때문입니다. 저자는 바닥에 도달하는 탐색이 공간을 1.94에서 약 1.89 bits/key로 줄인다고 계산하고, 이 약 0.05 bits/key를 더 나은 탐색이 줄일 수 있는 여지로 봅니다.

원문이 남긴 열린 문제는 이것 말고도 있습니다. 더 작은 구조로 마지막 레벨들을 대체하는 문제와, 크기를 정확히 아는 부분집합 안에서 범핑 없는 배치를 효율적으로 찾는 문제입니다.

동적 구조에서 비용이 모이는 삭제 슬롯

선형 탐사는 키 v의 해시 위치 h(v)부터 v나 빈 슬롯을 만날 때까지 앞으로 훑습니다. 삭제한 슬롯을 빈 슬롯으로 되돌리면 그 뒤에 놓인 키의 탐색 경로가 끊깁니다. 그래서 구현은 뒤쪽 키를 당겨 오거나, 탐색이 지나가도록 툼스톤(tombstone)을 남깁니다.

Meta의 F14 소개 글은 툼스톤의 비용을 이렇게 설명합니다. 삽입과 삭제가 섞인 워크로드에서 툼스톤이 쌓이면, 탐색 성능은 적재율이 높은 테이블처럼 나빠지고 메모리 효율은 적재율이 낮은 테이블처럼 떨어집니다. 해시 함수나 탐사 규칙을 바꾸지 않아도 삭제 처리만으로 두 비용을 함께 치르는 셈입니다.

F14는 14슬롯 청크마다 1바이트 카운터를 두고, 그 청크에 놓이려 했지만 다른 청크에 저장된 키의 수를 셉니다. 키를 지울 때는 그 키의 탐사 경로에 있는 모든 청크의 카운터를 줄입니다. 카운터가 0이면 그 청크를 거쳐 다른 청크로 넘어간 키가 없으므로, 탐색은 그 청크에서 멈출 수 있습니다.

여러 스레드가 동시에 테이블을 고치면 선택지가 더 좁아집니다. Attiya, Oshman, Schiller의 논문은 기존 동시성 선형 탐사 설계를 삭제 방식별로 비교합니다. U는 키 도메인 크기, n은 프로세스 수입니다.

표의 셀 크기는 논문 표 1의 값이며, 크기 조정에 쓰는 보조 공간을 포함하지 않습니다. 마지막 두 행이 이 논문의 설계입니다.

툼스톤을 다시 쓰면 생기는 중복

이 논문은 툼스톤을 새 삽입에 다시 씁니다. 그러면 같은 키를 동시에 넣는 삽입들이 서로 다른 툼스톤을 보고, 같은 키의 임시 복사본(tentative copy)을 여러 곳에 쓸 수 있습니다. 슬롯 재사용이 공간 문제를 해결하는 대신 정확성 문제를 만듭니다.

논문은 탐사 순서로 우선권을 정합니다. h(v)에 더 가까운 복사본이 이기고, 살아남는 복사본은 h(v) 쪽으로만 이동합니다. 경쟁 삽입은 뒤쪽 임시 복사본에 COLLIDED를, 삭제는 DELETED를 쓰고, 그 복사본을 만든 삽입이 셀을 툼스톤으로 정리합니다.

조회도 이 정리에 참여합니다. 조회가 확정되지 않은 복사본을 근거로 true를 반환할 때는 그 셀에 revalidate를 써서 원래 삽입에 중복 검사를 다시 요청합니다. 복사본이 h(v) 쪽으로 옮겨질 수 있으므로, 전진 탐색에서 결론이 나지 않으면 런(run)의 끝에서 h(v)까지 후진 탐색을 한 번 더 합니다.

셀당 메타데이터는 작게 유지됩니다. LL/SC 버전은 키 외에 태그 2비트와 예약 값 하나를 쓰고, CAS 버전은 셀 인덱스나 프로세스 식별자를 위해 min(⌈log n⌉, ⌈log m⌉)비트를 더합니다. 여기서 m은 셀 수입니다.

정확성 보장은 넓고 비용 분석은 좁습니다. 알고리즘은 같은 키의 동시 삽입이 있어도 linearizable하며, 조회는 wait-free, 삽입과 삭제는 lock-free입니다. 반면 기대 상각 단계 수 O(x²+c)를 보인 정리 21은 다음 조건을 모두 둡니다.

• x > 1이고, 적재율을 1 − 1/x로 나타냅니다.
• 연산 묶음은 해시 함수를 고르기 전에 정하며, 최악의 스케줄러가 그 안에서 실행 순서를 정합니다.
• 묶음의 삽입 호출은 (1 − 1/x)m 이하입니다.
• 어느 순간에도 같은 키의 활성 삽입은 최대 하나입니다.
• 같은 키를 대상으로 동시에 겹치는 연산은 최대 c개입니다.

조회가 공유 셀에 쓰는 비용은 LRU를 대체하는 FIFO 캐시 축출에서 다룬 LRU 히트 경로의 쓰기와 같은 종류입니다. 다만 이 조회는 확정되지 않은 복사본을 만날 때만 쓰므로, 경합이 낮으면 그 비용도 작을 것으로 추정합니다.

이 주장이 약해지는 조건

키 집합이 작으면 범핑 비용이 작습니다. PHastR 논문에서 10⁷개 키는 구조가 캐시에 들어가는 규모이며, 범핑된 키의 추가 질의 시간이 약 45 ns, 범핑 1%당 평균 0.5 ns 이하였습니다. 이 규모에서는 범핑 비율보다 구축 시간이나 bits/key를 먼저 보는 편이 맞을 수 있으며, 이는 판단입니다.

해시 함수가 비트를 고르게 섞지 못하면 우선순위가 바뀝니다. F14 글은 정수용 std::hash가 흔히 항등 함수라서, 하위 5비트만 쓰면 32의 배수인 키가 많이 충돌한다고 설명합니다. PHastR 비교는 모든 구조에 같은 GxHash를 써서 해시 품질을 고정했으므로, 품질이 낮은 해시 함수의 경우에는 답하지 않습니다.

삭제가 없는 워크로드에서는 툼스톤이 생기지 않으므로, 삭제 슬롯 처리가 비용을 정하는 비중이 작다고 판단합니다. 툼스톤을 재구축으로 치우는 설계는 툼스톤의 비용 대신 재구축 비용을 치릅니다.

근거의 범위도 좁습니다. PHastR 수치는 저자 한 명이 64비트 정수 키로 한 기종에서 측정한 결과이고, 10⁹개 키의 구축은 한 번만 측정했습니다.

같은 논문의 v2는 Intel Xeon Platinum 8488C에서 구축 시간 37% 수준과 질의 28% 단축을 보고했습니다. v3는 AMD EPYC 9R45와 수정한 구현으로 각각 38%와 34%를 보고합니다.

동시성 논문은 구현 벤치마크를 싣지 않았습니다. 비용 분석은 툼스톤 재사용을 일부러 무시하고, 삽입된 키가 삭제 뒤에도 자리를 차지한다고 봅니다. 그래서 O(x²+c) 상한은 삭제된 키를 포함한 누적 삽입 수가 (1−1/x)m 이하인 구간에만 적용됩니다.

같은 이유로 툼스톤 재사용이 런 길이를 실제로 얼마나 줄이는지는 이 논문으로 알 수 없습니다. 테이블 크기 조정도 범위 밖이며, 빈 셀을 찾지 못한 삽입은 ABORT를 반환합니다.

소스가 답하지 않은 질문도 있습니다. F14식 카운터를 lock-free 툼스톤 재사용과 결합한 설계나, 두 방식을 같은 워크로드에서 측정한 비교는 이 글의 소스에 없습니다.

충돌 뒤처리를 확인하는 기준

해시 구조를 고르거나 구현할 때는 다음 질문을 차례로 확인합니다.

• 키 집합이 고정인가? 고정이면 MPHF가 후보이고, bits/key와 함께 첫 레벨 범핑 비율과 범핑된 키의 질의 경로를 확인합니다.
• 구조가 캐시보다 큰가? 크면 범핑 1%의 질의 비용이 커집니다. PHastR 저자는 이 이유로 λ=4.5보다 0.04 bits/key를 더 쓰는 λ=4.25를 기본값으로 권하며, λ=4.5는 10⁹개 키에서 질의가 10% 느렸습니다.
• 삽입과 삭제가 섞이는가? 섞이면 툼스톤을 재구축, F14식 카운터, 툼스톤 재사용 가운데 어떤 방식으로 치우는지 확인합니다. 오래 도는 워크로드는 누적 삽입 수가 앞의 O(x²+c) 분석 한도를 넘을 수 있으므로, 그 구간의 비용은 측정으로 확인합니다.
• 여러 스레드가 같은 테이블을 고치는가? 그렇다면 툼스톤 재사용 여부, 셀당 메타데이터 비트, 조회가 셀에 쓰는지, 테이블이 찼을 때의 처리를 확인합니다.

충돌한 키를 다른 후보 자리로 옮기는 재배치형 구조도 같은 질문으로 볼 수 있습니다. 쿠쿠 해싱의 킥아웃 체인과 재해시 비용은 쿠쿠 해싱과 지문 필터에 정리했습니다.

참고 자료

• PHastR: Faster Minimal Perfect Hashing with Rotated Layouts, arXiv:2610.17833 (2026-10, v3 기준)
• PHast – Perfect Hashing made fast, arXiv:2504.17918 (2025-04, ALENEX 2026)
• Space-Efficient Lock-Free Linear-Probing Hash Table, arXiv:2606.17315 (2026-06)
• Open-sourcing F14 for faster, more memory-efficient hash tables, Engineering at Meta (2019-04)

모든 수치는 2026-10 기준으로 각 원문에서 대조했습니다.

정리

이 글의 사례에서는 해시 함수와 첫 레벨 질의 비용이 같아도 충돌 뒤처리에 따라 비용이 달랐습니다. PHastR는 같은 해시 함수와 시드 폭에서 배치 레이아웃만 늘려 범핑을 1.79%에서 0.51%로 줄였고, 그 결과 10⁹개 키에서 공간과 질의 시간이 함께 줄었습니다. Attiya 등의 설계에서는 툼스톤 재사용을 위해 중복 복사본 정리, 후진 탐색, 조회의 재검증 요청을 씁니다.

정적 구조에서는 키 집합이 크고 해시 함수가 비트를 고르게 섞을 때 이 기준이 가장 잘 맞으며, 작은 키 집합에서는 범핑 비용이 작습니다. 동적 구조에서는 삽입과 삭제가 섞일 때 이 기준이 맞지만, 동시성 논문은 실측 성능을 제시하지 않았습니다. 해시 구조를 고를 때는 bits/key, 평균 프로브 수와 함께 범핑 비율과 삭제 슬롯 처리 방식을 확인합니다.