3 ms·
What he means is that to construct a particular instance of this hash function you pick random values a,b,c and do what he describes. You can make multiple diff
by gjm11 8y ago
What he means is that to construct a particular instance of this hash function you pick random values a,b,c and do what he describes. You can make multiple different hash functions by picking different random (a,b,c) triples.
Now, there are some specific choices of a,b,c that yield bad results. If you pick a=b=0 then your hash function ignores your data. If a or b is a multiple of a large power of 2 then it ignores many bits of your data. If you take e.g. (a,b,c) and (3a,3b,c') then you get two closely-related hash functions.
The specific property he's interested in here is that of being "strongly universal" which means that when you pick your hash function at random from whatever family of hash functions you've got, "on average" it behaves well. (Specifically, it means that if you fix two possible inputs and vary your hash function at random then collisions between those two inputs are as rare as they should be.) His family is strongly universal despite the issues I describe above because having enough low-order bits be zero to cause trouble is "rare enough".