Resolving collisions by open addressing No storage is used outside of the hash table itself. Insertion systematically probes the table until an empty slot is found The hash function depends on both the key and probe number h:U×{0,1,…,m-1}→>{0,1,…,m-1} The probe sequence (h(k,), h(k, 1),..., h(k,m-1)) should be a permutation of 0, 1 The table may fill up, and deletion is difficult(but not impossible o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.14© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.14 Resolving collisions by open addressing No storage is used outside of the hash table itself. • Insertion systematically probes the table until an empty slot is found. • The hash function depends on both the key and probe number: h : U × {0, 1, …, m–1} → {0, 1, …, m–1}. • The probe sequence 〈h(k,0), h(k,1), …, h(k,m–1)〉 should be a permutation of {0, 1, …, m–1}. • The table may fill up, and deletion is difficult (but not impossible)