Understanding HashMaps in Python: A Practical Example
Classified in Computers
Written at on 
English with a size of 7.43 KB.
Understanding HashMaps in Python
Introduction
This document demonstrates a simple implementation of a HashMap in Python. A HashMap, also known as a hash table, is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash function is used to compute an index into an array of buckets or slots, from which the desired value can be found.
Code Implementation
The following code provides a basic HashMap class in Python:
from random import *
class HashMap:
DEFAULT_SIZE = 4096
class item:
def __init__(self,k,v):
self.key = k
self.value = v
def __init__(self):
self.table = [None] * self.DEFAULT_SIZE
self.size = 0
def __eq__(self, other):
return self.items() == other.items() and self.keys() == other.keys()
def __ne__(self, other):
return not(self == other)
def clear(self):
self.__init__()
def keys(self):
keys = []
for i in range(len(self.table)):
if self.table[i] is not None:
keys.append(self.table[i].key)
return keys
def items(self):
items = []
for i in range(len(self.table)):
if self.table[i] is not None:
items.append(self.table[i].value)
return items
def probe(self,k):
where = self.hash_func(k)
for i in range(len(self.table)):
if self.table[where + i ** 2] is None:
return -1
if self.table[where + i ** 2].key is k:
return where + i ** 2
return -1
def __getitem__(self, item):
where = self.hash_func(item)
if self.table[where] is None:
raise KeyError("Key Error : " + str(item))
return self.table[self.probe(item)].value
def __setitem__(self, key, value):
where = self.hash_func(key)
for i in range(len(self.table)):
if self.table[where + i ** 2] is None or self.table[where + i ** 2].key is key:
if self.table[where + i ** 2] is None:
self.size += 1
self.table[where + i**2] = self.item(key, value)
return True
return False
def __delitem__(self, key):
where = self.hash_func(key)
if self.table[where] is None:
raise KeyError("Key Error : " + str(key))
find = self.probe(key)
if find >= 0:
del self.table[find]
self.size -= 1
def __len__(self):
return self.size
def __iter__(self):
self._i = 0
return self
def __next__(self):
if self._i < len(self.keys()):
result = self.items()[self._i]
self._i += 1
return result
else:
raise StopIteration
def hash_func(self, key):
return hash(key) % len(self.table)
Methods:
- __init__: Initializes the HashMap with a default size.
- __eq__: Checks if two HashMap objects are equal.
- __ne__: Checks if two HashMap objects are not equal.
- clear: Clears the HashMap.
- keys: Returns a list of keys in the HashMap.
- items: Returns a list of values in the HashMap.
- probe: Probes for a key in the HashMap.
- __getitem__: Retrieves the value associated with a key.
- __setitem__: Sets the value associated with a key.
- __delitem__: Deletes a key-value pair from the HashMap.
- __len__: Returns the number of key-value pairs in the HashMap.
- __iter__: Returns an iterator for the HashMap.
- __next__: Returns the next value in the iteration.
- hash_func: Computes the hash value for a given key.
Example Usage
Here's an example of how to use the HashMap class:
map = HashMap()
map["John"] = 15
print(map["John"])
map["John"] = 18
print(map["John"])
map["Marie"] = 15
del map["John"]
print(map.items())
This code creates a HashMap, adds some key-value pairs, updates a value, deletes a key-value pair, and prints the remaining values.