Hash table that automatically doubles in size when load exceeds 2/3. Examples: >>> rht = ResizableHashTable() >>> rht.put(1, 'a') >>> rht.get(1) 'a'
| 143 | |
| 144 | |
| 145 | class ResizableHashTable(HashTable): |
| 146 | """Hash table that automatically doubles in size when load exceeds 2/3. |
| 147 | |
| 148 | Examples: |
| 149 | >>> rht = ResizableHashTable() |
| 150 | >>> rht.put(1, 'a') |
| 151 | >>> rht.get(1) |
| 152 | 'a' |
| 153 | """ |
| 154 | |
| 155 | MIN_SIZE = 8 |
| 156 | |
| 157 | def __init__(self) -> None: |
| 158 | super().__init__(self.MIN_SIZE) |
| 159 | |
| 160 | def put(self, key: int, value: object) -> None: |
| 161 | """Insert or update, resizing if load factor exceeds two-thirds. |
| 162 | |
| 163 | Args: |
| 164 | key: The key to insert. |
| 165 | value: The value associated with the key. |
| 166 | """ |
| 167 | super().put(key, value) |
| 168 | if len(self) >= (self.size * 2) / 3: |
| 169 | self._resize() |
| 170 | |
| 171 | def _resize(self) -> None: |
| 172 | """Double the table size and rehash all existing entries.""" |
| 173 | keys, values = self._keys, self._values |
| 174 | self.size *= 2 |
| 175 | self._len = 0 |
| 176 | self._keys = [self._empty] * self.size |
| 177 | self._values = [self._empty] * self.size |
| 178 | for key, value in zip(keys, values, strict=False): |
| 179 | if key is not self._empty and key is not self._deleted: |
| 180 | self.put(key, value) |
no outgoing calls