118 lines
3.6 KiB
Python
118 lines
3.6 KiB
Python
class HashTable:
|
|
def __init__(self, capacity=10):
|
|
if not isinstance(capacity, int) or isinstance(capacity, bool):
|
|
raise TypeError("Capacity must be an integer.")
|
|
if capacity <= 0:
|
|
raise ValueError("Capacity must be positive.")
|
|
|
|
self.capacity = capacity
|
|
self.empty = object()
|
|
self.deleted = object()
|
|
self.slots = [self.empty] * capacity
|
|
self.count = 0
|
|
|
|
def hash(self, key):
|
|
if not isinstance(key, str):
|
|
raise TypeError("Key must be a string.")
|
|
|
|
result = 0
|
|
for char in key:
|
|
result = result * 31 + ord(char)
|
|
return result % self.capacity
|
|
|
|
def probe(self, key):
|
|
start_idx = self.hash(key)
|
|
idx = start_idx
|
|
first_deleted = None
|
|
|
|
for _ in range(self.capacity):
|
|
slot = self.slots[idx]
|
|
if slot is self.empty:
|
|
return first_deleted if first_deleted is not None else idx
|
|
elif slot is self.deleted:
|
|
if first_deleted is None:
|
|
first_deleted = idx
|
|
elif slot[0] == key:
|
|
return idx
|
|
|
|
idx = (idx + 1) % self.capacity
|
|
|
|
if first_deleted is not None:
|
|
return first_deleted
|
|
raise RuntimeError("HashTable probe failed.")
|
|
|
|
def load_factor(self):
|
|
return float(self.count) / self.capacity
|
|
|
|
def __len__(self):
|
|
return self.count
|
|
|
|
def __contains__(self, key):
|
|
if not isinstance(key, str):
|
|
raise TypeError("Key must be a string.")
|
|
try:
|
|
idx = self.probe(key)
|
|
slot = self.slots[idx]
|
|
return slot is not self.empty and slot is not self.deleted and slot[0] == key
|
|
except RuntimeError:
|
|
return False
|
|
|
|
def __getitem__(self, key):
|
|
if not isinstance(key, str):
|
|
raise TypeError("Key must be a string.")
|
|
idx = self.probe(key)
|
|
slot = self.slots[idx]
|
|
if slot is not self.empty and slot is not self.deleted and slot[0] == key:
|
|
return slot[1]
|
|
raise KeyError(key)
|
|
|
|
def __setitem__(self, key, value):
|
|
if not isinstance(key, str):
|
|
raise TypeError("Key must be a string.")
|
|
|
|
is_new = not self.__contains__(key)
|
|
if is_new:
|
|
if (self.count + 1) / self.capacity > 0.7:
|
|
self._resize()
|
|
|
|
idx = self.probe(key)
|
|
slot = self.slots[idx]
|
|
|
|
if slot is self.empty or slot is self.deleted:
|
|
self.slots[idx] = (key, value)
|
|
self.count += 1
|
|
elif slot[0] == key:
|
|
self.slots[idx] = (key, value)
|
|
|
|
def __delitem__(self, key):
|
|
if not isinstance(key, str):
|
|
raise TypeError("Key must be a string.")
|
|
idx = self.probe(key)
|
|
slot = self.slots[idx]
|
|
if slot is not self.empty and slot is not self.deleted and slot[0] == key:
|
|
self.slots[idx] = self.deleted
|
|
self.count -= 1
|
|
else:
|
|
raise KeyError(key)
|
|
|
|
def __iter__(self):
|
|
for slot in self.slots:
|
|
if slot is not self.empty and slot is not self.deleted:
|
|
yield slot[0]
|
|
|
|
def _resize(self):
|
|
old_slots = self.slots
|
|
self.capacity *= 2
|
|
self.slots = [self.empty] * self.capacity
|
|
self.count = 0
|
|
|
|
for slot in old_slots:
|
|
if slot is not self.empty and slot is not self.deleted:
|
|
key, value = slot
|
|
idx = self.probe(key)
|
|
self.slots[idx] = (key, value)
|
|
self.count += 1
|
|
|
|
|
|
|