HASH CHAINING Professor Marley hypothesizes that he can obta

HASH CHAINING

Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

Solution

Hash Chaining:

Affecting of time will be taken as following:

Both Successful and Unsuccessful Searches take time O(l) where l = length of the list. As long as load factor is constant. O(1) average time complexity will not effect it.

Insertions: The insertion operation earlier took O(1) because ecah time a new key was added to the head of the list. But now it would take O(l) where l = length of the list.+

Deletions: As long as list is doubly linked list, it should still take O(1) time to delete an element from the table. But if it is singly linked list then it would take O(l) whether or not the list is sorted.