3 ms·

IIRC you can get to high occupancy by doing enough rehashes. After that, if you do no more insertions and only lookups, it is a good deal since each lookup tak

IIRC you can get to high occupancy by doing enough rehashes. After that, if you do no more insertions and only lookups, it is a good deal since each lookup takes at most two memory accesses. So this is useful if you are willing to spend a long time building what will then be a read-only table. Obviously there are uses for that.

dataflow 5y ago
> IIRC you can get to high occupancy by doing enough rehashes. Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than O(n^2)? And if you're going to spend a lot of time rebuilding the hash table all the time, then why not just use a perfect hash generator?
- throwaway81523 5y ago
  Large perfect hash tables have to store an awful lot of information. I don't remember quite how it's done but it's not a free lunch. The hash function itself has a size that grows with the total size of all the keys. I don't know offhand how many rehashes you need to get 98% occupancy with cuckoo hashing. There may be ways to optimize it by sharding the table into smaller ones. I'll re-read the wikipedia article when I get a chance. It's a fun algorithm and I've sometimes looked for places to use it.
- nullc 5y ago
  > Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than It depends on your bucket sizes and how many hashes you use. If you attempt 99% occupancy with 2 hashes and 4 entries per bucket, then you are going to be doing a LOT of kicking. 92% with that geometry, OTOH, is fine and will end up with just a couple kicks per insert on average.