I think people here seem to implicitly assume linked buckets, those are bad on modern architectures for several reasons. Look at (Hopscotch,) Robin Hood or Cuc

I think people here seem to implicitly assume linked buckets, those are bad on modern architectures for several reasons. Look at (Hopscotch,) Robin Hood or Cuckoo Hashing for hashing with linear probing, high fill factor (~0.9) and _amortized_ O(1). I've seen a paper somewhere that proved Robin Hood worst-case O(log log n) afair. http://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul... https://en.m.wikipedia.org/wiki/Hopscotch_hashing https://en.m.wikipedia.org/wiki/Hopscotch_hashing You can make open probing performantly concurrent with 2 bytes of memory overhead per key/value too: http://preshing.com/20160314/leapfrog-probing/ http://preshing.com/20160314/leapfrog-probing/