Я пытаюсь реализовать карту ha sh, мой код хранит ключи и значения, но при попытке получить значение с помощью ключа он всегда возвращает None, я использую python алгоритмы и структуру данных goodrich ссылка
from random import randrange
class MapBase:
class item:
def __init__(self,k,v):
self.key = k
self.value = v
def __eq__(self, other):
return self.key == other.key
def __ne__(self, other):
return not self.key == other.key
def __lt__(self, other):
return self.key < other.key
class UnsortedMap(MapBase):
def __init__(self):
self.data = []
self.size = 0
def __getitem__(self, item):
for i in self.data:
if item == i.key:
return i.value
raise KeyError('Not Existing in the bucket')
def __setitem__(self, key, value):
item = self.item(key,value)
for i in self.data:
if key == i.key:
i.value = value
return
self.data.append(item)
def __len__(self):
return len(self.data)
def __delitem__(self, key):
if len(self) == 0:
raise KeyError('the map is empty')
for i in range(len(self.data)):
if key == self.data[i].key:
del self.data[i]
return
raise KeyError('The key doesnot exist in the map')
def __iter__(self):
for i in self.data:
yield i
class HashMapBase(MapBase):
def __init__(self,cap = 11, p = 109345121):
self.data = cap*[None]
self.n = 0
self.prime = p
self.scale = 1+ randrange(p-1)
self.shift = randrange(self.prime)
def hash_function(self,k):
return (hash(k)*self.scale + self.shift) %self.prime %len(self.data)
def __len__(self):
return self.n
def items(self):
for i in self.data:
for item in i:
yield item.key, item.value
def resize(self,c):
old = self.items()
self.data = c*[None]
self.n = 0
for (k,v) in old:
self.data[k] = v
def __setitem__(self, key, value):
i = self.hash_function(key)
self.bucket_setitem(i,key,value)
if self.n > len(self.data) // 2:
self.resize(2*len(self.data) -1)
def __getitem__(self, key):
i = self.hash_function(key)
self.bucket_getitem(i,key)
def __delitem__(self, key):
self.bucket_delitem(key)
class SeparateHashMap(HashMapBase):
def bucket_setitem(self,i,key,value):
if self.data[i] is None:
self.data[i] = UnsortedMap()
old_size = len(self.data[i])
self.data[i][key] = value
if len(self.data[i]) > old_size:
self.n += 1
def bucket_getitem(self,i,key):
bucket = self.data[i]
if bucket is None:
raise KeyError("The bucket is empty")
return bucket[key]
def bucket_delitem(self,key):
i = self.hash_function(key)
for item in self.data[i]:
if key == item.key:
del item[i][key]
return
raise KeyError("The key doesn't exist")
def __iter__(self):
for bucket in self.data:
if bucket is not None:
for item in bucket:
yield item.key
это мой код, и реализация была просто:
s = SeparateHashMap()
s[5] = 'v1'
s.__setitem__('key1','value1')
print(len(s))
for key in s:
print(key)
print(s.__getitem__(key))
и результатов было 5 Нет 'key1' Нет Я попытался переформатировать setitem и getitem, но ничего не изменило результаты одинаковы