Skip to content

Instantly share code, notes, and snippets.

@jalcoding8
Last active March 29, 2024 16:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jalcoding8/1878229bf3c96968a997bb0eb1cf486a to your computer and use it in GitHub Desktop.
Save jalcoding8/1878229bf3c96968a997bb0eb1cf486a to your computer and use it in GitHub Desktop.
Python hash_map delete issue
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]
number_collisions += 1
return
"""this is my function to delete a key/value bucket from the hash but it is problematic and incomplete. Even though the
the key/value pair is removed/deleted, the nested array [] remnant persists and cannot be reused."""
def delete_pair(self, key):
array_index = self.compressor(self.hash(key))
possible_delete = self.array[array_index]
print(possible_delete)
# returns index of deleted pair
print("Below is the index of the key/value (above) that will bedeleted.")
print(self.array.index(possible_delete))
empty_array = self.array.index(possible_delete)
if possible_delete[0] == key:
possible_delete.pop()
possible_delete.pop()
#self.array.pop(empty_array)
#I added this 2nd if statement (below) because even though the key/value was deleted from the array (index 1)
#the empty [] persisted and could not be used, so I had to find the empty array and revert it back to 'None' type value so it could be reused and the array is still of the originally intended size. :-0
if self.array[empty_array] == []:
self.array[empty_array] = None
hash_map = HashMap(20)
hash_map.assign('gabbro', 'igneous')
hash_map.assign('sandstone', 'sedimentary')
hash_map.assign('gneiss', 'metamorphic')
print()
print(hash_map.array)
print()
print(hash_map.retrieve('gabbro'))
print(hash_map.retrieve('sandstone'))
print(hash_map.retrieve('gneiss'))
print()
#calling delete function on hash (array)
#for pair 'gabbo' 'igneous'
#while it returns None the actual [] stays
print(hash_map.delete_pair('gabbro'))
print()
"""printing hash to reveal the hash doesn't delete completely. Instead the empty nested array (bucket) lingers but cannot be reused. It is the second element [None, [], None, None,...]"""
print(hash_map.array)
print()
"""in the output,this is the offending empty array that must be removed from the hash_map
if it is not removed it is useless space
so this is a brute force line of code way to remove
I haven't found a complete function to do so yet"""
print(hash_map.array.pop(1))
print()
"""so now in the ouput we will see the empty bucket is gone and the space is reuseable and set to None"""
print(hash_map.array)
"""In output showing the array_index can now be reused
now I assign a new pair to the same index, so now space/time complexity is better
and the hash_map functions as it should
I input a key/value pair that compresses to the same index-value to illustrate"""
hash_map.assign('on', 'one')
print()
print(hash_map.array)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment