Class Notes (806,815)
Canada (492,451)
CSC263H1 (52)
Lecture 8

Lecture 8 - Hash Tables.docx

3 Pages
Unlock Document

University of Toronto St. George
Computer Science
Toniann Pitassi

Worst Case vs Avg Complexity Hash Tables [CLRS 11] Dictionary: S of n elements with keys k from a universe U = {0,1,…,u-1} OPS: Insert, Delete, Search 1) If |U| is small -Store S in a Direct Access Table T[0,1,..,u-1] -Store element x with key k into T[k] Suppose U = {0,1,2,..,9and S = {2,5,9} Index 0 1 2 3 4 5 6 7 8 9 T X X 2 X X 5 X X X 9 2) |U| is large |S| ≪ |U| Ex: k is 64 bit. |U| = 2^64 keys cannot use a Table T with 2^64 entries Let n = # of keys in S Let m = SIZE of hashTable T [0,1,…,m-1] Hash Function h: U----> {0,1,…,m-1} k ∈ U h(k) = i ∈ {0,1,…,m-1} key k hashes into slot h(k) of T Index 0 1 … i … j … m-1 Table … K1 … K2 … If H(k3) = i = H(k1) then k1 and k2 collide Could use hashing with chaining to handle the collision - If something c
More Less

Related notes for CSC263H1

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


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.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.