Hash map with open addressing.
| 34 | |
| 35 | |
| 36 | class HashMap(MutableMapping[KEY, VAL]): |
| 37 | """ |
| 38 | Hash map with open addressing. |
| 39 | """ |
| 40 | |
| 41 | def __init__( |
| 42 | self, initial_block_size: int = 8, capacity_factor: float = 0.75 |
| 43 | ) -> None: |
| 44 | self._initial_block_size = initial_block_size |
| 45 | self._buckets: list[_Item | None] = [None] * initial_block_size |
| 46 | assert 0.0 < capacity_factor < 1.0 |
| 47 | self._capacity_factor = capacity_factor |
| 48 | self._len = 0 |
| 49 | |
| 50 | def _get_bucket_index(self, key: KEY) -> int: |
| 51 | return hash(key) % len(self._buckets) |
| 52 | |
| 53 | def _get_next_ind(self, ind: int) -> int: |
| 54 | """ |
| 55 | Get next index. |
| 56 | |
| 57 | Implements linear open addressing. |
| 58 | >>> HashMap(5)._get_next_ind(3) |
| 59 | 4 |
| 60 | >>> HashMap(5)._get_next_ind(5) |
| 61 | 1 |
| 62 | >>> HashMap(5)._get_next_ind(6) |
| 63 | 2 |
| 64 | >>> HashMap(5)._get_next_ind(9) |
| 65 | 0 |
| 66 | """ |
| 67 | return (ind + 1) % len(self._buckets) |
| 68 | |
| 69 | def _try_set(self, ind: int, key: KEY, val: VAL) -> bool: |
| 70 | """ |
| 71 | Try to add value to the bucket. |
| 72 | |
| 73 | If bucket is empty or key is the same, does insert and return True. |
| 74 | |
| 75 | If bucket has another key that means that we need to check next bucket. |
| 76 | """ |
| 77 | stored = self._buckets[ind] |
| 78 | if not stored: |
| 79 | # A falsy item means that bucket was never used (None) |
| 80 | # or was deleted (_deleted). |
| 81 | self._buckets[ind] = _Item(key, val) |
| 82 | self._len += 1 |
| 83 | return True |
| 84 | elif stored.key == key: |
| 85 | stored.val = val |
| 86 | return True |
| 87 | else: |
| 88 | return False |
| 89 | |
| 90 | def _is_full(self) -> bool: |
| 91 | """ |
| 92 | Return true if we have reached safe capacity. |
| 93 |
no outgoing calls