Mastodawn

Radek Jurga Sep 26, 2023

@pkhuong I'm reading your article http://pvk.ca/Blog/more_numerical_experiments_in_hashing.html

There is a claim that I would like to understand better: "The table’s layout is independent of the insertion order."

To me, it seems that for two keys that hash to the same value, the relative order of the entries will depend on which is inserted first, even though they will be in adjacent slots. Am I understanding that wrong?

So, by layout, do you just mean which slots are occupied, and not the order of entries?

More numerical experiments in hashing: a conclusion - Paul Khuong mostly on Lisp

Show thread

Paul Khuong

@rjurga For the layout of a hash table that only looks at the hash values, we must consider entries equivalent when they have the same hash value. That's useful in the context of understanding what impact history has on the hash table's performance. (The quote itself is taken from a section that explains how a Monte Carlo approach doesn't have to simulate a specific sequence of inserts and deletions to estimate the performance under various loads.)

If you really want a deterministic representation, you have to break ties by sorting on the keys, when the hash is equal (rare enough, hopefully).