Hash Tables Linear Probing and Double Hashing

1. Feb 27, 2012

lina29

1. The problem statement, all variables and given/known data
Consider a hash table T with 11 entries and the hash function h(x) = x mod 11. Show the result of hashing the keys 10,16,11,43,33,13,14,12,3, and 22, assuming collisions are handled by
(a) open addressing with linear probing
(b) double hashing using a secondary hash function h′(x) = 5−(x mod 5)

2. Relevant equations

3. The attempt at a solution

I believe I have the correct answer, I just want to double-check since I'm having difficulties.

Using a table I have:
Key ---- h(x) ---- h'(x) ---- probes LP ---- probes DH
10 ---- 10 ---- ---- 10 ---- 10
16 ---- 05 ---- ---- 5 ---- 5
11 ---- 00 ---- ---- 0 ---- 0
43 ---- 10 ---- 2 ---- 10, 0, 1 ---- 10,2
33 ---- 00 ---- 2 ---- 0, 1, 2 ---- 0, 2, 3
13 ---- 02 ---- 2 ---- 2,3 ---- 2,2,3,4
14 ---- 03 ---- 1 ---- 3,4 ---- 3,1
12 ---- 01 ---- 3 ---- 1,2,3,4,5,6 ---- 1,3,4,5,6
03 ---- 03 ---- 2 ---- 3,4,5,6,7 ---- 3,2,3,4,5,6,7
22 ---- 00 ---- 3 ---- 0,1,2,3,4,5,6,7,8 ---- 0,3,4,5,6,7,8

2. Feb 28, 2012

rcgldr

The linear probe interval isn't specified. Are you supposed to assume it's 1? The contents of the hash table is not specified, so how are you supposed to know when collisions have occurred, or are you just supposed to list a set of indexes for the collision sequence for each key, or are you supposed to assume that the hash table is initially empty and the list of keys you're given are going to be stored in the hash table in the listed key order?

3. Feb 28, 2012

lina29

We're supposed to assume the interval is 1. I'm not sure I understand what you mean but you know a collision occurs when both keys have the same h(x) like keys 10 and 43 both have h(x) as 10

4. Feb 28, 2012

rcgldr

I understand that, but are you just supposed to list the order in probes would take place if the hash table was completely filled (no empty slots), or are you supposed to list the probes that would take place if the hash table was initially empty and you stored that list of 10 keys into the hash table, leaving one empty slot when done?

Last edited: Feb 28, 2012
5. Feb 28, 2012

lina29

We're supposed to list the probes by the place is should initially be at. if that spot is filled then we advance to the next spot until we find an empty spot

6. Feb 28, 2012

rcgldr

Looks like it's the case where you're adding those 10 keys in order to an initially empty table, in which case your answer appears to be correct. Note, you can put [ code ] and [ /code ] (without the spaces) around your text to preserve it's format.

7. Feb 28, 2012

thank you!