Clicker Questions - 08-Collision-Res
Name H1 H2
--------------------- ------ ------
Aidan Nepal 9bc6cc 42757b
Alexander Aeronautic 4345ae 93249d
Austin Prissy 20b849 8c1ef7
Charlie Maiden 0d6fc1 e5855d
Claire Tva fe30bf 8124af
Gavin Parallelepiped 0e9b65 db8914
Hunter Fabric b112a2 78d98d
Isabelle Stack 4c30e6 f7193f
Joshua Polonium 831e15 eeba38
Madison Willoughby 1874dc 911d61
Max Mere fc7e5b 8d1814
Maya Paddy 107b1e 5e84ff
Natalie Sober c624de b46fa3
Noah Porous ae3e75 2dbc99
Riley Predecessor f001c1 385e34
Savannah Tradesman a3d7ee ab7176
Sophia Keys 69147a 493120
Above, I have a table of 17 names, and what each name hashes to with two different hash functions, H1 and H2. The hash values are given in hexadecimal.
Below, I have a 16-element hash table that has been filled in with some of these names.
Please answer the questions below. Do not answer the questions as if one affects the other. Answer them all with respect to the tables shown here. For example, you should not answer part C as if Austin Prissy were inserted into the table. Instead, you simply answer with respect to the table above.
In all of the questions, assume that hash function H1 is used to insert into the table, and if double-hashing is used, then hash function H2 is used as the second hash function.
0. --------------------
1. Charlie Maiden
2. Hunter Fabric
3. --------------------
4. --------------------
5. Gavin Parallelepiped
6. Isabella Stack
7. --------------------
8. --------------------
9. --------------------
10. Sophia Keys
11. Max Mere
12. Aiden Nepal
13. Madison Willoughby
14. Savannah Tradesman
15. Claire Tva
Question 1: What is the load factor of the table (you can give a fraction here)?
Answer
There are 10/16 entries full, so the load factor is 10/16.This came from the 2019 midterm for COSC140.
Question 2: Into which index will Austin Prissy go into the table, using linear probing?
Answer
Austin Prissy's index is 9, which is empty, so the answer is 9.This came from the 2019 midterm for COSC140.
Question 3: Into which index will Joshua Polonium go into the table, using quadratic probing?
Answer
Joshua Polonium's index is 5. Five is taken, so we check 5+12 = 6. That is taken, so we check 5+22 = 9. That is empty, so the answer is 9.This came from the 2019 midterm for COSC140.
Question 4: Into which index will Maya Paddy go into the table, using double hashing?
Answer
Maya Paddy's index is 0xd = 13. 13 is taken, so we'll need to use the second hash value, which is 0xf = 15. This means that we'll be looking at successively smaller indices -- 12, 11, 10, and finally 9.This came from the 2019 midterm for COSC140.
Question 5: Into which index will Noah Porous go into the table, using linear probing?
Answer
Noah Porous' index is 5. Five is taken, so we'll look at successively larger indices -- 6, which is taken, and then 7, which is empty. The answer is 7.This came from the 2019 midterm for COSC140.
Question 6: Into which index will Riley Predecessor go into the table, using double hashing?
Answer
Riley Predecessor's index is 1. 1 is taken, so we'll need to use the second hash value, which is 4. 5 is taken, but 9 is empty, so the answer is nine.This came from the 2019 midterm for COSC140.