Can we increment number_collisions by more than 1?


#1

Question

In the context of this exercise, can we increment number_collisions by more than 1 on each collision?

Answer

Yes, you can increment number_collisions by a different value if you’d like. But, you should try to use a value that ensures that every index will eventually be checked if there are collisions, which can depend on your array size.

For instance, say that instead of incrementing by 1 on each collision, we incremented the count_collisions by 2 on each collision. Furthermore, say that our array had an even size, 4. If we encounter collisions for this array, then some indexes will not be checked. Let’s say that the array is currently this,

array = [
  [key1, value1],
  None,
  [key3, value3],
  None
]

If we try to insert a new entry, and get a collision on index 0, it would then increment number_collisions by 2, and then check index 2. Index 2 would also have a colliding entry with [key3, value3], so it will recalculate the hash code. However, since this array is an even size, it will continue to only check the indexes 0 and 2. As we can see, indexes 1 and 3 will never be checked this way.

To avoid these kinds of issues, incrementing by 1 is usually a great choice, as it works on all array sizes, whether they are odd or even size, and will check every other index.