Adaptive Hashing
a year ago
- #hashing
- #SBCL
- #optimization
- The talk at ELS 2024 focused on adaptive hashing to improve general-purpose hash tables by making them faster and more robust.
- Hash table theory often ignores constant factors, which are crucial in practice, and assumes random hash functions, whereas real-world use involves fixed hash functions.
- Perfect Hashing optimizes hash functions for a fixed set of keys but is impractical for general use due to inflexibility or high computational cost.
- Adaptive hashing aims to improve performance by adjusting the hash function dynamically based on actual key usage, reducing collisions and improving cache efficiency.
- SBCL's adaptive hashing implementation starts with a simple constant hash function and switches to more complex functions based on collision rates and table size.
- For EQ hash tables, SBCL transitions from linear search to optimized hash functions (like single-shift or Murmur) as the table grows or collision rates increase.
- For EQUAL hash tables, adaptive hashing reduces the cost of hashing composite keys by limiting the parts of the key that are hashed initially, expanding only if collisions are high.
- SBCL's adaptive hashing has been in use for nearly a year, improving speed in common cases and robustness in others.