Hash Tables Linear Probing and Double Hashing

[lina29]

Homework Statement

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)

Homework Equations

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

 

[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?

 

[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

 

[rcgldr]

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

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?

 

[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

 

[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.

 

[lina29]

thank you!