Almost all the containers we use on a regular basis provide only amortized constant time inserts.
In standard containers if you pre-define the capacity (say with std::vector::reserve) all the insertions are guaranteed to be constant time. Cuckoo hashing can't give this guarantee.
Counter-intuitively, I've also noticed in many cases that using binary search over sorted elements in contiguous memory is actually faster than using a hash table at all.
Has anyone else found this?
Sounds like you're using the wrong hash functions.
Are you using secure cryptographic hash functions perchance? (such as MD5, SHA, etc) Because they're not intended for use in data structures.
Most data structure algorithms just require a hash function with good avalanche behaviour and a statistically even bit dispersion. The FNV hash will do this for you with just a MUL and a XOR per byte, which is (rough guess) at least 100 times faster than SHA. FNV hash (http://www.isthe.com/chongo/tech/comp/fnv/) it's super-effective!
The ones that come with most languages or libraries by default quite simply aren't optimized for use on anything. There's hash functions that work better on strings and hash functions that work better on numbers (length bias). In the perfect world, this wouldn't be true, but in the real world, yes it is.
That said, may I recommend MurmurHash3: code.google.com/p/smhasher/wiki/MurmurHash3
Switch your hash tables to this. The performance difference is incredible.
The amazing part is, not only is access O(1), the expected insertion time whenever there is no rehashing is also O(1) and rehashing occurs infrequently.
http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pd...
