Hash Collision Resolution

Linear Probing
(adjacent location checking)

• displacement
• clustering

Chaininglinked list stack queue

• buckets
• overflow areas

Buckets

• buckets fill up
• spill addressing

Chaining

• without separate overflow table
• with separate overflow area

Complexity of Hashing

  insert, delete, member

  O(1 + N/B)
  N = # keys  
  B = # buckets

What affects runtime?

• # buckets
• size of buckets
• size of overflow area
• # original
• likelihood of clustering

Hashing functions?

• mod/remainder
• mid-square
• random number generator (seedable)
• folding

Example of Chaining

• Sample C++ implementation file

Return to CIS 350 Index Page