Hash tables

Exercises 3.1 and 3.2

Exercise 3.1

Consider a hash table with separate chaining, M = 10 positions with integer keys, and hash function h(x)=x \pmod M.

Starting from an empty table, show the resulting table after inserting the keys:

3441
3412
498
1983
4893
3874
3722
3313
4830
2001
3202
365
128181
7812
1299
999
18267

Show the resulting table after applying a rehash of the previous table into M=20 positions.

Hint

The hash table when M=10 and the first element has been inserted has the following form.

h(x)
0
1	3441
2
3
4
5
6
7
8
9

When M=20 (and the first element has been inserted) it has the following form

h(x)
0
1	3441
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Exercise 3.2

Now we want to build the hash table with separate chaining for the keys

30
20
56
75
31
19

with M=11 positions and hash function h(x)=x \pmod M.

What is the maximum number of comparisons in a successful search in this last table?

What is the expected number of comparisons in a successful search in this last table?

Hint

The hash table when M=11 and the first element has been inserted has the following form.

h(x)
0
1
3
2
4
5
6
7
8	30
9
10