Learn
Hash Maps: Python
Open Addressing

Now we’re going to implement an open addressing system so our hash map can resolve collisions. In open addressing systems, we check the array at the address given by our hashing function. One of three things can happen:

  • The address points to an empty cell.
  • The cell holds a value for the key we are getting/setting
  • The cell holds a value for a different key.

In the first case, this means that the hash map does not have a value for the key and no collision resolution needs to happen. Notice that this does not work if we want to be able to delete keys in our hash map. There are strategies for deleting pairs from a hash map (see Lazy Deletion) but we will not be investigating these.

In the second case, we’ve found the value for our key-value pair!

In the third case, we need to use our collision addressing strategy to find if our key is somewhere else (it may or may not be) so we should recalculate the index of our array.

Instructions

1.

Give HashMap.hash() another parameter: count_collisions. This will be the number of times the .hash() has hit a collision.

Have count_collisions default to 0.

2.

Instead of returning hash_code from .hash(), return hash_code + count_collisions.

Folder Icon

Sign up to start coding

Already have an account?