Get the latest tech news
Adaptive Hashing
Tags: tech, lisp, Date: 2025-05-02 At the 2024 ELS, I gave a talk on adaptive hashing, which focusses on making general purpose hash tables faster and more robust at the same time. Theory vs Practice Hash table theory most concerns itself with the asymptotic worst-case cost with a hash function chosen randomly from a family of hash functions.
The drawback is that they either require the set of keys to be fixed or they are too slow to be used as general purpose hash tables. The general idea is sound, but turning it into real performance gains is hard due to the cost of choosing a hash function and switching to it. So, SBCL hash tables have been adaptive for almost a year now, gaining some speed in common cases, and robustness in others.
Or read this on Hacker News