3 ms·

The comments here have given me an idea for my own hash tables. Rather than accounting for poor hash functions using phi or fmix, I'm going to measure the hash

• twotwotwo 8y ago
  Runtime errors seem a little bit fussy, but "try a fast approach that usually works, detect worst-case behavior, then fall back to a thing that's usually slower but avoids the worst case" is a common implementation pattern (think introsort). In principle, you could start with something trivial as your hash, then rehash your key with a better-behaved-but-slower function if your normal probing strategy is going on far longer than it ought to given the load factor. But we rarely see that, and there are probably good reasons. Hash tables are more rarely the bottleneck in the real world than in benchmarks, and when they are an issue, other factors (size, concurrency, weird pathologies, mem latency) may matter more often than hashing time.