Analysis of chaining We make the assumption of simple uniform hashing Each key k e K of keys is equally likely to be hashed to any slot of table independent of where other keys are hashed 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 o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.6 Analysis of chaining We make the assumption of 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. 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 α = n/m = average number of keys per slot
Search cost Expected time to search for a record with a given key=(1+∞) apply hash h searc function and the list access slot Expected search time =o(1)ifa=O(1) or equivalently, ifn=O(m) o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.7 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)
Choosing a hash function The assumption of simple uniform hashing is hard to guarantee but several common techniques tend to work well in practice as long as their deficiencies can be avoided Desirata: a good hash function should distribute the keys uniformly into the slots of the table Regularity in the key distribution should not affect this uniformity o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7. 8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.8 Choosing a hash function The assumption of simple uniform hashing is hard to guarantee, but several common techniques tend to work well in practice as long as their deficiencies can be avoided. Desirata: • A good hash function should distribute the keys uniformly into the slots of the table. • Regularity in the key distribution should not affect this uniformity