Hash tables are one of the most popular data structures in computer science. The promised land of constant time lookups, even if amortized, is hard to resist, but we all know that software engineering is all about trade-offs and hashing is also not free - usually we have to read the entire input into memory in order to compute the hash code. Well, we can leverage another trade-off here and use a few bytes of memory to store the computed hash code so that we can avoid its recomputation.
To make things concrete, let’s illustrate this using
Nothing fancy here - we use a hashcode field to store precomputed hash code value. This can be done lazily and hash computation logic is intentionally terrible. Now, we can use this field when using std::hash
Let’s see what compilers produce in order to compute the hash
Not bad - we just do a single memory read
But, you’ve probably noticed that we’ve added constexpr to CachedHash constructor, so why don’t we take advantage of it and see what happens for
And, as expected, compiler magic reduced everything to a trivial constant move
This technique can be useful for cases when you have a hashtable with a limited number of keys you know in advance, since we can define all of them as constexprs and not waste any runtime cycles for hash computation.
In the future, we may explore ways to get this to a next level and precompute the hashtable as well - in fact we can find ideal hash function that would generate unique hash values for statically known keys, so that hashtable has 0 wastage with open-addressing.