One of the first advanced programming techniques I learned back when I was beginning was the use of hashing for fast table lookup. The use of the adjective “advanced” probably looks strange to younger engineers who are used to languages like Perl, Python, and others that have dictionaries or hash tables built in but they weren’t as well known back then except, of course, that Lisp already had them. Regardless, I was fascinated with the technology and read everything I could find about them. During my career I’ve implemented hashing tens or even hundreds of times.
Attractivechaos over at Attractive Chaos has a very nice post on Advanced techniques to implement fast hash tables. He begins by noting that open hashing is very often faster than the chaining method. That’s a bit counterintuitive for me, perhaps because chaining seems more deterministic even though it really isn’t.
He then goes on to discuss some advanced techniques that can be used to speed up hashing. He concludes by noting that the choice of a hashing library is always a tradeoff and there is no “best choice.” He says there probably isn’t even a best choice for the fastest hashing method.
It’s a fairly short post and well worth reading for anyone who uses hashing in any way more significant that just using Perl or Python’s associative arrays.