Java Reference
In-Depth Information
Display 15.33
Constructing a Hash Table
1. Existing hash table initialized with ten empty linked lists
hashArray = new LinkedList 3[SIZE]; // SIZE = 10
0 1 2 3 4 5 6 7 8 9
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
hashArray
2. After adding "cat" with hash of 2
0 1 2 3 4 5 6 7 8 9
hashArray
empty
empty
empty
empty
null
empty
empty
empty
empty
cat
3. After adding "dog" with hash of 4 and "bird" with hash of 7
0 1 2 3 4 5 6 7 8 9
hashArray
empty
empty
empty
empty
empty
empty
empty
cat
dog
bird
4. After adding "turtle" with hash of 2 - collision and chained to linked list with "cat"
0 1 2 3 4 5 6 7 8 9
empty
empty
empty
empty
empty
empty
empty
hashArray
turtle
dog
bird
cat
A Hash Function for Strings
A simple way to compute a numeric hash value for a string is to sum the ASCII value
of every character in the string and then compute the modulus of the sum using the
size of the fixed array. A subset of ASCII codes is given in Appendix 3. Code to com-
pute the hash value is shown below:
