Question

Suppose that s = { 4 , 9 , 17 , 42 , 63 , 57 , 14 , 12 , 99 } and Suppose that hash table ( HT ) , is of size 10, indexed from 0 , 1 , 2, . . 9 . Show how these values in the order given , are inserted in HT using the hashing function h(s) = s % n. Use linear probing to resolve collision. Is this a good hash function.

Answer 1

Inserting 4
4 is inserted at position 4

Inserting 9
9 is inserted at position 9

Inserting 17
17 is inserted at position 7

Inserting 42
42 is inserted at position 2

Inserting 63
63 is inserted at position 3

Inserting 57
There is already an item in 7
So, checking at index 8
57 is inserted at position 8

Inserting 14
There is already an item in 4
So, checking at index 5
14 is inserted at position 5

Inserting 12
There is already an item in 2
So, checking at index 3
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
12 is inserted at position 6

Inserting 99
There is already an item in 9
So, checking at index 0
99 is inserted at position 0

HashTable
-----------
0   -      99
1   -
2   -      42
3   -      63
4   -      4
5   -      14
6   -      12
7   -      17
8   -      57
9   -      9

Yes, this is a good hash function.