13,623 views
39 votes
39 votes

An advantage of chained hash table (external hashing) over the open addressing scheme is

  1. Worst case complexity of search operations is less

  2. Space used is less

  3. Deletion is easier

  4. None of the above

6 Answers

Best answer
35 votes
35 votes
  1. False :-  search operation can go worst in chaining if all elements are stored under a single bucket.
  2. False . Pointer space is overhead in chaining.
  3. is true BCZ in Open Adressing sometimes though element is present we cant delete it if Empty Bucket comes in between while searching for that element ;Such Limitation is not there in Chaining.
edited by
9 votes
9 votes
8 votes
8 votes
C. The performance of delete operation in doubly linked list chaining is O(1). You simply have to delete the element x in the list T[h(x.key)] and you don't need to get the previous pointer to delete a node in linked list as it's doubly linked list.
Whereas, in open chaining, you need to probe for the element to delete and mark it with 'X' if found. Essentially it will depend on the number of consecutive locations filled which will make it O(n) I believe, where n < size of the hash table.

B. is wrong because extra space for links is required.

A. I feel that Chaining is faster than Open addressing but essentially the worst case performance in both cases boils down to O(n), as you have to traverse the linked list in chaining and probe for finding the element in open addressing. So, in the first case of chaining : all elements are in a single bucket => O(n)
And in open addressing: all places except last are filled which makes load factor < 1 (a requirement for open addressing) and you have to probe each and every location to decide whether the element is there or not.
Correct me if I am wrong, but I feel that worst cases of both are O(n) and hence, A is wrong.
1 votes
1 votes

In chained hash table deletion is easy and can be implemented in O(1) time complexity using double linked list to store the key in case of collision.

now one might wonder to search the element itself took O(n) if the length of the chain is n but the problem is actually you are now at the element and you want to delete the element and in case of singly linked list it cant be possible in O(1) but using doubly linked list we can easily done it O(1).

so correct option ic C.

one may check out the below link for some reference.

https://stackoverflow.com/questions/8105889/why-deletion-of-elements-of-hash-table-using-doubly-linked-list-is-o1

Answer:

Related questions

24 votes
24 votes
4 answers
1
29 votes
29 votes
3 answers
2
Kathleen asked Oct 9, 2014
12,123 views
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?$1$$3$$7$$8$
54 votes
54 votes
7 answers
3
Kathleen asked Oct 9, 2014
22,708 views
A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain.$\begin{array}{llllll} \text{(a)} ...
21 votes
21 votes
3 answers
4
Kathleen asked Oct 9, 2014
4,304 views
Which of the following sequences denotes the post order traversal sequence of the below tree?$f\; e\; g\; c\; d\; b\; a$$g\; c\; b\; d\; a\; f\; e$$g\; c\; d\; b\; f\; e\...