Java Reference
In-Depth Information
private
int
computeHash(String s)
{
int
hash = 0;
for
(int i = 0; i < s.length( ); i++)
{
hash += s.charAt(i);
}
return hash % SIZE;// SIZE = 10 in example
}
For example, the ASCII codes for the string
"dog"
are as follows:
d
-> 100
o
-> 111
g
-> 103
The hash function is computed as follows:
Sum
=
100 + 111 + 103
= 314
Hash = Sum % 10 =
314 % 10
= 4
In this example we first compute an unbounded value, the sum of the ASCII values in
the string. However, the array was defined to only hold a finite number of elements. To
scale the sum to the size of the array, we compute the modulus of the sum with respect to
the size of the array, which is 10 in the example. In practice the size of the array is generally
a prime number larger than the number of items that will be put into the hash table.
4
The
computed hash value of 4 serves like a fingerprint for the string
"dog"
. However, different
strings may map to the same value. We can verify that
"cat"
maps to (99
+
97
+
116) %
10 = 2 and also that
"turtle"
maps to (116
+
117
+
114
+
116
+
108
+
101) % 10 = 2.
A complete code listing for a hash table class is given in Display 15.34, and a dem-
onstration is provided in Display 15.35. The hash table definition in Display 15.34
uses an array in which each element is a
LinkedList2
class defined in Display 15.7.
Display 15.34
A Hash Table Class
(part 1 of 2)
1
public
class
HashTable
2{
3
// Uses the generic LinkedList2 class from Display 15.7
4
private
LinkedList2[] hashArray;
5
private
static
final
int
SIZE = 10;
6
public
HashTable( )
7
{
8
hashArray =
new
LinkedList2[SIZE];
(continued)
4
A prime number avoids common divisors after modulus that can lead to collisions.
