Skip to content

Instantly share code, notes, and snippets.

@Nasdin
Created April 17, 2020 10:16
Show Gist options
  • Select an option

  • Save Nasdin/94084c87ce8fb8125e3963c54c6e92ac to your computer and use it in GitHub Desktop.

Select an option

Save Nasdin/94084c87ce8fb8125e3963c54c6e92ac to your computer and use it in GitHub Desktop.
Hashmap in Python without dictionaries
# Implement a hashmap in Python without using a dictionary
# A simple toy example, look to improve when the hashes start clashing with each other either by adapting a dynamic size
# Or using a better hash function
class HashMap(object):
def __init__(self, size, hash_function):
self.array = [None] * size
self.size = size
self.hash_function = hash_function
def __getitem__(self, item):
index = self._get_index(item)
value = self.array[index]
if value is None:
raise KeyError("Value does not exist")
return value
def _get_index(self, val):
return self.hash_function(val) % self.size
def __setitem__(self, item, value):
if item is None:
return ValueError("NoneTypes are not hashable")
if value is None:
return ValueError("NoneTypes cannot be stored")
index = self._get_index(item)
self.array[index] = value
def simple_hash_function(value):
str_hash = str(value)
hash_strs = 'abcdefghijklmnopqrstuvwxyz'
hash_strs = hash_strs + hash_strs.upper()
hash_strs = hash_strs + '0123456789'
hash_dict = {v:i for i,v in enumerate(hash_strs)}
value = [hash_dict[v] for v in value]
return sum(value)
example_hashmap = HashMap(30, simple_hash_function )
example_hashmap['toy'] = 123
example_hashmap['duck'] = 'quack'
assert example_hashmap['toy'] == 123
assert example_hashmap['duck'] == 'quack'
print(example_hashmap['toy'])
print(example_hashmap['duck'])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment