Java Reference
In-Depth Information
addressing with double hashing. a word can appear on more than one line, but each word
must be inserted only once in the table. if a word appears on more than one line, then all
words on those lines are synonyms. this part of the data is terminated by a line containing
the word
EndOfSynonyms
.
the data structure must be organized such that, given any word, all synonyms for that word
can be quickly found.
the next part of the data consists of several commands, one per line. a valid command is
designated by
P
,
A
,
D
, or
E
.
P
word
prints, in alphabetical order, all synonyms of
word
.
A
word1 word2
adds
word1
to the list of synonyms for
word2
.
D
word
deletes
word
from the thesaurus.
E
, on a line by itself, indicates the end of the data.
7.
Write a program to compare quadratic probing, linear probing with double hashing, and
chaining. Data consists of an english passage, and you are required to store all the distinct
words in the hash tables. For each word and each method, record the number of probes
required to insert the word in the hash table.
Cater for 100 words. For quadratic probing and double hashing, use a table size of 103. For
chaining, use two table sizes—23 and 53. For each of the four methods, use the same basic
hash function.
print an alphabetical listing of the words and the number of probes for each of the four
methods. Organize your output so that the performance of the methods can be easily
compared.