Skip to content

Instantly share code, notes, and snippets.

@Edald123
Last active Aug 3, 2021
Embed
What would you like to do?
Hash Map in Python using Open Addressing to resolve collisions
"""
Demonstrative implementation of hash tables in python
without using dictionaries:
This implementation uses an "open addressing system"
to resolve collisions.
In open addressing systems, we check the array at the
address given by our hashing function. One of three
things can happen:
1. The address points to an empty cell.
2. The cell holds a value for the key we are getting/setting
3. The cell holds a value for a different key.
1. 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.
2. In the second case, we’ve found the value for our key-value
pair!
3. 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.
"""
class HashMap:
def __init__(self, array_size):
self.array_size = array_size
self.array = [None for item in range(array_size)]
def hash(self, key, count_collisions=0):
key_bytes = key.encode()
hash_code = sum(key_bytes)
return hash_code + count_collisions
def compressor(self, hash_code):
return hash_code % self.array_size
def assign(self, key, value):
array_index = self.compressor(self.hash(key))
current_array_value = self.array[array_index]
if current_array_value is None:
self.array[array_index] = [key, value]
return
if current_array_value[0] == key:
self.array[array_index] = [key, value]
return
# Collision!
number_collisions = 1
while(current_array_value[0] != key):
new_hash_code = self.hash(key, number_collisions)
new_array_index = self.compressor(new_hash_code)
current_array_value = self.array[new_array_index]
if current_array_value is None:
self.array[new_array_index] = [key, value]
return
if current_array_value[0] == key:
self.array[new_array_index] = [key, value]
return
number_collisions += 1
return
def retrieve(self, key):
array_index = self.compressor(self.hash(key))
possible_return_value = self.array[array_index]
if possible_return_value is None:
return None
if possible_return_value[0] == key:
return possible_return_value[1]
retrieval_collisions = 1
while (possible_return_value != key):
new_hash_code = self.hash(key, retrieval_collisions)
retrieving_array_index = self.compressor(new_hash_code)
possible_return_value = self.array[retrieving_array_index]
if possible_return_value is None:
return None
if possible_return_value[0] == key:
return possible_return_value[1]
retrieval_collisions += 1
return
# Test cases:
hash_map = HashMap(16)
hash_map.assign('gabbro', 'igneous')
hash_map.assign('sandstone', 'sedimentary')
hash_map.assign('gneiss', 'metamorphic')
print(hash_map.retrieve('gabbro'))
print(hash_map.retrieve('sandstone'))
print(hash_map.retrieve('gneiss'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment