Does this method of open addressing guarantee that every index will be checked?


#1

Question

In the context of this exercise, does this method of handling collisions for open addressing guarantee that every index will be checked?

Answer

Yes, this method of open addressing will ensure that every index of the array is checked as we encounter collisions and are finding a place to insert our new entry.

The method we’re using, in this lesson, will increase a variable by 1 each time we encounter a collision. When we try to recalculate the hash code, we provide this value as the count_collisions parameter to the hash method. For each collision, this value fo count_collisions will increase by 1.

By increasing this value by just 1 each time we get a collision, it will essentially check every other index.

For example, say we had a hash map where its array is currently storing

[
  ['key1', value1],
  ['key2', value2],
  ['key3', value3],
  None
]

If we tried to add a new entry, and it collided at index 0, it will then recalculate the hash code, and check the next index, 1. Each time there is a collision, it just shifts over by 1 index, and eventually, it will reach index 3, which is None.