Question

Assume data is to be stored in a hash table using the following keys: 62,77.26, 42, 52,76 Assume the hash table size is 7, the hash function used is the modulo function i.e. h/key) = key % table_size, and collisions are handled using linear probing. What's the content of the table after all keys are mapped to the hash table? (List keys starting from table index 0 and on Separate numbers by a comma and a single space, and indicate an empty slot with a dash. If a data item can't be stored, indicate so).

Answer 1

• The given table size is 7, so the hash funtion will be h(key) = key%7
• The inital hash table will be as follows:

0: _

1: _

2: _

3: _

4:_

5: _

6: _

• Now , insert 62 into table. 62%7 = 6

0: _

1: _

2: _

3: _

4:_

5: _

6: 62

• insert 77 into table, 77%7 = 0

0: 77

1: _

2: _

3: _

4:_

5: _

6: 62

• Insert 26 into table, 26%7 = 3

0: 77

1: _

2: _

3:

4:_

5: 26

6: 62

• Insert 42 into table, 42%7 = 0. It collides with 77, so store in next index 1

0: 77

1: 42

2: _

3:

4:_

5: 26

6: 62

• insert 52 into table. 52%7 = 3

0: 77

1: 42

2: _

3: 52

4:_

5: 26

6: 62

• insert 76 into table, 76%7 = 6. It collides with 62, so linearly probe until a free index is obtained. 0 is filled and 1 is filled too, so add the element ot index 2.

0: 77

1: 42

2: 76

3: 52

4:_

5: 26

6: 62

Answer: 77, 42, 76, 52, _, 26, 62