Collisions resolution by chaining Records in the same slot are linked into a list T 4968|心521 h(49)=h(86)=h(52)=i
Collisions resolution by chaining Records in the same slot are linked into a list. T i 49 68 52 / h(49) = h(86) = h(52) = i
Hash functions Designing good functions is quite nontrivial For now, we assume they exist. Namely, we assume simple uniform hashing Each key k e K of keys is equally likely to be hashed to any slot of table T, independent of where other keys are hashed
Hash functions Designing good functions is quite nontrivial For now, we assume they exist. Namely, we assume simple uniform hashing: – Each key k ∈ K of keys is equally likely to be hashed to any slot of table T, independent of where other keys are hashed
Analysis of chaining Let n be the number of keys in the table and let m be the number of slots Define the load factor of T to be a=n/m average number of keys per slot The number of elements examined during a successful search for an element x is 1 more that the number of elements that appear before x in x's list
Analysis of chaining α = n m/ Let n be the number of keys in the table, and let m be the number of slots. Define the load factor of T to be = average number of keys per slot. The number of elements examined during a successful search for an element x is 1 more that the number of elements that appear before x in x’s list
Search cost Expected time to search for a record with a given key (1+a) apply hash h search function and the list access slot Expected search time o(1)ifa=O(1 or equivalently, ifn=O(m)
Search cost Expected time to search for a record with a given key Θ(1 ) +α apply hash function and access slot search the list Expected search time = Θ(1) if = O(1), or equivalently, if n = O(m). α
Analysis of successful search Let x: denote the ith element inserted into the table for i=1, 2,,n, and let ki-keyxl For keys k, and k we define the indicator variable rh(ki=h(k,)) Under the assumption of simple uniform hashing we have pr{hn(k1)=h(k,)}=m:(
Analysis of successful search 11 1 { ( ) ( )} ( ) i j pr h k h k m mm m = =⋅ ⋅ = Let xi denote the ith element inserted into the table, for i = 1, 2, .., n, and let ki = key [ xi ]. Under the assumption of simple uniform hashing, we have: For keys ki and kj, we define the indicator variable Xij = I{ h ( ki) = h ( kj)}