Linear Probing

Complete the insert and get methods.

Insert

1. Compute the index for the key in the hashmap with self.key_to_index(key). Create an original_index variable and assign index to it.
2. Initialize a boolean variable first_iteration to True.
3. Begin a while loop that continues as long as the hashmap's slot at index is occupied (not None) and its key doesn't match the key being inserted.
   • If this is not the first iteration and the current index equals original_index, raise an exception "hashmap is full". This means we've traversed the entire hashmap without finding an empty slot.
   • Increment index by 1 and wrap it around to the start of the hashmap if necessary (using modulo operation with hashmap's length).
   • Set first_iteration to False after the first iteration.
4. Insert the key-value pair at the found index: self.hashmap[index] = (key, value).

Get

1. Compute the index for the key in the hashmap with self.key_to_index(key). Create an original_index variable and assign index to it.
2. Initialize a boolean variable first_iteration to True.
3. Begin a while loop that continues as long as the hashmap's slot at index is occupied (not None).
   • If the key at the current index matches the key being searched, return the value from the key-value pair in the hashmap at the current index.
   • If this is not the first iteration and the current index equals original_index, raise an exception "sorry, key not found". This means we've traversed the entire hashmap without finding the key.
   • If the key does not match, increment index by 1 and wrap it around to the start of the hashmap if necessary (using modulo operation with hashmap's length).
   • Set first_iteration to False after the first iteration.
4. If the while loop completes without finding a match, raise an exception "sorry, key not found".