Hash Table Strategies

One problem with hash tables is there's a lot of ways to structure them. Most people are aware of "open addressing" versus "chaining", but there's more.

A lot of times when you see someone report some result about hashing, you have to wonder if they've even picked the optimal form of hashing to try to improve (see, for instance, results about Robin Hood hashing).

But of course there isn't even an "optimal form"; there are a lot of possible strategies, and the optimal strategy is going to depend on how big the keys are, how fast hashing is, how fast the key comparisons are, and how big the values are--so there isn't ever going to be one right answer.

Anyway, in 2010 I made a failed attempt to implement every possible strategy I could think of to compare them all in practice. (I wrote most of the code, but never got around to debugging it and measuring it.)

Here is the list of strategies I brainstormed, at least at the data structure level (this ignores double hashing vs linear probing).

Ignore the word "bucket" if there's no red box. Also note these are not hash chains, it's still open addressing, just indirecting key & value. Hash chains later.