3 ms·
> If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique. No it isn't. In fact, with 16 bits of input, th
by FartyMcFarter 8y ago
> If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique.
No it isn't. In fact, with 16 bits of input, the probability of a collision is not far from 50% according to the birthday problem:
https://en.m.wikipedia.org/wiki/Birthday_attack https://en.m.wikipedia.org/wiki/Birthday_attack
- TheCoelacanth 8y agoThat's assuming random distribution of hashes. I can trivially write a hash function that produces a unique 32-bit hash for inputs of 32-bit. Just truncate the input to 32 bits. It's not a very good hash function for longer inputs, of course.
- iainmerrick 8y agoYou could do that and also use a real hash for longer inputs. Literally truncating the input wouldn’t be great in the likely case that your hash table is using only 10 bits (say) of the hash value, but I bet there are similar approaches that would work.
- FartyMcFarter 8y agoTrue - but I still don't think it's reasonable to assume that a hash function behaves that way.