CSC263H1 Lecture 8: Lecture 8 - Hash Tables.docx
22 Apr 2014
School
Department
Course
Professor
Document Summary
Dictionary: s of n elements with keys k from a universe u = {0,1, ,u-1} Ops: insert, delete, search: 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,,9} and s = {2,5,9} |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] {0,1, ,m-1} key k hashes into slot h(k) of t. If h(k3) = i = h(k1) then k1 and k2 collide. Could use hashing with chaining to handle the collision. The worst case search(k) can take (n) time in a table with n elements. Expected time for search(k) is o(1) under reasonable assumptions: Any key is equally likely to hash into any of the m slots of t.
