PTHash(2024) 논문이 완벽해싱에서 우수한 성능을 보이는것 으로 알려져 있는데 충돌처리를 어떻게 하고 있는지 알려줘 0%인가요? - tlooto, The Most Powerful AcademicGPT

완벽 해싱에서 PTHash(Probabilistic Two-level Hashing)는 충돌이 전혀 없는 minimal perfect hash function (MPHF)을 구축하는 최신 기법입니다. 즉, 최종적으로 완성된 PTHash 구조에서는 충돌이 0%, 즉 어떤 두 키도 동일한 해시 인덱스로 매핑되지 않습니다[1][2]. 하지만, 이 결과에 이르기까지의 처리 방식에 대한 중요한 세부 사항들이 존재합니다. --- PTHash의 충돌 처리 과정 1. 두 단계 구조 - 1단계(Global Hashing): 전체 키 집합 $S$를 수십수백 개의 bucket으로 분할하는 전역 해시 함수를 사용합니다. 이 단계에서는 임의의 충돌이 발생할 수 있습니다. 그러나 각 bucket 내에서는 별도로 완벽 해시 구조를 구축하므로 충돌이 해결될 준비 단계에 불과합니다[1][2]. - 2단계(Local MPHFs): 각 bucket 내에서 bucket에 포함된 키 집합만을 대상으로 별도의 minimal perfect hash function을 생성합니다. 이 때는 각 bucket이 독립적으로 처리되므로, 충분한 randomization(난수화)와 여러 candidate 함수(파라미터) 선택을 반복해 충돌이 없도록 합니다. 2. 충돌 해소는 어떻게 하는가? - 각 bucket에서 MPHF를 만들 때 충돌(같은 인덱스에 두 키가 매핑되는 상황)이 발생하면 해당 bucket에 대한 파라미터 또는 해시 함수의 시드값을 변경(재시도)합니다. - 이 과정은 bucket 별로 독립적이기 때문에 병렬화(parallelization)에 매우 적합하고, 평균적으로 빠른 시간 내에 충돌 없는 상태에 도달할 수 있습니다. 실험적으로 재시도 횟수는 작으며, 전체 빌드 시간과 공간 효율성 모두 매우 우수합니다[1]. 3. 최종 결과의 충돌률 - 완벽 해시 함수의 정의상, 완성된 PTHash에서는 충돌이 0%입니다. 즉, 각 키가 유일한 인덱스로 정해지므로 충돌에 대한 처리가 필요 없습니다. - 충돌이