data_structures.hashing.hash_map

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

Attributes

KEY

VAL

_deleted

Classes

HashMap

Hash map with open addressing.

_DeletedItem

_Item

Module Contents

class data_structures.hashing.hash_map.HashMap(initial_block_size: int = 8, capacity_factor: float = 0.75)

Bases: collections.abc.MutableMapping[KEY, VAL]

Hash map with open addressing.

__delitem__(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

__getitem__(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
__iter__() → collections.abc.Iterator[KEY]
__len__() → 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
__repr__() → str
__setitem__(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)

_add_item(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)

_get_bucket_index(key: KEY) → int
_get_next_ind(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

_is_full() → 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
_is_sparse() → bool

Return true if we need twice fewer buckets when we have now.

_iterate_buckets(key: KEY) → collections.abc.Iterator[int]
_resize(new_size: int) → None
_size_down() → None
_size_up() → None
_try_set(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.

_buckets: list[_Item | None] = [None, None, None, None, None, None, None, None]
_capacity_factor = 0.75
_initial_block_size = 8
_len = 0
class data_structures.hashing.hash_map._DeletedItem

Bases: _Item

__bool__() → bool
class data_structures.hashing.hash_map._Item

Bases: Generic[KEY, VAL]

key: KEY
val: VAL
data_structures.hashing.hash_map.KEY
data_structures.hashing.hash_map.VAL
data_structures.hashing.hash_map._deleted