Last active
March 29, 2024 16:52
-
-
Save jalcoding8/1878229bf3c96968a997bb0eb1cf486a to your computer and use it in GitHub Desktop.
Python hash_map delete issue
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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