引自免费微信小程序：皆我百晓生
首先，我们已经给出了Node和LinkedList类，接下来我们将实现ExtensibleHashTable类。为了简化哈希函数，这里我们将使用简单的取模运算符 % 来计算哈希值。以下是完整的实现：
class ExtensibleHashTable:
def __init__(self, capacity=16, load_factor=1.5):
self._capacity = capacity
self._load_factor = load_factor
self._buckets = [LinkedList() for _ in range(capacity)]
self._size = 0
def _resize(self):
new_capacity = self._capacity * 2
new_buckets = [LinkedList() for _ in range(new_capacity)]
for bucket in self._buckets:
current = bucket.get_head().next
while current is not bucket.get_head():
key, value = current.data()
index = self._hash_function(key, new_capacity)
new_buckets[index].add((key, value))
current = current.next
self._buckets = new_buckets
self._capacity = new_capacity
def _hash_function(self, key, capacity=None):
if capacity is None:
capacity = self._capacity
return hash(key) % capacity
def is_empty(self):
return self._size == 0
def __contains__(self, key):
return self.get(key) is not None
def __getitem__(self, key):
index = self._hash_function(key)
bucket = self._buckets[index]
if not bucket:
raise KeyError(f"KeyError: '{key}'")
current = bucket.get_head().next
while current is not bucket.get_head():
if current.data()[0] == key:
return current.data()[-1]
current = current.next
raise KeyError(f"KeyError: '{key}'")
def __setitem__(self, key, value):
index = self._hash_function(key)
if self._size >= self._load_factor * self._capacity:
self._resize()
bucket = self._buckets[index]
if not bucket:
bucket.add((key, value))
else:
current = bucket.get_head().next
while current is not bucket.get_head():
if current.data()[0] == key:
current.data()[-1] = value
return
current = current.next
bucket.add((key, value))
self._size += 1
def find_bucket(self, key):
index = self._hash_function(key)
return self._buckets[index]
def __iter__(self):
for bucket in self._buckets:
current = bucket.get_head().next
while current is not bucket.get_head():
yield current.data()[0]
current = current.next
def values(self):
for bucket in self._buckets:
current = bucket.get_head().next
while current is not bucket.get_head():
yield current.data()[-1]
current = current.next
def items(self):
for bucket in self._buckets:
current = bucket.get_head().next
while current is not bucket.get_head():
yield current.data()
current = current.next
def remove(self, key, defaultvalue=None):
index = self._hash_function(key)
bucket = self._buckets[index]
if not bucket:
if defaultvalue is None:
raise KeyError(f"KeyError: '{key}'")
else:
return defaultvalue
current = bucket.get_head().next
prev = bucket.get_head()
removed = False
while current is not bucket.get_head():
if current.data()[0] == key:
removed = True
prev.next = current.next
current.next.prior = prev
self._size -= 1
break
prev = current
current = current.next
if removed:
return current.data()[-1]
elif defaultvalue is None:
raise KeyError(f"KeyError: '{key}'")
else:
return defaultvalue
def get(self, key, defaultvalue=None):
try:
return self[key]
except KeyError:
if defaultvalue is None:
raise
else:
return defaultvalue
def size(self):
return self._size
这个实现中，我们使用了LinkedList类来存储每个桶中的节点，并实现了所有的指定方法。注意，这里的哈希函数非常简单，实际应用中可能需要更复杂的哈希函数以减少冲突。
