3 ms·

Does anyone know if there are any similar studies for hash tables (e.g. algorithm, bucket layouts, probe sequences)?

• nkurz 11y ago
  Not quite what you are asking for, but I think this is a similarly smart paper about Cuckoo Hashes that takes the right approach for modern processors, and includes some background on how other approaches fare: http://www.cs.columbia.edu/~orestis/sigmod15.pdf http://www.cs.columbia.edu/~orestis/sigmod15.pdf
  • uxcn 11y ago
    Interesting results. Thanks, I'll have to take a deeper look through the paper. Cuckoo hashing seems to be the standard, but I still haven't seen concrete numbers comparing different variations or other schemes like hopscotch particularly for latency and throughput. Hopscotch seems like it might give better latency. For simple stuff, I've found that a good hash and linear probe generally outperforms other simple schemes up to roughly 50% load, but I honestly haven't really had a need to dig further into other schemes so far.