4 ms·
> Clearly you'll have tons of collisions with that solution Why? If we assume the hash code assignment to one of the 2^32 people is uniformly random from a se
by upquark 13y ago
> Clearly you'll have tons of collisions with that solution
Why?
If we assume the hash code assignment to one of the 2^32 people is uniformly random from a set of 2^160 codes, the odds of finding a collision are astronomically small (order of 2^-95 or so). Am I missing something?
- jules 13y agoYou are not taking the entire hash, you are only taking the first 33 bits of the hash. Since there are only about 8.5 billion different values for the 33 bits and there are about 7 billion people, the odds are astronomically low that each of those 7 billion people will receive a different one of those 8.5 billion possibilities. This is the birthday paradox with instead of 365 days you have 2^33 possible answer values and instead of 23 people you have 7 billion people. I leave it as an exercise for the reader to fill in these values into one of the formulas to calculate the probability of successfully giving each person a unique 33 bit answer: http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem
- upquark 13y ago> You are not taking the entire hash, you are only taking the first 33 bits Right, my bad, didn't pay attention to the problem we are trying to solve :)