Class Notes (834,152)
CSC263H1 (54)
Lecture 9

# Lecture 9 - Hashing with Chain.docx

3 Pages
87 Views

Department
Computer Science
Course
CSC263H1
Professor
Toniann Pitassi
Semester
Winter

Description
Hashing with chaining - m keys from a large U(universe) -Hash table T[0…m-1] - Hash function h: U → {0,1,…,m-1} Example: h(k) = k mod m (where m is a prime number) SUHA : ∀ 0 ≤ j ≤ m-1, PROB [h(k) = j] = 1/m Insert n keys in to T, then do Search(k). What is the expected cost(number of key comparisons)(E)? By SUHA, the expected length of any chain is ⍺ = n/m 2 Cases: 1) k !∈ (not element) T E ≈ ⍺ Comps 2) k ∈ T,  E ≈ ⍺ /2 Comps = ⍺/2 + 1 ­ (1/2m) h(k) = j Assume that m = Ɵ (n) => O(⍺) = n / Ɵ (n) = O(1) If k =ik Then expected cost (# of comps of search(k) = (n-i)/m + 1 (adding 1 is for k itself) Assume that PROB[k=ki = 1/n (for each 1≤ I ≤ n) 1 n n−i E = n ( ∑ ( +1) ) i=1 m n 1 1∑ (n−1) E = n ( m i=1 + n) 1∗n(n−1) E = 1 m n( 2 +n) 1 1 2∗n 1 E = 2m (n−1)+1= m −2m +1 1 −1 E = 2 ⍺
More Less

Related notes for CSC263H1
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.