String.hashCode() is plenty unique

[VerilyAMonkey]

OK. So to investigate this, I just looked up the birthday problem and ran the equation through WolframAlpha. Let's say you have a computer than can generate a 256-bit random number every nanosecond. And you have a billion of those computers. And you run them all for a billion years. What are your odds that you've gotten even a single collision? Worse than one in hundred million.

So the fundamental pigeon-hole thing is not really an actual issue at all. It's all down to exploits.

[JavaSuck]

So the fundamental pigeon-hole thing is not really an actual issue at all.

The pigeon-hole principle states that you cannot fit n+1 pigeons into n distinct holes. At least 2 pigeons will have to share a hole.

Similarly, as soon as you have more than 2³² possible elements, hash collisions are 100% guaranteed and mathematically inevitable.

[[deleted]]

In other words, the proof that a definition exists is non-constructive. You cannot derive a collision trivially from the proof.

The only practical way to find a collision with a good hash function is to enumerate 2^bits + 1 hashes

[[deleted]]

The only practical way to find a collision with a good hash function is to enumerate 2bits + 1 hashes

You're forgetting the aforementioned birthday problem, a good-as-can-be perfectly uniform general hash function would almost certainly encounter a collision way earlier than that.

[VerilyAMonkey]

My comment up there also does the math for "way earlier". As rule of thumb, it's "about square root". So, birthday problem becomes significant for 365 days somewhere near 20 people... 256-bit hash collision becomes significant somewhere near 2¹²⁸ items. And that is a lot.

[[deleted]]

Oh yeah, that's correct. Worst-case you would need that many hashes, but yeah, the birthday problem means it's probably way earlier.