Re:String.hashCode() is plenty unique
by FartyMcFarter on Saturday August 11, 2018 @08:09AM
(#17739371)
> 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:
Re:String.hashCode() is plenty unique
by TheCoelacanth on Saturday August 11, 2018 @08:40AM
(#17739460)
That'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.
Re:String.hashCode() is plenty unique
by FartyMcFarter on Sunday August 19, 2018 @10:35PM
(#17797383)
True - but I still don't think it's reasonable to assume that a hash function behaves that way.
Re:String.hashCode() is plenty unique
by iainmerrick on Saturday August 11, 2018 @03:29PM
(#17741144)
You 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.
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.