Java Reference
In-Depth Information
715
S
ELF
C
HECK
5.
If a hash function returns
0
for all values, will the
HashSet
work
correctly?
6.
What does the
hasNext
method of the
HashSetIterator
do when
it has reached the end of a bucket?
16.4 Computing Hash Codes
A hash function computes an integer hash code from an object, so that different
objects are likely to have different hash codes. Let us first look at how you can
compute a hash code from a string. Clearly, you need to combine the character values
of the string to yield some integer. You could, for example, add up the character
values:
int h = 0;
for (int i = 0; i < s.length(); i++)
h = h + s.charAt(i);
However, that would not be a good idea. It doesn't scramble the character values
enough. Strings that are permutations of another (such as
ÐeatÑ
and
ÐteaÑ
) all
have the same hash code.
Here is the method the standard library uses to compute the hash code for a string.
final int HASH_MULTIPLIER = 31;
int h = 0;
for (int i = 0; i < s.length(); i++)
h = HASH_MULTIPLIER * h + s.charAt(i);
For example, the hash code of
ÐeatÑ
is
31 * (31 * 'e' + 'a') + 't' = 100184
The hash code of
ÐteaÑ
is quite different, namely
31 * (31 * 't' + 'e') + 'a' = 114704
(Use the Unicode table from Appendix B to look up the character values:
ÓaÓ
is 97,
Ó
eÓ
is 101, and
ÓtÓ
is 116.)
