Java Reference
In-Depth Information
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
+
2.
A complete code listing for a hash table class is given in Display 15.34, and a
demonstration 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 .
114
+
116
+
108
+
101) % 10
=
VideoNote
Walkthrough of
the Hash Table
Class
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];
9
for
(
int
i=0; i < SIZE; i++)
10 hashArray[i] =
new
LinkedList2( );
11 }
4
A prime number avoids common divisors after modulus that can lead to collisions.
