Division method assume all keys are integers, and define h(k)=k mod m Deficiency: Dont pick an m that has a small divisor d. a preponderance of keys that are congruent modulo d can adversely affect uniformity Extreme deficiency: Ifm=2 then the hash doesn t even depend on all the bits of k Ifk=1011000111011010,andr=6,then h()=0110102 h(k) o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.9 h(k) Division method Assume all keys are integers, and define h(k) = k mod m. Extreme deficiency: If m = 2r, then the hash doesn’t even depend on all the bits of k: • If k = 10110001110110102 and r = 6, then h(k) = 0110102 . Deficiency: Don’t pick an m that has a small divisor d. A preponderance of keys that are congruent modulo d can adversely affect uniformity