4 ms·
The original criticism seems perfectly valid (although maybe people are reading too much into it). If you have a 32-bit hash and less than 32 bits of input, it
by iainmerrick 8y ago
The original criticism seems perfectly valid (although maybe people are reading too much into it).
If you have a 32-bit hash and less than 32 bits of input, it’s reasonable to hope all hashes might be unique. 10x extra collisions on short strings does seems pretty bad. And it’s unfortunate that this hash function can’t be changed without breaking the language spec.
- 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.