92 lines
2.5 KiB
Python
92 lines
2.5 KiB
Python
from typing import Generic, TypeVar
|
|
from math import ceil
|
|
|
|
K, V = TypeVar('K'), TypeVar('V')
|
|
|
|
class HashItem(Generic[K, V]):
|
|
def __init__(self, key: K, value: V):
|
|
self.key = key
|
|
self.value = value
|
|
|
|
class HashTable(Generic[K, V]):
|
|
def __init__(self):
|
|
self.__size = 256
|
|
self.__count = 0
|
|
self.__slots: list[HashItem[K, V]] = [None for _ in range(self.__size)]
|
|
|
|
def __hash(self, key: K):
|
|
multiplier = 1
|
|
hashValue = 0
|
|
|
|
for character in key:
|
|
hashValue += multiplier * ord(character)
|
|
multiplier += 1
|
|
|
|
return hashValue % self.__size
|
|
|
|
def __filledSlots(self):
|
|
return list(filter(lambda x: x is not None, self.__slots))
|
|
|
|
def __load(self):
|
|
return len(list(self.__filledSlots())) / self.__size
|
|
|
|
def __grow(self, newSize: int):
|
|
self.__slots += [None for _ in range(newSize - self.__size)]
|
|
self.__size = newSize
|
|
|
|
def put(self, key: K, value: V):
|
|
item = HashItem(key, value)
|
|
hashValue = self.__hash(key)
|
|
|
|
while self.__slots[hashValue] != None:
|
|
if self.__slots[hashValue].key == key:
|
|
break
|
|
|
|
hashValue += 1
|
|
hashValue %= self.__size
|
|
|
|
if self.__slots[hashValue] == None:
|
|
self.__count += 1
|
|
|
|
# If the hash table is nearing its maximum load, increase the size of the hash table by 10%
|
|
if self.__load() >= 0.75:
|
|
self.__grow(ceil(self.__size * 1.1))
|
|
|
|
self.__slots[hashValue] = item
|
|
|
|
def get(self, key: K):
|
|
hashValue = self.__hash(key)
|
|
|
|
for slot in self.__filledSlots():
|
|
if hashValue == self.__hash(slot.key):
|
|
return slot.value
|
|
|
|
return None
|
|
|
|
def __setitem__(self, key: K, value: V):
|
|
self.put(key, value)
|
|
|
|
def __getitem__(self, key: K):
|
|
return self.get(key)
|
|
|
|
def __str__(self):
|
|
template = " {: ^10} | {: ^10}"
|
|
out = template.format("Key", "Value")
|
|
out += "\n" + ("-" * (len(out) // 2)) + "|" + ("-" * (len(out) // 2)) + "\n"
|
|
|
|
slots = self.__filledSlots()
|
|
|
|
for i, slot in enumerate(slots):
|
|
out += template.format(slot.key, slot.value)
|
|
|
|
if i + 1 != len(slots):
|
|
out += "\n"
|
|
|
|
return out
|
|
|
|
def __len__(self):
|
|
return len(self.__slots)
|
|
|
|
ages = HashTable[str, int]()
|
|
ages["John Doe"] = 16
|
|
print(ages)
|