Understanding hash map by building a dummy one in python!

If like me, you have used dictionaries for years without understanding how they work. This is made for you!

What is a hash map and why we invented it?

A Hash Map is a data structure with an average insert and search time of a key in O(1). It is often used to build a dictionary, by associating arbitrary data to keys, allowing to retrieve corresponding data in O(1). To understand how a Hash Map achieves that let visualize and formalize the problem.

class DummyHashMap():
def __init__(self, storage_size=100):
self.size = storage_size
self.storage = [None for i in range(storage_size)]

def insert(self, key, value):
"""
insert key to self, and associate value
:param: key: hashable value
:return: None
"""
position = key % self.size # modulo operation
self.storage[position] = value
class DummyHashMap():
def __init__(self, storage_size=100, hash_func=hash):
# by default we use the default python hash function
self.size = storage_size
self.storage = [None for i in range(storage_size)]
self.hash = hash_func

def insert(self, key, value):
"""
insert key to self, and associate value
:param: key: hashable value
:return: None
"""
hash_value = self.hash(key)
position = hash_value % self.size # modulo operation
self.storage[position] = value
class DummyHashMap():    def __init__(self, storage_size=100, hash_func=hash):
# by default we use the default python hash function
self.size = storage_size
self.storage = [[]for i in range(storage_size)]
self.hash = hash_func
def position(self, key):
"""
return the position of key in self storage
:param: key: hashable value
:return: int
"""
hash_value = self.hash(key)
position = hash_value % self.size # modulo operation
return position
def insert(self, key, value):
"""
insert key to self, and associate value
:param: key: hashable value
:return: None
"""
position = self.position(key)
for e in self.storage[position]: if e[0] == key:
e[1] = value # We use the fact that lists are mutable
return
self.storage[position].append([key, value])
def get(self, key):
"""
If key in dict return the associated value else return an Error
:param: key: hashable value
:return: any | Error
"""
position = self.position(key)

for
e in self.storage[position]:
if e[0] == key:
return e[1]
raise(ValueError)def exist(self, key):
"""
If key in dict return TRUE else return FALSE
:param: key: hashable value
:return: bool
"""
position = self.position(key)

for
e in self.storage[position]:
if e[0] == key:
return True
return Falsedef delete(self, key):
"""
If key in dict delete the pair (key value)
:param: key: hashable value
:return: None
"""
position = self.position(key)
value = self.get(key) # we should take care of the error here
self
.storage[position].remove([key, value])