CS计算机代考程序代写 chain Hashing

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 + c2i2) 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?