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]

_capacity_factor

_initial_block_size

_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