concept · INFO-CS-ADS-074Quadratic Probing and Double Hashing
Quadratic probing and double hashing are open-addressing techniques that generate alternative table positions after a collision. Both can reduce clustering compared with basic linear probing, but they use different methods to calculate probe sequences.
Explanation
Overview
Quadratic probing and double hashing are collision-resolution strategies that search for alternative positions within a hash-table array using mathematical offsets rather than checking only consecutive positions.
Key concepts
name: Core idea; description: The central focus of quadratic probing and double hashing is the capability described here: Quadratic probing and double hashing are open-addressing techniques that generate alternative table positions after a collision. Both can reduce clustering compared with basic linear probing, but they use different methods to calculate probe sequences.; name: Problem context; description: Quadratic Probing and Double Hashing is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using quadratic probing and double hashing, check its assumptions, input requirements, expected output, and resource constraints.
Example
scenario: A software feature needs to use quadratic probing and double hashing.; task: Design a small, testable solution that demonstrates quadratic probing and double hashing while satisfying the requirements described in this entry.; approach: Identify the input and expected output, apply the central idea of quadratic probing and double hashing, and trace the result with a small representative dataset.; learningPoint: This quadratic probing and double hashing example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.
Limitations
Performance depends on hash quality, input distribution, collision behavior, and the chosen load factor.; An implementation of quadratic probing and double hashing can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For quadratic probing and double hashing, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.
Example or application
Scenario
A software feature needs to use quadratic probing and double hashing.
Task
Design a small, testable solution that demonstrates quadratic probing and double hashing while satisfying the requirements described in this entry.
Approach
Identify the input and expected output, apply the central idea of quadratic probing and double hashing, and trace the result with a small representative dataset.
Learning Point
This quadratic probing and double hashing example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.
Definition
Quadratic probing and double hashing are collision-resolution strategies that search for alternative positions within a hash-table array using mathematical offsets rather than checking only consecutive positions.
Quadratic Probing
Definition
Quadratic probing generates probe positions using quadratic functions of the probe number. The offsets grow according to a quadratic pattern.
Formula
index_i = (h(k) + c1 × i + c2 × i²) mod m
Variables
H(k)
The initial hash index of key k.
I
The probe number, beginning with zero.
C1
A chosen linear coefficient.
C2
A chosen quadratic coefficient.
M
The hash-table capacity.
Example
For an illustrative sequence with h(k) = 3, c1 = 0, c2 = 1, and m = 11, the probe positions begin at 3, 4, 7, and 1 as the probe number increases from 0.
Primary Benefit
Quadratic probing can reduce primary clustering because entries do not always occupy consecutive positions after collisions.
Limitation
Keys with the same initial hash value can follow the same probe sequence, creating secondary clustering. Depending on the table capacity and coefficients, the sequence may not visit every table position.
Double Hashing
Definition
Double hashing uses a second hash function to determine the distance between successive probe positions.
Formula
index_i = (h1(k) + i × h2(k)) mod m
Variables
H1(k)
The first hash function determines the initial position.
H2(k)
The second hash function determines the probe step size.
M
The hash-table capacity.
Example
For a table capacity of 11, suppose h1(k) = 3 and h2(k) = 4. The probe sequence begins at 3, then 7, 0, 4, and continues by adding 4 modulo 11.
Step Requirement
The second hash function should produce a nonzero step size that is relatively prime to the table capacity. This allows the probe sequence to visit every position in the table.
Primary Benefit
Different keys can have different probe step sizes, which helps reduce clustering and spreads probe sequences more effectively.
Limitation
It requires two hash-function calculations and careful selection of the second function and table capacity.
Comparison
| Feature | Quadratic Probing | Double Hashing |
|---|
Probe calculation | Uses a quadratic offset based on the probe number. | Uses a second hash function to determine the step size. |
Primary clustering | Reduces primary clustering. | Generally reduces primary clustering. |
Secondary clustering | Can occur when keys share the same initial hash index. | Reduced because different keys can have different step sizes. |
Implementation | Requires suitable coefficients and table-capacity choices. | Requires two appropriate hash functions. |
Probe coverage | Depends on the table size and selected coefficients. | Can visit every slot when the step size is relatively prime to the capacity. |
Deletion
Both techniques generally require tombstones or another deletion method that preserves the correctness of the probe sequence.
Average Complexity
Lookup, insertion, and deletion can be O(1) on average when the load factor is controlled and the probe sequence distributes searches effectively.
Worst Case Complexity
An operation can require O(n) time when it examines a large number of table positions.
Load Factor Effect
Both methods become less efficient as the table approaches full occupancy. Maintaining a suitable load factor is important for keeping probe sequences short.
Selection Considerations
Expected distribution of input keys.
Table capacity and its mathematical properties.
Probe-sequence coverage.
Cost of calculating hash functions.
Expected load factor.
Complexity of deletion and tombstone management.
Important Distinction
Quadratic probing changes the offset using a quadratic expression. Double hashing calculates the offset using a second hash function. They are different probing strategies, even though both belong to open addressing.
Common Applications
Open-addressing hash maps.
Hash sets.
Collision-resolution algorithm design.
Performance comparisons between probing strategies.
Memory-efficient lookup structures.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of quadratic probing and double hashing is the capability described here: Quadratic probing and double hashing are open-addressing techniques that generate alternative table positions after a collision. Both can reduce clustering compared with basic linear probing, but they use different methods to calculate probe sequences. |
Problem context | Quadratic Probing and Double Hashing is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using quadratic probing and double hashing, check its assumptions, input requirements, expected output, and resource constraints. |
Limitations
Performance depends on hash quality, input distribution, collision behavior, and the chosen load factor.
An implementation of quadratic probing and double hashing can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.
For quadratic probing and double hashing, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.
Practice Questions
| Question | Answer |
|---|
What is the main purpose of quadratic probing and double hashing? | Quadratic probing and double hashing are open-addressing techniques that generate alternative table positions after a collision. Both can reduce clustering compared with basic linear probing, but they use different methods to calculate probe sequences. |
What should be checked before applying quadratic probing and double hashing? | For quadratic probing and double hashing, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of quadratic probing and double hashing be validated? | Trace a representative quadratic probing and double hashing case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of quadratic probing and double hashing.
Identify the assumptions, inputs, and conditions relevant to quadratic probing and double hashing.
Evaluate an application of quadratic probing and double hashing for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures