def __setitem__(self, key, value):
j = self._hash_func(key)
self._inner_setitem(j,key,value)
if self._n>len(self._table)//2: #调整大小，使负载因子小于等于0.5
self._resize(2*len(self._table)-1)
def __delitem__(self, key):
j = self._hash_func(key)
self._inner_delitem(j,key)
self._n -= 1
def _resize(self,cap):
old = list(self.items())
self._table = cap*[None]
self._n = 0
for (k,v) in old:
self[k] = v
其中innergetitem，_inner_setitem，_inner_delitem的实现需要结合处理冲突的方式,猜测self.items()是内部调用了__iter方法实现的
使用二级容器
class HashMapOne(HashMapBase):
"""使用二级容器解决冲突的方式实现的哈希表"""
def _inner_getitem(self,j,k):
bucket = self._table[j] #把二级容器叫做桶
if bucket is None:
raise KeyError('Key Error: '+ repr(k))
return bucket[k]
def _inner_setitem(self,j,k,v):
if self._table[j] is None:
self._table[j] = MyMap()
oldsize = len(self._table[j])
self._table[j][k] = v
if len(self._table[j])>oldsize:
self._n += 1
def _inner_delitem(self,j,k):
bucket = self._table[j]
if bucket is None:
raise KeyError('Key Error: ' + repr(k))
del bucket[k]
def __iter__(self):
for bucket in self._table:
if bucket is not None:
for key in bucket:
yield key
使用线性探测
class HashMapTwo():
"""使用线性探测解决冲突实现的哈希表"""
_AVAIL = object() # 标记删除位置
def _is_available(self, j):
"""判断该位置是否可用"""
return self._table[j] is None or self._table[j] is HashMapTwo._AVAIL
def _find_slot(self, j, k):
"""寻找键k所在的索引
如果找到了，返回(True,索引)
如果没找到，返回(False,第一个可提供的索引位置)"""
firstAvail = None
while True:
if self._is_available(j):
if firstAvail is None: # _AVAIL标记可以是第一个可提供的位置
firstAvail = j
if self._table[j] is None: # 跳过_AVAIL标记
return (False, firstAvail)
elif k == self._table[j].key:
return (True, j)
j = (j + 1) % len(self._table) # 向下一个查找
def _inner_getitem(self, j, k):
found, s = self._find_slot(j, k)
if not found:
raise KeyError('Key Error: ' + repr(k))
return self._table[s].value
def _inner_setitem(self, j, k, v):
found, s = self._find_slot(j, k)
if not found: # 使用第一个可提供的位置
self._table[s] = self.Item(k, v)
self._n += 1
else:
self._table[s].value = v