Problem
The following sequence of keys is to be inserted into an initially empty hash table of size 8 that employs open addressing:
the, my, an, by, do, we, if, to, go
The hash function assigns to each key the number of characters in the key. For example, h("the") is 3, because "the" has 3 characters.
Assume that linear probing is used to insert the keys. Determine which key causes overflow, and show the table at that point by adding the keys at the appropriate positions in the table that we have provided in section 7-1 of ps9_partI.
Now assume that quadratic probing is used. Determine which key causes overflow, and show the table at that point.
Finally, assume that double hashing is used, and that the second hash function h2 is based on the part of speech of the key, as follows:
1) h2(k) = 1 if k is a noun or pronoun (e.g., "we", "my")
2) h2(k) = 2 if k is a verb (e.g., "do", "go")
3) h2(k) = 3 if k is an article (e.g., "the", "an")
4) h2(k) = 4 if k is any other part of speech (the rest of the words above).
Now consider the fourth table provided for problem 7 in ps9_partI.
Assume that this table is using double hashing with the hash functions described above. The table includes a number of existing keys, and positions 2 and 7 are shaded to indicate that they are removed positions - i.e., ones that used to hold an item that has since been removed.
If we now insert an item whose key is "see" (which is a verb), what is the probe sequence - i.e., the sequence of positions examined during probing - for that insertion?
Show what the table will look like after "see" is inserted.