Learn
Hash Maps: Python
Handling Collisions in the Setter

Our hash and compression functions together can result in collisions. This is when two different keys resolve to the same array index. In our current implementation, all keys that resolve to the same index are treated as if they are the same key.

Our first step in implementing a collision strategy is updating our .assign() and .retrieve() methods to set the value with the key and check the key before retrieving a value.

Instructions

1.

We’re going to overwrite the functionality for .assign(). After finding the array_index, we want to do a check of the content that’s currently at self.array[array_index].

In order to avoid overwriting the wrong key, check the existing value in the array at self.array[array_index]. Save this into current_array_value.

2.

There are three possibilities for current_array_value:

  • It has the same key as key.
  • It has a different key than key.
  • It’s None.

If current_array_value already has contents, check if the saved key is different from the key we are currently processing. If the keys are the same, overwrite the array value.

If the keys are different, we’re going to implement a way to find the next array index where our key should go. We’ll get to handling different keys later.

3.

Lastly, we want to store the key and the value instead of just the key if current_array_value is equal to None. Instead of just saving value, save [key, value] to the array.

Folder Icon

Sign up to start coding

Already have an account?