Chapter 8: Hash Tables

Question 1

There is a hash table with 40 slots and there are 200 elements stored in the table. What will be the load factor of the hash table?

Solution

The load factor of the hash table = (no. of elements) / (no. of table slots) = 200/40 = 5.

Question 2

What is the worst-case search time of hashing using a separate chaining algorithm?

Solution

The worst-case time complexity for searching in a separate chaining algorithm using linked lists is O(n), because in the worst case, all the items will be added to index 1 in a linked list, searching an item will work similarly to a linked list.

Question 3

Assume a uniform distribution of keys in the hash table. What will be the time complexities for the search/insert/delete operations?

Solution

The index of the hash table is computed from the key in O(1) time when the keys are uniformly distributed in the hash table. The creation of the table will take O(n) time, and other...