# Computing hash of string

I want my code to be reviewed and I'd like to hear your opinions.

Sun's code to compute hash of string:

public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}


My code:

public int hashCode2() {
if (hash == 0) {
for (int i = 0; i < value.length; i++) {
hash = 31 * hash + value[i];
}
}
return hash;
}


Why I consider my code an improved version:

1. There is no need to create variables h and val as done in Sun's method.
2. The premature check of value.length > 0 is not good enough to add this complexity.
• That code, which you claim is from sun, is broken, (some places you have val and other places you have value. Is this not a copy/paste? Commented Dec 17, 2013 at 6:51
• Not sure with what you mean. This code is a copy paste, it was intended to be a copy paste. I apologize but i dint see whats broken and where? Commented Dec 17, 2013 at 10:06

I do not understand why val was introduced in addition to value – it isn't even a copy of the contents.

On the other hand h does make sense once you consider thread safety. Assume we have two threads which calculate the hash of the string at nearly the same time – to trigger this, have both threads sleep for a moment when they enter the if branch. At the beginning, both threads will have hash == 0, so they will calculate the hash anew. With the original implementation, only a local variable is mutated, and then atomicaly committed to the hash variable. With your code, both threads mutate the same hash directly and will thus compute an invalid result. Your solution would be OK iff all accesses to the hash were synchronized (by locking the whole string object for each such method which is silly when using immutable strings).

As this is Code Review, I will also suggest to return early in both implementations, instead of putting the whole calculation into an if branch. It is also nicer to use a foreach loop than to use indices.

public int hashCode() {
int h = hash; // copy for thread safety
if (h != 0 || value.length == 0) return h;

for (char c : value) {
h = 31 * h + c;
}

hash = h; // commit the change
return h;
}


On the other hand, a foreach-loop might not be as optimized as looping over the indices, and an early return could also impact what code is generated.

Edit: The value.length > 0 test in the original avoids committing the old value when no change of the hash is required (for the empty string). This can be relevant in cache-sensitive applications (remember that writing to shared memory can invalidate caches for other processors as well – we want to avoid this if possible. The condition also provides the guarantee that the loop will execute at least once if that branch is taken. Code ought to be generated in a way that this prior check does not reduce performance – on the contrary.

• val was likely introduced as a micro-optimization to take out querying the value field in the loop. I've seen that pattern a few times in Sun's code elsewhere. They likely relied on constant extraction for the value.length test (easily provable because both value and it's length field are final) Commented Dec 17, 2013 at 9:44
• @amon great answer, but whats your take on second criteria ? The premature check of value.length > 0 is not good enough to add this complexity. Do u suggest it be a included in clause for early return ? Commented Dec 17, 2013 at 10:11
• @JavaDeveloper This is very professional-looking and highly optimized code. My guess is (as I explained in my edit) that this avoids cache invalidation – but it isn't there just to look ugly.
– amon
Commented Dec 17, 2013 at 10:22
• @amon i understood your point. Very useful feedback. Commented Dec 17, 2013 at 10:25

Something to remember about the Java libraries (especially older ones) is that they were written when Java was a new language. Some of the techniques and patterns we use as standard now were not available and the compilers, optimizers etc were a lot less smart.

A lot of things we can just ignore now and let hotspot handle had to be considered in the code, and since these are core libraries that must run well on every possible Java device they cannot assume anything about the environment they run in so have to do as many optimizations as possible by hand.

Sun's code to compute hash of string:

public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}


My code:

public int hashCode2() {
if (hash == 0) {
for (int i = 0; i < value.length; i++) {
hash = 31 * hash + value[i];
}
}
return hash;
}


The separate variable h is needed for thread safety. Otherwise you could potentially have a second thread see a partially computed h (or as already mentioned have two threads calculating a hash at the same time and interfering). Both will break things badly (for example inserting a string into a HashMap with the hash wrongly calculated and you will never find that String again).

Copying value to val[] looks like a now-obsolete micro optimization.

Again the immediate check for the array being empty is a micro optimization to handle the empty string case without entering the loop.

public int hashCode() {
int h = hash; // copy for thread safety
if (h != 0 || value.length == 0) return h;

for (char c : value) {
h = 31 * h + c;
}

hash = h; // commit the change
return h;
}


This is a very nice implementation, and in fact will be just as fast as the sun one since foreach over an Array internally uses a for (i=0;..) style approach.

The problem with it is that it is not compatible with earlier versions of Java since the foreach loop is a recent addition to the language.

Micro optimisations

You will see this term a fair amount in this sort of discussion and in general it can be read to mean "something that makes such a small performance increase that it is not worth the increased code complexity". In the usual development scenario keeping code simple will reduce bugs and increase developer performance in terms of functionality provided for time spent far more than the micro optimisations can increase application performance.

In fact in some cases micro optimisations actually degrade performance as they confuse the compiler which otherwise would make the same or better optimisations behind the scene.

"Premature optimisation is the root of all evil" - Donald Knuth

This is a well known quote in this field, although actually if you go hunt down the full quote there is far more to it than the catchy tagline.

As a developer you should focus on writing clean and well structured code and on the big optimisations such as choosing the right algorithms, data structures, etc. Once that is done if you still need to increase performance then assuming you have the right algorithms and data structures (which will save far more than any amount of micro optimisation) that is when you look at progressively finer optimisations.

But keeping the code clean and readable will gain you far more in the long run...quite apart from anything else it makes it easier to get the algorithm right!

The core Java libraries are a special case as every single Java program is written on top of them, so slow performance there slows down everyone...and they have to run on every single JVM so they cannot rely on clever compilers or virtual machines.

In many cases the core Java libraries are a bad source of coding examples. Partly for that reason and partly because they were written when Java was new and people were still learning the best ways to do things. In fact the book "Effective Java" by Joshua Bloch uses examples from the core Java libraries as things NOT to do.

That's an excellent book by the way, you need some Java experience to appreciate it but I recommend it to all developers with a year or two of Java behind them.

• Very useful explanation, but "Again the immediate check for the array being empty is a micro optimization to handle the empty string case without entering the loop." - is it recommended to take effort to make a check or reduce code complexity by removing such micro optimizations - assuming cache invalidation is not a concern in some code. Commented Dec 18, 2013 at 5:11
• See the small Essay I just added Commented Dec 18, 2013 at 6:29