Advantages | Disadvantages | |
---|---|---|
Open Addressing | Memory Efficient – stores elements in empty array spaces | Creates Clusters with Linear and Quadratic Probing |
Separate Chaining | Very Easy to implement | Memory Inefficient – requires a secondary data structure to store collisions Long Chains will produce Linear search times |
- What is the advantage of separate chaining?
- What is the advantage of separate chaining compared with open addressing?
- What are the disadvantages of linear probing?
What is the advantage of separate chaining?
The biggest advantage of separate chaining is its collision avoidance capabilities. This means that many data items may be hashed with the same keys creating long link chains. But this adversely affects the turnaround time for searching operations.
What is the advantage of separate chaining compared with open addressing?
Chaining is easy to implement effectively. Easily delete a value from the table. It uses less memory if the record is large compared to the open addressing.
What are the disadvantages of linear probing?
The problem with linear probing is that keys tend to cluster. It suffers from primary clustering: Any key that hashes to any position in a cluster (not just collisions), must probe beyond the cluster and adds to the cluster size.