Skip to main content

Hash Table Quadratic Probing Rehashing Method

1. Overview​

Quadratic probing is an open addressing method for resolving hash collisions. When a collision occurs in a hash table, it uses a quadratic function to calculate the next possible position, effectively reducing the phenomenon of data clustering.

2. Basic Principle​

When the computed hash address is already occupied, the next available position is sought following a quadratic function pattern.

3. Probe Sequence​

Assuming the initial position is h and the hash table size is m, the probe sequence is:

h, (h+1²) % m, (h+2²) % m, (h+3²) % m, ..., (h+k²) % m

where k is the probe count.

4. Advantages​

  • Produces less clustering than linear probing
  • Can distribute data more uniformly

5. Disadvantages​

  • Slightly higher computational complexity than linear probing
  • Cannot probe all positions in the hash table (unless the table size is a prime number squared)

6. Implementation Steps​

  1. Compute the initial hash value h = H(key)
  2. If position h is occupied, compute (h+1²) % m
  3. If the new position is still occupied, compute (h+2²) % m
  4. Repeat this process until an empty position is found or the entire table has been probed

7. Example​

Assume the hash table size is 11 and we want to insert the key 49:

  1. Initial hash value: H(49) = 49 % 11 = 5
  2. If position 5 is occupied, the next positions to try will be:
    • (5+1²) % 11 = 6
    • (5+2²) % 11 = 9
    • (5+3²) % 11 = 3
    • ...and so on

8. Notes​

  • Choosing an appropriate table size is important; selecting a prime number typically yields better distribution
  • In practice, it may be necessary to combine quadratic probing with other methods (such as double hashing) to handle extreme cases
  • Quadratic probing works well when the load factor is not too high

9. Application Scenarios​

  • Database indexing
  • Cache systems
  • Symbol table implementations
  • Built-in hash table implementations in certain programming languages

10. Conclusion​

Quadratic probing is a relatively effective method for resolving hash collisions in practice, particularly suitable for medium-sized hash tables and scenarios with lower load factors.