CSE 373 Lecture Notes - Lecture 4: Quadratic Probing, Double Hashing, Open Addressing
17 May 2018
School
Department
Course
Professor
CSE 373 Lecture 4
Hash function – use % of the table size to determine where to put value
- INSERT HASH FUNCTION SLIDE
- Collision – when there are duplicates (e.g., 20 % 10 and 10 % 0)
o Fewer collisions → better runtime (closer to O(1))
o Solution 1: chaining – each space in the array holds a “bucket” that can store
multiple values
▪ Generally implemented w/ linked list
▪ Load factor (lambda) = n / c
• n = total number of key-value pairs
• c = array capacity
▪ Worst case is when everything ends up in same bucket
▪ Ideally have uniform distribution of outputs
o Resizing array’s internal capacity
▪ Resize when lambda ~= 1.0
▪ Must rehash
o Solution 2: open addressing – resolve collisions by choosing a different location
if natural choice is alreadyfull
▪ Type 1: linear probing – keep checking next element until spot found
• Drawback – causes clustering → leads to more looping across
array
• Best runtime – empty table
• Worst runtime – when table is full / hitting a cluster
• Maximum load factor = 1 (b/c only store 1 item per bucket)
• Resize when load factor (lambda) ~.5
▪ Type 2: quadratic probing – if there’s a collision, try next i2 space
• Drawback – could end up with infinite loop if spot never found
• Can still end up with clusters, when hashing to same natural
location
