Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Not to appear overly Bayesian here, but shouldn't the prior probabilities of the objects themselves be factored in?

I mean, in most real-life situations you probably won't know ahead of time which objects you're going to have to hash (or else you could hash them perfectly anyway).



In theory, you can treat the objects as i.i.d. giving them a uniform prior.

In practice, of course only the inputs are inputs and if you were to take that into account then you could avoid collisions, but as you say, you can't really know that ahead of time.

Unless you can, such as when there is structure to the inputs or some other source of non-uniformity that you can account for. The topic of learned indexes is worth investigating if you're interested:

https://arxiv.org/abs/1712.01208

https://arxiv.org/abs/2012.12501


> of course only the inputs are inputs and if you were to take that into account then you could avoid collisions

Sorry, I don't understand?!


If you could time travel (backwards) to before you got the inputs that needed to be stored in a hash table, you could come up with a hash function that would not have any collisions with your inputs, and also know how big your initial hash table would need to be. This is kind of what the GP comment was saying, that the values to be put into the hash are biased to be the values we will be storing there.

My point is that even though we can't predict future or talk with our past self, we can sometimes know enough about the class of inputs (the string's contents, or the values in the key fields of a struct) that we can learn a more special hash function with low collision rate and high density. At very large scale this can have a measurable effect.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: