Many algorithms and data structures assume access to a family of hash functions satisfying some nice property (say, $k$-independence or $k$-universality). In these cases, we usually assume that we sample hash functions from these families uniformly at random.

Are there any instances of an algorithm or data structure sampling from a family of hash functions in a way that isn’t uniformly at random? For example, do any randomized algorithms or data structures sample from hash families using other distributions to, say, bias where elements end up hashing or to introduce some correlations among hashed values?

  • $\begingroup$ One tricky thing with this question is that, in some sense, picking a hash function uniformly at random from a 3-independent family is very similar to picking a hash function from a 2-independent family non-uniformly at random, where the family strictly includes the 3-independent family and the non-uniformity comes from the probability of all the additional functions being 0. Maybe we should think about this as non-uniformity in a set where there are at least two functions with distinct non-zero probabilities? $\endgroup$
    – jbapple
    May 18, 2020 at 4:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.