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
.retrieve() methods to set the value with the key and check the key before retrieving a value.
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
In order to avoid overwriting the wrong key, check the existing value in the array at
self.array[array_index]. Save this into
There are three possibilities for
- It has the same key as
- It has a different key than
current_array_value is equal to
None, instead of just saving
[key, value] to the array.
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.