PowerPoint Presentation
Hashing
CSC263 Week 5 Lectures 2-3, Week 6 Lecture 1
Definitions
Universe of keys U
Hash table T
each location called a ____________ or __________
Hash Function
Collision
Chaining or Closed Addressing
Each slot of T stores a linked list of items that hash to this bucket
h(k1) = h(k4) = h(k6) = 2 h(k2) = h(k5) = 1 h(k3) = m-1
Chalk Talk
Worksheet
Worksheet Questions 1-2: One Solution
This solution assumes that new elements are inserted at the head of the chain. You could also insert at the tail.
Average-case Runtime of Search with Chaining
Chalk Talk
Simple Uniform Hashing Assumption
consequence
Load factor
Distribution over input:
Average-case Runtime of Search with Chaining
Chalk Talk
Chalk Talk
Chalk Talk
Chalk Talk
Open Addressing
Keep all records IN the table
When the first bucket is already taken, go to another bucket
Probe sequence:
Want (require?) the probe sequence
to be a permutation of
Worksheet
Q3 & Q4: Open Addressing Example
h(k,i) = (h’(k) + i) mod m i = 0, 1, 2, … , n-1
h’(k) = k mod m
Challenges with Linear Probing
Primary clustering
Q: Would using a larger step than 1 help?
Q. How about a random step size?
Zoom Poll
Quadratic Probing
h(k,i) = (h’(k) + c1i + c2i
2) mod m i = 0, 1, 2, … , n-1
h’(k) = k mod m
Challenge?
Double Hashing
h(k,i) = (h1(k) + h2(k)i) mod m i = 0, 1, 2, … , n-1
h1(k) = k mod m
Constraints on
hash functions?
What about deleting in open-addressing?