Consistency of hashCode() on a Java string

Question

The hashCode value of a Java String is computed as (String.hashCode()):

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Are there any circumstances (say JVM version, vendor, etc.) under which the following expression will evaluate to false?

boolean expression = "This is a Java string".hashCode() == 586653468

Update #1: If you claim that the answer is "yes, there are such circumstances" - then please give a concrete example of when "This is a Java string".hashCode() != 586653468. Try to be as specific/concrete as possible.

Update #2: We all know that relying on the implementation details of hashCode() is bad in general. However, I'm talking specifically about String.hashCode() - so please keep the answer focused to String.hashCode(). Object.hashCode() is totally irrelevant in the context of this question.

• Brian Agnew: Do you actually need this functionality ? Why do you need the precise value ?
• knorv: @Brian: I'm trying to understand the contract of String.hashCode().
• mP.: @Knorv Its not ncessary to understand exactly how it works - its more important to understand the contract and its ulterior meaning.
• knorv: @mP: Thanks for your input, but I guess that's up to me to decide.
• android developer: why did they give the first character the largest power? when you want to optimize it for speed in order to preserve extra calculations, you would store the power of the previous one, yet the previous one would be from the last character to the first one. this mean there would also be cache misses. isn't it more efficient to have an algorithm of: s[0] + s[1]*31 + s[2]*31^2 + ... + s[n-1]*31^[n-1] ?

Answer 1

I can see that documentation as far back as Java 1.2.

While it's true that in general you shouldn't rely on a hash code implementation remaining the same, it's now documented behaviour for java.lang.String, so changing it would count as breaking existing contracts.

Wherever possible, you shouldn't rely on hash codes staying the same across versions etc - but in my mind java.lang.String is a special case simply because the algorithm has been specified... so long as you're willing to abandon compatibility with releases before the algorithm was specified, of course.

• Martin OConnor: The documented behaviour of String has been specified since Java 1.2 In v1.1 of the API, the hash code computation is not specified for the String class.
• Felype: In this case we better write our own hashing codes 'ight matey?
• Jon Skeet: @Felype: I really don't know what you're trying to say here, I'm afraid.
• Felype: @JonSkeet I mean, in this case we may perhaps write our own code to generate our own hash, to grant portability. Is it?
• J-16 SDiZ: most java code simply don't run in pre-1.4. it is safe to assume it is consistent.

Answer 2

I found something about JDK 1.0 and 1.1 and>= 1.2:

In JDK 1.0.x and 1.1.x the hashCode function for long Strings worked by sampling every nth character. This pretty well guaranteed you would have many Strings hashing to the same value, thus slowing down Hashtable lookup. In JDK 1.2 the function has been improved to multiply the result so far by 31 then add the next character in sequence. This is a little slower, but is much better at avoiding collisions. Source: http://mindprod.com/jgloss/hashcode.html

Something different, because you seem to need a number: How about using CRC32 or MD5 instead of hashcode and you are good to go - no discussions and no worries at all...

Answer 3

You should not rely on a hash code being equal to a specific value. Just that it will return consistent results within the same execution. The API docs say the following :

The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

EDIT Since the javadoc for String.hashCode() specifies how a String's hash code is computed, any violation of this would violate the public API specification.

• knorv: Your answer is valid, but does not address the specific question asked.
• Jon Skeet: That's the general hash code contract - but the specific contract for String gives details of the algorithm, and effectively overrides this general contract IMO.

Answer 4

As said above, in general you should not rely on the hash code of a class remaining the same. Note that even subsequent runs of the same application on the same VM may produce different hash values. AFAIK the Sun JVM's hash function calculates the same hash on every run, but that's not guaranteed.

Note that this is not theoretical. The hash function for java.lang.String was changed in JDK1.2 (the old hash had problems with hierarchical strings like URLs or file names, as it tended to produce the same hash for strings which only differed at the end).

java.lang.String is a special case, as the algorithm of its hashCode() is (now) documented, so you can probably rely on that. I'd still consider it bad practice. If you need a hash algorithm with special, documented properties, just write one :-).

• Jon Skeet: But was the algorithm specified in the docs before JDK 1.2? If not, it's a different situation. The algorithm is now laid down in the docs, so changing it would be a breaking change to a public contract.
• Tom Hawtin - tackline: (I remember it as 1.1.) The original (poorer) algorithm was documented. Incorrectly. The documented algorithm actually threw an ArrayIndexOutOfBoundsException.
• sleske: @Jon Skeet: Ah, didn't know that the algorithm of String.hashCode() is documented. Of course that changes things. Updated my comment.

Answer 5

Another (!) issue to worry about is the possible change of implementation between early/late versions of Java. I don't believe the implementation details are set in stone, and so potentially an upgrade to a future Java version could cause problems.

Bottom line is, I wouldn't rely on the implementation of hashCode().

Perhaps you can highlight what problem you're actually trying to solve by using this mechanism, and that will highlight a more suitable approach.

• knorv: Thanks for your answer. Can you give a concrete examples of when "This is a Java string".hashCode() != 586653468?
• Brian Agnew: No. Sorry. My point is that everything you test on may work the way you want. But that's still no guarantee. So if youre' working on a (say) short term project where you have control of the VM etc., then the above may work for you. But you can't rely on it in the wider world.
• Steve Jessop: "an upgrade to a future Java version could cause problems". An upgrade to a future Java version could remove the hashCode method entirely. Or make it always return 0 for strings. That's incompatible changes for ya. The question is whether Sun^HOracle^HThe JCP would consider it a breaking change and therefore worth avoiding. Since the algorithm is in the contract, one hopes they would.
• Holger: @SteveJessop well, since switch statements over strings compile to code relying on a particular fixed hash code, changes to String’s hash code algorithm would definitely break existing code...

Answer 6

Just to answer your question and not to continue any discussions. The Apache Harmony JDK implementation seems to use a different algorithm, at least it looks totally different:

Sun JDK

public int hashCode() {
 int h = hash;
 if (h == 0) {
 int off = offset;
 char val[] = value;
 int len = count;
 for (int i = 0; i < len; i++) {
 h = 31*h + val[off++];
 }
 hash = h;
 }
 return h;
}

Apache Harmony

public int hashCode() {
 if (hashCode == 0) {
 int hash = 0, multiplier = 1;
 for (int i = offset + count - 1; i >= offset; i--) {
 hash += value[i] * multiplier;
 int shifted = multiplier << 5;
 multiplier = shifted - multiplier;
 }
 hashCode = hash;
 }
 return hashCode;
}

Feel free to check it yourself...

• unwind: I think they're just being cool and optimizing it. :) "(multiplier << 5) - multiplier" is just 31 * multiplier, after all ...
• ReneS: But to make it clear from my side... Never rely on the hashcode because the hashcode is something internal.
• android developer: what are the variables of "offset", "count" and "hashCode" mean? i suppose "hashcode" is used as a cached value, to avoid future calculations, and that "count" is the number of characters, but what is the "offset" ? suppose I wish to use this code so that it will be consistent, given a string, what should i do to it?
• Kartik Chugh: @androiddeveloper See here: stackoverflow.com/questions/38546623/…
• Kartik Chugh: @androiddeveloper Now THAT'S an interesting question -- although I should have guessed it, based on your username. From the Android docs it looks like the contract is the same: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] Unless I am mistaken, this is because Android uses Sun's implementation of the String object with no changes.

Answer 7

If you're worried about changes and possibly incompatibly VMs, just copy the existing hashcode implementation into your own utility class, and use that to generate your hashcodes .

• Nick H: I was going to say this. While the other answers do answer the question, writing a separate hashCode function is probably the appropriate solution to knorv's problem.

Answer 8

The hashcode will be calculated based on the ASCII values of the characters in the String.

This is the implementation in the String Class is as follows

public int hashCode() {
 int h = hash;
 if (h == 0 && value.length > 0) {
 hash = h = isLatin1() ? StringLatin1.hashCode(value)
 : StringUTF16.hashCode(value);
 }
 return h;
}

Collisions in hashcode are unavoidable. For example, the strings "Ea" and "FB" give the same hashcode as 2236