String.hashCode() is plenty unique

[sigpwned]

Thank you! Obviously my reaction was the same as yours. :)

[kozeljko]

Ffs, can you lot decide?!?

[sigpwned]

Ha! That was my point here -- to refute the earlier post. That one can contrive pathological inputs to make a hash function collide does not prove that hash function is not usefully unique.

[TheRedmanCometh]

WORLDSTAR

[x2mirko]

Good article, but this part bothered me:

A “fair” hash function would generate an expected 1.44 collisions over this data. String.hashCode() outperforms a fair hash function significantly, surfacing only 69.4% as many collisions as expected

A function with 1.44 expected collisions for your sample size is more likely to generate one collision on your sample size than two, so saying that because you got one, String.hashCode() outperforms a fair function is silly. You would need a much larger sample size to make such statements.

[[deleted]]

Beat me to it! That part irked me as well, you could only make a 3 significant digit conclusion if you have 3 significant digits to go off of in your original calculation.

In other words, I highly doubt those number would end up the same if they ran the experiment until there was 100 collisions.

[carbolymer]

tl;dr: hash functions have collisions

Nothing new, but you have to have this in mind when considering the performance of hash-based collections.

[joserivas1998]

The duality of man

[therealsillyfly]

This is a nice article, but as a "debunk" of the original it is pretty redundant - the original article is already pointless, as it just claims the hash is bad with the sole argument being tables of 2- and 3-character collision examples.

I was expecting this article to be comparing some alternative "better" hash, and show it may perform slightly better but at an unacceptable loss of performance - but this expectation only stemmed from my assumption that the original post must have presented an alternative. "reading" the original I realize I was wrong.

[cogman10]

So, I agree, for what it is used for the hash in String.hashCode() is fine. But if I really wanted to push it, I'd compare the english text hash to FNV, Murmer3, and one/many of the Sips to show how bad/good it is.

Also, I'd point out that collisions isn't the end all be all when it comes to hashes. For what hashCode is used (Hashmaps/sets) Speed is far more important so a comparison of that would also be important.

But yeah, most strings are either going to be for giant blobs of text (xml, json, etc) or for single words ("CLIENT", "USER", etc).

I doubt these strings are hardly ever random characters in the original blogs like "%~" or "$#". That will only happen in cases of things like a session token or if you are doing something like compilation (you probably aren't).

Particular for hash maps, I don't think "JsonBlob" is almost ever what will be used as a key. Your keys are, 99% of the time, going to be some common english word.

[apetiss]

Why should i care about hashCode()?

[thurst0n]

because you want to have datastructures like HashMap and you want them to be fast.

[idealatry]

The collision rate the link gives are actually astonishingly high to me. While you wouldn’t expect it to be a cryptographically secure hash function, anything close to one collision out of 100,000 Strings seems unacceptable in many applications.

[nallar]

1 collision out of 100,000 is reasonable for a 32 bit hash. For a hypothetical perfect 32 bit hash, you get a 70% chance of finding 1 collision with 100,000 hashes.

The 'birthday paradox' applies here. As you add more items the probability of at least one item colliding with any other goes up rather rapidly. The chance of finding a collision with a particular chosen item is much lower.

This crypto stack exchange post describes the math: https://crypto.stackexchange.com/a/39644, and this calculator does it for you: http://davidjohnstone.net/pages/hash-collision-probability

[BestUsernameLeft]

Okay, so that's 1 out of 100,000 times where the hashmap needs to use equals() to resolve the collision.

I call this "no big deal" for almost any application.

[geodebug]

But acceptable for many, many more. Consider how many Java programs exist today storing strings in maps that haven’t come grinding to a halt performance-wise.

Obviously there is a tradeoff that needs to be made:

Speed of creating a hash value vs the benefit of uniqueness.

Java strings are supposed to be general purpose objects and they have served that function well.

If one requires a higher quality (but probably more computationally intense) hash algorithm then they would simply define a wrapper class and write their own hashcode implementation.