Last updated April 10, 2022

Status: Tags: #cards/cmpt225/dataStructures/hash Links: Hash Functions

Open Addressing

Principles

Effective open addressing ?

• Size hash table should not be even
  • Increase probability that each position is part of probing sequence
    • Primes help with modulo

Types

Linear probing hashing

?

• Can just take current and add P(i) % size
  • p() is probing function, i is from 1 to size

Process

• %10

  • 10-60% full ~ O(1)
  • 60-80% full ~~ O(1)

  • 80% full ~ O(n)

• %11

  • up to 90% ~O(1)

Drawback

?

• Clustering

Quadratic probing

?

• Can just take current and add P(i^2) % size
  • p() is probing function, i is from 1 to size
• Example probings
  • 

Methods

?

• Constant adding
  • 
  • Synonyms will produce same sequence, not enter new ones
• Alternating between add and minus
  • 
  • Eventually lead to filling

Pros/Cons

?

• Pros
  • Reduce primary clustering from linear probing
• Cons
  • Produces different kind of clustering where some are avoided
    • Solution? Have a different hash index sequence for each index

Random probing

?

• Random number generator
• Probing example
  • 

Rehashing

?

• p(i) is a hashing function itself
  • $h_p(k)$ != 0
• Probing sequence
  • 

Tweak hash table size

?

• Estimate capacity required
• Double it and use as size

References:

Created:: 2022-03-25 18:31