Hash functions Solution: Use a hash function h to map the universe U of all keys into {0,1,…,m-1} 0 k h(k h(k K k h(k2)=h(k5 k3 When a record to be inserted maps to an already occupied slot in T' a collision occurs o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.4 As each key is inserted, h maps it to a slot of T. Hash functions Solution: Use a hash function h to map the universe U of all keys into {0, 1, …, m–1}: U K k1 k2 k3 k4 k5 0 m–1 h(k1) h(k4) h(k2) h(k3) When a record to be inserted maps to an already occupied slot in T, a collision occurs. T = h(k5)