Hash Tables Help Center

Learn more

Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.

To specify an array or sequence of values in an answer, separate the values in
the sequence by whitespace. For example, if the question asks for the first
ten powers of two (starting at 1), then the following answer is acceptable:

     1 2 4 8 16 32 64 128 256 512

If you wish to discuss a particular question and answer in the forums, please
post the entire question and answer, including the seed (which can be used by
the course staff to uniquely identify the question) and the explanation (which
contains the correct answer).

Question 1

(seed = 342641)
Insert the following sequence of 12 keys into a separate-chaining hash table with 3 chains:

key  hash
---  ----
 J    2
 X    1
 W    0
 F    1
 L    1
 N    0
 M    2
 I    1
 B    0
 R    1
 T    0
 Q    0


Consider a search miss for the key U, whose hash value is 1.
What is the sequence of keys that get compared with U?

Question 2

(seed = 989985)
Give the array that results after inserting the following sequence of 10 keys
into an initially empty linear-probing hash table.

key  hash
---  ----
 K    5
 G    1
 P    0
 J    4
 S    3
 B    6
 N    8
 Z    0
 E    9
 Y    9

Assume that the size of the hash table is 10 and that it neither grows nor shrink.

Question 3

(seed = 516315)
Suppose that the following keys are inserted into an initially empty linear-probing hash table
but not necessarily in the order given:

key  hash
---  ----
 A    2
 J    4
 M    0
 Q    4
 U    1
 V    2
 W    3

Assuming that the size of the hash table is 7 and that it does not grow or shrink,
which one or more of the following could be the contents of the resulting array?
    
You cannot submit your work until you agree to the Honor Code. Thanks!