Modern Perfect Hashing
7 months ago
- #perfect-hashing
- #string-processing
- #optimization
- 现代字符串完美哈希的目标是将固定字符串集高效映射到预定义的整数上。
- 该方法通过按字符串长度分组来优化边界检查和SIMD内存比较。
- 曾考虑使用PEXT（位提取）技术，但因表格过大及Arm/部分x86 CPU不支持而被放弃。
- 受计算机象棋启发的解决方案采用魔术数将稀疏位转换为无冲突哈希表。
- 以4字符CSS关键词为例，演示如何用魔术数实现零碰撞表索引。
- 当键值较少时，简单内存比较已足够，无需复杂哈希计算。
- 魔术数搜索采用试错法，通过杀手启发式快速排除无效候选值加速过程。
- 若找不到魔术数，建议根据字符检查分组处理，但性能表现不稳定。
- 最终实现速度比gperf快两倍且代码量减半，但搜索过程耗时较长。