Linear Probing

• In open addressing, all the elements are stored directly in the hash table. • If an address is already being used, then we systematically move to another address in a predetermined sequence until we find an empty slot. • Hence, we can think of the hash function as producing not just a single address, but a sequence of addresses h(x, 0), h(x, 1),..., h(x,M − 1). • Ideally, the sequence produced should include every address in the table. • The effect is essentially the same as chaining except that we compute the pointers instead of storing them. • The price we pay is that as the table fills up, the operations get more expensive. • It is also much more difficult to delete items. 2 IE170 Lecture 12