Hash tables - Data Structures and Problem Solving Using Java - page 778

somewhat similar. Two such examples were maps in which the keys were
URLs such as http://www.cnn.com/ and maps in which the keys were complete
filenames, such as
/a/file.cs.fiu.edu./disk/storage137/user/weiss/public_html/dsj4/code .
Performance in these maps degraded considerably because the keys
generated relatively few unique hash codes.
In Java 1.2, the hashCode was returned back to the simpler version, with 31
used as the constant multiplier. Needless to say, the programmers who designed
the Java library are among the most gifted on the planet, and so it is easy to see
that designing a top-notch hash function can be laden with pitfalls and is not as
simple as it may seem.
In Java 1.3, a new idea was attempted, with more success. Because the
expensive part of the hash table operations is computing the hashCode , the
hashCode method in the String class contains an important optimization: Each
String object stores internally the value of its hashCode . Initially it is 0, but if
hashCode is invoked, the value is remembered. Thus if hashCode is computed
on the same String object a second time, we can avoid the expensive recom-
putation. This technique is called caching the hash code, and represents
another classic time-space tradeoff. Figure 20.4 shows an implementation of
the String class that caches the hash code.
Caching the hash code works only because String s are immutable: if
the String were allowed to change, it would invalidate the hashCode , and the
hashCode would have to be reset back to 0. Although two String objects with
the same state must have their hash codes computed independently, there are
many situations in which the same String object keeps having its hash code
queried. One situation where caching the hash code helps occurs during
rehashing, because all the String s involved in the rehashing have already had
their hash codes cached.

public final class String

figure 20.4
Excerpt of String
class hashCode

1

{ 2

public int hashCode( ) 3

{ 4

if( hash != 0 ) 5

return hash; 6

7
8 for( int i = 0; i < length( ); i++ )
9 hash = hash * 31 + (int) charAt( i );
10 return hash;
11 }

12
13

private int hash = 0;

} 14