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