Collision Resolution Techniques-
In Hashing, collision resolution techniques are classified as-
In this article, we will compare separate chaining and open addressing.
Separate Chaining Vs Open Addressing-
Separate Chaining |
Open Addressing |
| Keys are stored inside the hash table as well as outside the hash table. | All the keys are stored only inside the hash table.
No key is present outside the hash table. |
| The number of keys to be stored in the hash table can even exceed the size of the hash table. | The number of keys to be stored in the hash table can never exceed the size of the hash table. |
| Deletion is easier. | Deletion is difficult. |
| Extra space is required for the pointers to store the keys outside the hash table. | No extra space is required. |
|
Cache performance is poor. This is because of linked lists which store the keys outside the hash table. |
Cache performance is better. This is because here no linked lists are used. |
|
Some buckets of the hash table are never used which leads to wastage of space. |
Buckets may be used even if no key maps to those particular buckets. |
Which is the Preferred Technique?
The performance of both the techniques depend on the kind of operations that are required to be performed on the keys stored in the hash table-
Separate Chaining-
Separate Chaining is advantageous when it is required to perform all the following operations on the keys stored in the hash table-
- Insertion Operation
- Deletion Operation
- Searching Operation
NOTE-
- Deletion is easier in separate chaining.
- This is because deleting a key from the hash table does not affect the other keys stored in the hash table.
Open Addressing-
Open addressing is advantageous when it is required to perform only the following operations on the keys stored in the hash table-
- Insertion Operation
- Searching Operation
NOTE-
- Deletion is difficult in open addressing.
- This is because deleting a key from the hash table requires some extra efforts.
- After deleting a key, certain keys have to be rearranged.
To gain better understanding about Separate Chaining Vs Open Addressing,
Get more notes and other study material of Data Structures.
Watch video lectures by visiting our YouTube channel LearnVidFun.