fis
๐ Joined in 2009
๐ผ 27 Karma
โ๏ธ 16 posts
Load more
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
(Replying to PARENT post)
"Knuth's finding was that the dispersion of indexes for a sequence of consecutive keys is maximized when M is chosen this way, thus a multiplicative hash table with a dense set of keys will have the fewest possible collisions when M approx= 2^N * R."
Although, if the keys are dense, then we could just use the low bits directly. I guess the unstated assumption is that in the real world, we'll have a mix of keys that are sequential and keys that are strided in such a way that using low bits directly would cause a lot of collisions. So we need a multiplicative hash to take care of the latter and we should use 2^n/phi to take care of the former.
Austin, you've done a lot of great work on this. What is the hash function you'd use today for small (<=32byte) keys?
(Replying to PARENT post)
https://news.ycombinator.com/item?id=35446847