Adaptive Hashing
a year ago
- #hashing
- #SBCL
- #optimization
- ELS 2024的演讲聚焦于通过自适应哈希改进通用哈希表，使其更快更健壮。
- 哈希表理论常忽略实际应用中至关重要的常数因子，并假设使用随机哈希函数，而现实场景中多采用固定哈希函数。
- 完美哈希针对固定键集优化哈希函数，但因缺乏灵活性或计算成本过高，不适用于通用场景。
- 自适应哈希通过根据实际键使用情况动态调整哈希函数，减少冲突并提升缓存效率，从而优化性能。
- SBCL的自适应哈希实现从简单常量哈希函数起步，依据冲突率和表大小切换至更复杂的函数。
- 对于EQ哈希表，SBCL在表扩容或冲突率上升时，会从线性搜索过渡到单位移位或Murmur等优化哈希函数。
- 对于EQUAL哈希表，自适应哈希通过初始仅哈希键的部分内容来降低复合键的哈希成本，仅在冲突率高时扩展哈希范围。
- SBCL的自适应哈希已稳定运行近一年，在常规场景中提升速度，在特殊场景中增强健壮性。