hash_map.py

"""
Hash map with open addressing.

https://en.wikipedia.org/wiki/Hash_table

Another hash map implementation, with a good explanation.
Modern Dictionaries by Raymond Hettinger
https://www.youtube.com/watch?v=p33CVV29OG8
"""

fromcollections.abcimportIterator, MutableMapping
fromdataclassesimportdataclass
fromtypingimportGeneric, TypeVar

KEY=TypeVar("KEY")
VAL=TypeVar("VAL")


@dataclass(frozen=True, slots=True)
class_Item(Generic[KEY, VAL]):
key: KEY
val: VAL


class_DeletedItem(_Item):
def__init__(self) ->None:
super().__init__(None, None)

def__bool__(self) ->bool:
returnFalse


_deleted=_DeletedItem()


classHashMap(MutableMapping[KEY, VAL]):
"""
 Hash map with open addressing.
 """

def__init__(
self, initial_block_size: int=8, capacity_factor: float=0.75
 ) ->None:
self._initial_block_size=initial_block_size
self._buckets: list[_Item|None] = [None] *initial_block_size
assert0.0<capacity_factor<1.0
self._capacity_factor=capacity_factor
self._len=0

def_get_bucket_index(self, key: KEY) ->int:
returnhash(key) %len(self._buckets)

def_get_next_ind(self, ind: int) ->int:
"""
 Get next index.

 Implements linear open addressing.
 >>> HashMap(5)._get_next_ind(3)
 4
 >>> HashMap(5)._get_next_ind(5)
 1
 >>> HashMap(5)._get_next_ind(6)
 2
 >>> HashMap(5)._get_next_ind(9)
 0
 """
return (ind+1) %len(self._buckets)

def_try_set(self, ind: int, key: KEY, val: VAL) ->bool:
"""
 Try to add value to the bucket.

 If bucket is empty or key is the same, does insert and return True.

 If bucket has another key or deleted placeholder,
 that means that we need to check next bucket.
 """
stored=self._buckets[ind]
ifnotstored:
self._buckets[ind] =_Item(key, val)
self._len+=1
returnTrue
elifstored.key==key:
self._buckets[ind] =_Item(key, val)
returnTrue
else:
returnFalse

def_is_full(self) ->bool:
"""
 Return true if we have reached safe capacity.

 So we need to increase the number of buckets to avoid collisions.

 >>> hm = HashMap(2)
 >>> hm._add_item(1, 10)
 >>> hm._add_item(2, 20)
 >>> hm._is_full()
 True
 >>> HashMap(2)._is_full()
 False
 """
limit=len(self._buckets) *self._capacity_factor
returnlen(self) >=int(limit)

def_is_sparse(self) ->bool:
"""Return true if we need twice fewer buckets when we have now."""
iflen(self._buckets) <=self._initial_block_size:
returnFalse
limit=len(self._buckets) *self._capacity_factor/2
returnlen(self) <limit

def_resize(self, new_size: int) ->None:
old_buckets=self._buckets
self._buckets= [None] *new_size
self._len=0
foriteminold_buckets:
ifitem:
self._add_item(item.key, item.val)

def_size_up(self) ->None:
self._resize(len(self._buckets) *2)

def_size_down(self) ->None:
self._resize(len(self._buckets) //2)

def_iterate_buckets(self, key: KEY) ->Iterator[int]:
ind=self._get_bucket_index(key)
for_inrange(len(self._buckets)):
yieldind
ind=self._get_next_ind(ind)

def_add_item(self, key: KEY, val: VAL) ->None:
"""
 Try to add 3 elements when the size is 5
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm._add_item(2, 20)
 >>> hm._add_item(3, 30)
 >>> hm
 HashMap(1: 10, 2: 20, 3: 30)

 Try to add 3 elements when the size is 5
 >>> hm = HashMap(5)
 >>> hm._add_item(-5, 10)
 >>> hm._add_item(6, 30)
 >>> hm._add_item(-7, 20)
 >>> hm
 HashMap(-5: 10, 6: 30, -7: 20)

 Try to add 3 elements when size is 1
 >>> hm = HashMap(1)
 >>> hm._add_item(10, 13.2)
 >>> hm._add_item(6, 5.26)
 >>> hm._add_item(7, 5.155)
 >>> hm
 HashMap(10: 13.2)

 Trying to add an element with a key that is a floating point value
 >>> hm = HashMap(5)
 >>> hm._add_item(1.5, 10)
 >>> hm
 HashMap(1.5: 10)

 5. Trying to add an item with the same key
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm._add_item(1, 20)
 >>> hm
 HashMap(1: 20)
 """
forindinself._iterate_buckets(key):
ifself._try_set(ind, key, val):
break

def__setitem__(self, key: KEY, val: VAL) ->None:
"""
 1. Changing value of item whose key is present
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm.__setitem__(1, 20)
 >>> hm
 HashMap(1: 20)

 2. Changing value of item whose key is not present
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm.__setitem__(0, 20)
 >>> hm
 HashMap(0: 20, 1: 10)

 3. Changing the value of the same item multiple times
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm.__setitem__(1, 20)
 >>> hm.__setitem__(1, 30)
 >>> hm
 HashMap(1: 30)
 """
ifself._is_full():
self._size_up()

self._add_item(key, val)

def__delitem__(self, key: KEY) ->None:
"""
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm._add_item(2, 20)
 >>> hm._add_item(3, 30)
 >>> hm.__delitem__(3)
 >>> hm
 HashMap(1: 10, 2: 20)
 >>> hm = HashMap(5)
 >>> hm._add_item(-5, 10)
 >>> hm._add_item(6, 30)
 >>> hm._add_item(-7, 20)
 >>> hm.__delitem__(-5)
 >>> hm
 HashMap(6: 30, -7: 20)

 # Trying to remove a non-existing item
 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm._add_item(2, 20)
 >>> hm._add_item(3, 30)
 >>> hm.__delitem__(4)
 Traceback (most recent call last):
 ...
 KeyError: 4
 """
forindinself._iterate_buckets(key):
item=self._buckets[ind]
ifitemisNone:
raiseKeyError(key)
ifitemis_deleted:
continue
ifitem.key==key:
self._buckets[ind] =_deleted
self._len-=1
break
ifself._is_sparse():
self._size_down()

def__getitem__(self, key: KEY) ->VAL:
"""
 Returns the item at the given key

 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm.__getitem__(1)
 10

 >>> hm = HashMap(5)
 >>> hm._add_item(10, -10)
 >>> hm._add_item(20, -20)
 >>> hm.__getitem__(20)
 -20

 >>> hm = HashMap(5)
 >>> hm._add_item(-1, 10)
 >>> hm.__getitem__(-1)
 10
 """
forindinself._iterate_buckets(key):
item=self._buckets[ind]
ifitemisNone:
break
ifitemis_deleted:
continue
ifitem.key==key:
returnitem.val
raiseKeyError(key)

def__len__(self) ->int:
"""
 Returns the number of items present in hashmap

 >>> hm = HashMap(5)
 >>> hm._add_item(1, 10)
 >>> hm._add_item(2, 20)
 >>> hm._add_item(3, 30)
 >>> hm.__len__()
 3

 >>> hm = HashMap(5)
 >>> hm.__len__()
 0
 """
returnself._len

def__iter__(self) ->Iterator[KEY]:
yieldfrom (item.keyforiteminself._bucketsifitem)

def__repr__(self) ->str:
val_string=", ".join(
f"{item.key}: {item.val}"foriteminself._bucketsifitem
 )
returnf"HashMap({val_string})"


if__name__=="__main__":
importdoctest

doctest.testmod()