in DS
10,786 views
36 votes
36 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

in DS
10.8k views

3 Comments

chaning  having two draw back  1. pointer overhead

                                                   2. searching time is high bcz in case every one goes on same slot

open adressing having drawback of deletion is not easy bcz in case of empty slot arises inbetween
12
12

Open Addressing vs. Separate Chaining
Advantages of Chaining:
1) Chaining is Simpler to implement.
2) In chaining, Hash table never fills up, we can always add more elements to chain. In open addressing, table may become full.
3) Chaining is Less sensitive to the hash function or load factors.
4) Chaining is mostly used when it is unknown how many and how frequently keys may be inserted or deleted.
5) Open addressing requires extra care for to avoid clustering and load factor.

Advantages of Open Addressing
1) Cache performance of chaining is not good as keys are stored using linked list. Open addressing provides better cache performance as everything is stored in same table.
2) Wastage of Space (Some Parts of hash table in chaining are never used). In Open addressing, a slot can be used even if an input doesn’t map to it.
3) Chaining uses extra space for links.

Source: http://www.geeksforgeeks.org/hashing-set-3-open-addressing/

33
33
Here the easy or difficult is defined based on the number of operation we have to perform in order to delete in both implementations.

I  think the physical aspects of actual deletion like memory cycles to retrieve the block, delete it, write back etc are not at all considered.

Even if the worst case for deletion is O(n) for both schemes, the delete operation in chaining is much better that open addressing most of the time.
0
0

4 Answers

32 votes
32 votes
Best answer
  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

4 Comments

Can anyone please reply to @VS's previous comment. I think deletion is more costly in Chaining than in Open addressing.(And as per my understanding, "costly" also means not easy to implement)

VS's comment:

I am not getting why deletion is easier in chaining.

There can be 2 cases here ::

Case1: When a pointer to the node to be deleted is not given

In this case first search for the node which can take O(n) time is worst case.And then we can delete the node.

Case 2: When a pointer to the node to be deleted is given

Now in this case we cannot directly delete the node.Because chaining is much like Singly Linked list ,even we directly have the address of the node to be deleted.In order to keep the linked list connected we need a ptr to the node before the node to be deleted.To obtain that we need to traverse the linked list. Time Taken :: O(n)

0
0

 Cost here implies number of operations(Number of comparisons), Coming to why deletion is less costly in chaining as compared to open Addressing , Let us consider we inserted 'n' keys to hash table using both the cases(ie chaining and open Addressing), Now let's consider we have deleted n-1 keys, So only one key is left,

For chaining it would be staright forward since by key we will get the location of key and in O(1) we can delete it, But for open addressing there me a possibility that the key which we want to delete may be inserted after n probes or not at all present in table, Which will lead to O(n) comparison even for 1 key deletion.

 

5
5

Adding to @sags.sharma comment, We may have to do rehashing of the table (if we have enough special markers in the table) to bring time complexity of operations on hash table down to constant. Thus making deletion in open addressing harder than in chaining.

0
0
9 votes
9 votes

3 Comments

Can anyone explain why it's not option a? I feel search time is also reduced with chained hash.
2
2
In  the case of chained hash table or chaining the worst case complexity of a successful search operation is O(1+alpha) and in case of open addressing let us take probing where succesful search time is O(1/alpha*ln 1/1-alpha) .Now let us take alpha= 7/8, in each  case calculating we see search time of chained hash table is more than probing so option a false
–1
–1
edited by
here they are taking simple chaining not hashed chaining so .
0
0
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 comment

edited by

 you don't need to get the previous pointer to delete a node in linked list as it's doubly linked list. 

 

anyone plz explain this line. How can we delete a node in a doubly linked list without getting the previous pointer? I think we need the previous pointer, you can say getting the previous pointer in a doubly-linked list is a constant time operation.

 

0
0
0 votes
0 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

1 comment

If you're at the element, that should be no problem in Open addressing as well ! You'll just need to put a marker. So whats the advantage ? I don't feel this is the correct reason, implicitly considering we are at the element or not doesn't matter. Acc to me, correct reason shall be that the WC goes to O(#keys) in chaining, and O(#buckets) in Open Addressing. But as #keys<#buckets, thus we say that deletion becomes easier as searching time reduces a little bit(WC). Also, I feel if all this was to be considered, they should've not given an option "none of the above" to avoid any confusion.
0
0
Answer:

Related questions