Python Data Structures and Algorithms

Open addressing

The collision resolution mechanism we used in our example, linear probing, is an example of an open addressing strategy. Linear probing is really simple since we use a fixed interval between our probes. There are other open addressing strategies as well but they all share the idea that there is an array of slots. When we want to insert a key, we check whether the slot already has an item or not. If it does, we look for the next available slot.

If we have a hash table that contains 256 slots, then 256 is the maximum number of elements in that hash. Moreover, as the load factor increases, it will take longer to find the insertion point for the new element.

Because of these limitations, we may prefer to use a different strategy ...