Java Reference
In-Depth Information
Display 15.33
Constructing a Hash Table
1. Existing hash table initialized with 10 empty linked lists
hashArray = new LinkedList 3[ SIZE]; // SIZE = 10
0
1
2
3
4
5
6
7
8
9
hashArray
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
2. After adding “cat” with hash of 2
0
1
2
3
4
5
6
7
8
9
empty
empty
empty
empty
null
empty
empty
empty
empty
hashArray
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 compute
the hash value is shown next:
private int
computeHash(String s)
{
int
hash = 0;
