Advantage of Chained Hash Table over Open Addressing Scheme

Chained hash table and open addressing scheme are two common techniques used for implementing hash tables. Chained hash table, also known as external hashing, is a technique where each slot in the hash table is a linked list, and collision resolution is done by appending the collided elements to the linked list. On the other hand, open addressing scheme is a technique where the collided elements are placed in the next available slot, following a certain probing sequence.

The advantage of chained hash table over open addressing scheme is:

Deletion is easier: In chained hash table, deletion of an element is relatively easy. Since each slot in the hash table is a linked list, removing an element from the list only requires updating the links of the neighboring elements. On the other hand, in open addressing scheme, deleting an element requires rehashing the entire table to maintain the probing sequence, which can be time-consuming.

Other considerations:

Worst case complexity of search operations: In open addressing scheme, the worst case complexity of search operations can be O(n), where n is the size of the hash table. This can happen when all the slots in the probing sequence are occupied, and the element being searched for is not in the table. In chained hash table, the worst case complexity is O(k), where k is the size of the linked list in the slot being searched. Therefore, in terms of worst case complexity, open addressing scheme may have an advantage over chained hash table.

Space used: In terms of space used, open addressing scheme may have an advantage over chained hash table. This is because chained hash table requires additional space to store the links between the elements in the linked list. On the other hand, in open addressing scheme, the occupied slots are used directly to store the elements, without any additional space required for links. However, this advantage may be offset by the need for more slots in open addressing scheme to maintain the probing sequence.

In summary, while chained hash table may have an advantage in terms of easier deletion, the choice between chained hash table and open addressing scheme depends on the specific application requirements and constraints, such as the expected load factor, the size of the table, and the frequency of insertions, deletions, and searches.