1. Linear Probing vs Double Hashing

|Characteristics |Linear Probing|Double Hashing| | :- | :- | :- | |Probing sequence|

hash(key) + i

|hash(key) + i * hash2(key)| |Primary clustering|Susceptible to primary clustering, consecutive clusters of occupied slots may form|Reduces primary clustering, produces a more even distribution| |Efficiency|Good cache performance, simple implementation |Better performance, fewer collisions, may require more computation| |Load Factor Sensitivity|Poor performance as load factor increases, longer probe sequences|Handles higher load factors more efficiently| |Deletion support|Supports deletion without disrupting probing sequence|Deletion may break the probing sequence, requires special techniques|

2. Open Addressing vs Separate Chaining

|Characteristics |Open Addressing|Separate Chaining| | :- | :- | :- | |Collision Resolution|

Colliding elements are stored directly in the hash table itself

|Colliding elements are stored in separate data structures (e.g., linked lists)| |Memory Efficiency|More memory-efficient as it does not require additional data structures for collision resolution|Requires additional memory for storing the separate data structures| |Load Factor Sensitivity|Sensitive to high load factors, as it can lead to increased collisions and longer probe sequences|Less sensitive to load factors, as separate data structures can handle collisions efficiently| |Performance|Generally faster for small-sized hash tables or low load factors|Can provide better performance for large-sized hash tables or high load factors| |Insertion and Deletion|Insertion and deletion may be more complex, as elements need to be inserted into specific slots and deleted slots need to be marked as "deleted"|Insertion and deletion are relatively simpler, as elements can be added to or removed from the separate data structures| |Memory Overhead|Requires less memory overhead, as it avoids the need for separate data structures|Requires additional memory overhead for storing the separate data structures| |Primary Clustering|Prone to primary clustering, which can impact performance|Avoids primary clustering by distributing elements across separate data structures| |Cache Performance|Generally, has better cache performance, as elements are stored contiguously in memory|May have lower cache performance due to scattered memory locations of separate data structures|

3. Open Addressing Methods

|Characteristics|Linear Probing|Quadratic Probing|Double Hashing| | :- | :- | :- | :- | |Probing Sequence|hash(key) + i|hash(key) + c1 * i + c2 * i²|hash(key) + i * hash2(key)| |Primary Clustering|Susceptible to primary clustering|Attempts to reduce primary clustering|Less prone to primary clustering| |Efficiency|Good cache performance, simple implementation|May have better performance than linear probing|Can have better performance in some cases| |Load Factor Sensitivity|Performance degrades with high load factors|Performance degradation is slower with high load factors|Can handle higher load factors efficiently| |Deletion Support|Supports deletion without disrupting probing sequence|Supports deletion without disrupting probing sequence|Deletion may require special techniques| |Probing Sequence Collision Patterns|Linear sequence, potential for clustering|Quadratic sequence, mitigates primary clustering|Varied sequence based on secondary hash function|