class HashTable: _DELETED = object() def __init__(self, capacity=10): if isinstance(capacity, bool) or not isinstance(capacity, int): raise TypeError("Capacity must be an integer") if capacity <= 0: raise ValueError("Capacity must be positive") self._capacity = capacity self._slots = [None] * capacity self._size = 0 @property def capacity(self): return self._capacity def hash(self, key): if not isinstance(key, str): raise TypeError("Key must be a string") h = 0 for char in key: h = (31 * h + ord(char)) % self.capacity return h def probe(self, key): start = self.hash(key) first_deleted = None for step in range(self.capacity): index = (start + step) % self.capacity slot = self._slots[index] if slot is None: return first_deleted if first_deleted is not None else index if slot is self._DELETED: if first_deleted is None: first_deleted = index elif slot[0] == key: return index if first_deleted is not None: return first_deleted raise RuntimeError("Hash table is full") def __setitem__(self, key, value): index = self.probe(key) slot = self._slots[index] if slot is not None and slot is not self._DELETED: self._slots[index] = (key, value) return if (self._size + 1) * 10 > self.capacity * 7: self._resize() index = self.probe(key) self._slots[index] = (key, value) self._size += 1 def __getitem__(self, key): index = self.probe(key) slot = self._slots[index] if slot is None or slot is self._DELETED: raise KeyError(key) return slot[1] def __delitem__(self, key): index = self.probe(key) slot = self._slots[index] if slot is None or slot is self._DELETED: raise KeyError(key) self._slots[index] = self._DELETED self._size -= 1 def __contains__(self, key): try: self[key] except KeyError: return False return True def __len__(self): return self._size def __iter__(self): for slot in self._slots: if slot is not None and slot is not self._DELETED: yield slot[0] def load_factor(self): return len(self) / self.capacity def _resize(self): old_slots = self._slots self._capacity *= 2 self._slots = [None] * self.capacity for slot in old_slots: if slot is not None and slot is not self._DELETED: self._slots[self.probe(slot[0])] = slot