Methods of Collision Detection
Here is your data: {3, 7, 11, 22, 18, 30, 72, 41, 14, 15, 77}
hash(x) = x mod 11
1. If TableSize = 11, where do your collisions occur?
2. One method of collision resolution is called separate chaining. In this case, each cell in your hash array points to "some data structure" which contains everything that hashed to that value in the array.
a. Draw a diagram showing this approach using a linked list.
b. Draw a diagram showing this approach using a BST.
c. Write pseudocode for implementing: find(), insert(), and remove()
d. What is the running time for find(), insert(), and remove()?
e. Name two reasons to use this approach.
f. Name two reasons not to use this approach.
3. Another method of collision resolution is called open addressing.
a. One type of open addressing is called linear probing. In this case, if the cell you need is full, you go to the next available cell. Draw a diagram showing this approach.
b. Write pseudocode for implementing: find(), insert(), and remove()
c. What are the running times for find(), insert(), and remove()?
d. Another type of open addressing is called quadratic probing. In this case, if the cell you need is full, you then check 1 cell away, then check 4 cells away (from the original cell), then 9 cells away, … Draw a diagram showing this approach.
e. Under what conditions in quadratic probing would insert() fail?
f. Name two reasons to use open addressing.
g. Name two reasons not to use open addressing.