Random Hash Functions

http://research.swtch.com/randhash

by mdwrigh2 • 14 years ago

38 10 14 years ago

research.swtch.com

ezyang3• 14 years ago

Which is distinct from a "totally random hash function", which is a hash function for which the hash associated with every value is uniformly randomly selected from the key space. Totally random hash functions have very good properties, but they take a lot of space to store. (Exercise for the reader: if the hash function is {0,1}^n -> {0,1}^m (so the input is an n-bit string, and the output is an m-bit string), how much space do you need? Why isn't this compressible?)

peterwwillis• 14 years ago

....not sure if april fools joke or if i'm just really dumb

tantalor• 14 years ago

> Since the inputs are identical

They aren't identical because NaN != NaN. That's what "identity" means.

barrkel3• 14 years ago

I had to AdBlock typekit.com in order to disable the custom font on this site; normally Firefox config option gfx.downloadable_fonts.enabled disables custom fonts, but not here.

(I think the "idea" presented here is silly; I think it's an April Fools. Any given NaN (IEEE NaNs have lots of different representations) should hash consistently and compare consistently with functions specific to the requirements of hash tables, i.e. one for which NaN = NaN for any given NaN. You shouldn't be able to store multiple NaNs in the hash table (unless you're specifically using distinct NaNs) no more than you can store multiple keys for '1.0', so there should be no quadratic explosion.)

(Oh and furthermore: I only know rudimentary Python, but timeit taking a string parameter for the code to time rather than a lambda is revolting.)

ezyang3• 14 years ago

Did you run the code?

The reason why the behavior here is bad is because Python uses probing to implement hash collision detection. Essentially, once you've looked up the hash, you have to check to make sure the value stored at this hash is actually the key you are looking for. However, floating point equality is different from bit-wise equality, and so once a NaN is stored as a key in the table it's unretrievable, since it will always report that it's not equal to any key you may be looking for.

Maybe it's April Fool's, but only in the fine tradition of WTF but true.

barrkel3• 14 years ago

I'm completely uninterested in the specifics of how Python hash tables are implemented; in other words, the code is irrelevant. What concerns me is the logic of hash functions as applied to hash tables, as a language independent concern.

Hash tables require certain things from the key hash and compare functions. If language defaults are used for comparing, particularly with NaNs, then hash tables break down. The fix isn't to make your hash function random; it's to make your compare function conform to the requirements of hash tables.

avar• 14 years ago

This is off-topic but is there an official Google API + snippet for embedding Google+ comments in a non-Google+ page like that? He seems to have some hardcoded custom JavaScript code for it, is there no easy official way to do so?

Random Hash Functions

Related Stories