Clicker Questions - 07-Collision-Res
For these questions, each answer is four numbers. Simply enter them on Turning point separated by spaces or commas.
I’ll also put the mathematical definition of open addressing here. From the lecture notes:
With open addressing, you test the keys in order, h_0, h_1, h_2, ..., until you find what you're looking for or you find an empty space in the hash table. h_i is defined as follows:
h~i~ = H(key) + F(i, key), modulo the table size.
H() is the hash function, and F() is a function that defines how to resolve collisions. It is usually convenient to make sure that F(0, key) equals zero, and it is necessary for F(i, key) not to equal zero when i doesn't equal zero.
- With linear probing, F(i, key) = i.
- With quadratic probing, F(i, key) = i^2^.
- With double hashing, F(i, key) = H2(key)*i.
Question 1: Suppose you are looking up a value in a hash table that has 100 elements, and the hash table is pretty full. The hash function for the value returns 847298. You are using linear probing – what are the first four indices that you will test when you look up the value?
Answer
You start at 98, and look at successively higher indices mod 100: 98, 99, 0, 1.This one came from the spring 2014 midterm.
Grading
- Question 1: To receive full credit on the 2nd, 3rd and 4th probes, they had to equal the previous probe plus one, mod 100.
- Question 1: If you said 1 instead of 0, you got half credit.
- Question 1: If you forgot the mod 100 when you added one, you got half credit.
Question 2: Now, suppose you are using quadratic probing. What are the first four indices that you will test?
Answer
Now, you start at 98, and add 02, 12, 22 and 32: 98, 99, 2, 7.This one came from the spring 2014 midterm.
Grading
- Question 2: To get full credit, your answer for the first probe had to equal the answer for the first probe in Question 1.
- Question 2: The other probes needed to be relative to the first probe.
- Question 2: If you forgot the mod 100, you got half credit.
- Question 2: On the third and fourth probes, if you were off by one, you got half credit.
Question 3: Now, suppose you are using double-hashing, and the second hash function returns 92821. What are the first four indices that you will test?
Answer
Now, you start at 98, and add 0*21, 1*21, 2*21 and 3*21: 98, 19, 40, 61.This one came from the spring 2014 midterm.
Grading
- Question 3: To get full credit, your answer for the first probe had to equal the answer for the first probe in Question 1.
- Question 3: The other probes needed to be relative to the first probe.
- Question 3: If you forgot the mod 100, you got half credit.
- Question 3: On the second, third and fourth probes, if you were off by one, you got half credit.