python hashtable拉链法删除元素
时间: 2023-10-16 13:27:38 浏览: 65
在哈希表的拉链法中,删除元素需要执行以下步骤:
1. 计算要删除元素的哈希值,找到对应的哈希桶。
2. 在哈希桶中查找要删除的元素。
3. 如果找到了要删除的元素,将该元素从链表中删除。
4. 如果链表为空,将哈希桶设置为空桶。
下面是一个示例代码:
```
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
class HashTable:
def __init__(self, capacity):
self.capacity = capacity
self.buckets = [None] * capacity
def hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
h = self.hash(key)
if not self.buckets[h]:
self.buckets[h] = Node(key, val)
else:
node = self.buckets[h]
while node.next:
if node.key == key:
node.val = val
return
node = node.next
if node.key == key:
node.val = val
return
node.next = Node(key, val)
def get(self, key):
h = self.hash(key)
node = self.buckets[h]
while node:
if node.key == key:
return node.val
node = node.next
return None
def remove(self, key):
h = self.hash(key)
node = self.buckets[h]
prev = None
while node:
if node.key == key:
if prev:
prev.next = node.next
else:
self.buckets[h] = node.next
return
prev = node
node = node.next
```
阅读全文