PDPH: A Performant Dynamic Perfect Hash Index with Rehashing Optimizations
Jiarui Wang, Xiangyu Zou, Wen Xia, Hao Hu, Xiangrui Meng, Xudong Li · 2025
A dynamic perfect hashing index offers collision-free assignment for entries, ensuring excellent query performance, an essential metric for the Quality of Service (QoS) in database and big data systems. Its core mechanism is rehashing, which resolves collisions during insertions by reassigning entries to distinct slots. However, rehashing is costly, as hash collisions increase linearly with the number of entries in the hash bucket, and the exponential complexity of finding a feasible reassignment. Therefore, rehashing significantly limits the insertion performance of dynamic perfect hashing indexes. To this end, we propose PDPH, a hybrid approach that enhances insertion performance by combining static and dynamic perfect hashing techniques. Specifically, (1) PDPH leverages the complementary strengths of both techniques to reduce the rehashing complexity to a linear level, rather than the exponential overhead of previous approaches. (2) It further reduces the frequency of rehashing by enforcing multiple insertions to share a single rehashing operation. (3) It also limits the scale of rehashing by allowing partial rehashing operations. Evaluations on realworld datasets suggest that, compared to the state-of-the-art approach (MapEmbed), PDPH enhances insertion throughput by up to$2.32 \times$, while maintaining query performance.