I have provided you with a program
called TestHash,
which is a version of the program
OpenLinear1 from the sample code.
It has been modified
to use a separate method
to choose the next location to check.
I have provided three such methods:
-
linear uses a linear probe of size one.
-
quadratic uses a quadratic probe.
-
doubleHash uses a variable-step-size linear probe.
It uses the hash value of the key to choose a step size.
Two keys that are sent to the same initial location
are likely to have different step sizes,
so they may each only have to go one step
before finding an open location.
The program is currently set up to use doubleHash.
Run the program and follow the example below,
confirming that the program is running like it should.
(Remember, the blue bits
are for you to type.)
This program creates and uses a hash table.
Press enter...
Adding 'me'
...'me' added at location 7
Adding 'myself'
...'myself' added at location 3
Adding 'I'
...'I' added at location 4
Adding 'mine'
...'mine' added at location 6
Adding 'Mark'
...location 7 is in use...
...'Mark' added at location 11
Adding 'Young'
...'Young' added at location 0
Adding 'ego'
...'ego' added at location 16
Adding 'swollen head'
...'swollen head' added at location 10
Press enter...
i hashTable[i]
- ------------
0 'Young'
1
2
3 'myself'
4 'I'
5
6 'mine'
7 'me'
8
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18
19
20
21
22
Press enter...
After the pause the program gives you some chances to add new words.
Add the words
je,
mon,
mes, and
ma.
Note that each word has a different step size
(-1, -6, -3 and 1):
Enter another word/phrase: je
Adding 'je'
...location 6 is in use...
...'je' added at location 5
Press enter...
i hashTable[i]
- ------------
0 'Young'
1
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18
19
20
21
22
Enter another word/phrase: mon
Adding 'mon'
...location 16 is in use...
...location 10 is in use...
...location 4 is in use...
...'mon' added at location 21
Press enter...
i hashTable[i]
- ------------
0 'Young'
1
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18
19
20
21 'mon'
22
Enter another word/phrase: mes
Adding 'mes'
...location 10 is in use...
...location 7 is in use...
...location 4 is in use...
...'mes' added at location 1
Press enter...
i hashTable[i]
- ------------
0 'Young'
1 'mes'
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18
19
20
21 'mon'
22
Enter another word/phrase: ma
Adding 'ma'
...location 3 is in use...
...location 4 is in use...
...location 5 is in use...
...location 6 is in use...
...location 7 is in use...
...'ma' added at location 8
Press enter...
i hashTable[i]
- ------------
0 'Young'
1 'mes'
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8 'ma'
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18
19
20
21 'mon'
22
Enter another word/phrase:
The word intense
also has a step size of -6
(like mon),
but it starts from a different location,
so it follows a different path thru the table
(7, 1, 18 instead of 16, 10, 4, 21).
Enter another word/phrase: intense
Adding 'intense'
...location 7 is in use...
...location 1 is in use...
...'intense' added at location 18
Press enter...
i hashTable[i]
- ------------
0 'Young'
1 'mes'
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8 'ma'
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18 'intense'
19
20
21 'mon'
22
Enter another word/phrase:
You should confirm that each word
visits the same locations
in the same order
each time we try to enter it.
It will notice if the word has already been entered into the table:
Enter another word/phrase: intense
Adding 'intense'
...location 7 is in use...
...location 1 is in use...
...location 18 is in use...
Duplicate entry not added
Press enter...
i hashTable[i]
- ------------
0 'Young'
1 'mes'
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8 'ma'
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18 'intense'
19
20
21 'mon'
22
Enter another word/phrase: ego
Adding 'ego'
...location 16 is in use...
Duplicate entry not added
Press enter...
i hashTable[i]
- ------------
0 'Young'
1 'mes'
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8 'ma'
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18 'intense'
19
20
21 'mon'
22
Enter another word/phrase: mon
Adding 'mon'
...location 16 is in use...
...location 10 is in use...
...location 4 is in use...
...location 21 is in use...
Duplicate entry not added
Press enter...
i hashTable[i]
- ------------
0 'Young'
1 'mes'
2
3 'myself'
4 'I'
5 'je'
6 'mine'
7 'me'
8 'ma'
9
10 'swollen head'
11 'Mark'
12
13
14
15
16 'ego'
17
18 'intense'
19
20
21 'mon'
22
Press enter...
Okay,
we're now ready to add some code.
You're going to complete the method
find.
The method find
is supposed to find out whether the given word
is in the given hash table.
It needs to find where the word is supposed to be,
and check if it's there.
-
If the cell it looks at is empty,
then the word can't be in the table.
find can return false.
-
If the cell it looks at contains the word we're looking for,
it's found,
and
find can return true
-
If the cell contains a different word,
then
find needs to keep looking.
It needs to figure out the next place the word could be
and check there.
Note that find
needs to behave much like the addHashEntry method,
except it shouldn't add the word;
it should simply return true if the word is there
and false otherwise.
Have find print reports of where it's looking.
After you've re-entered the words
(and duplicates) above,
your output should look like this:
Now we will search for some words.
Enter a word/phrase to search for: Young
Looking for 'Young'
...checking location 0
It's there.
Enter a word/phrase to search for: mes
Looking for 'mes'
...checking location 10
...checking location 7
...checking location 4
...checking location 1
It's there.
Enter a word/phrase to search for: myself
Looking for 'myself'
...checking location 3
It's there.
Enter a word/phrase to search for: you
Looking for 'you'
...location 9 is empty
It's not there.
Enter a word/phrase to search for: your
Looking for 'your'
...location 2 is empty
It's not there.
Enter a word/phrase to search for: yours
Looking for 'yours'
...checking location 16
...checking location 0
...checking location 7
...location 14 is empty
It's not there.
Enter a word/phrase to search for: mon
Looking for 'mon'
...checking location 16
...checking location 10
...checking location 4
...checking location 21
It's there.
Enter a word/phrase to search for:
Notice how yours and mon
were both sent initially to location 16,
but then they visited different later locations
(0, 7, 14 versus 10, 4, 21).