拉链法解决哈希冲突代码
时间: 2023-09-30 20:09:00 浏览: 32
拉链法是一种哈希表中解决哈希冲突的方法,它通过在哈希表中每个桶的位置上维护一个链表,将哈希到同一位置的元素都存储在该链表上。当需要查找某个元素时,首先计算该元素的哈希值,然后在对应的桶中查找与该元素哈希值相同的元素,如果该元素存在,则返回其对应的值;否则,返回不存在的信息。
以下是使用拉链法解决哈希冲突的代码示例:
```python
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
class HashMap:
def __init__(self, capacity=1000):
self.capacity = capacity
self.table = [None] * capacity
def put(self, key, value):
index = hash(key) % self.capacity
if self.table[index] is None:
self.table[index] = Node(key, value)
else:
p = self.table[index]
while p.next is not None:
if p.key == key:
p.val = value
return
p = p.next
if p.key == key:
p.val = value
else:
p.next = Node(key, value)
def get(self, key):
index = hash(key) % self.capacity
p = self.table[index]
while p is not None:
if p.key == key:
return p.val
p = p.next
return None
```
在上面的代码中,我们定义了一个 `Node` 类来表示链表节点,它包含一个键值对和指向下一个节点的指针。我们还定义了一个 `HashMap` 类来表示哈希表,它包含一个固定大小的数组 `table`,每个元素都是一个链表的头节点。在插入元素时,我们首先计算出元素的哈希值,并将其存储到对应的桶中。如果该桶为空,则直接插入元素;否则,遍历链表,查找与该元素键相同的节点,如果找到,则更新其值;否则,在链表末尾插入新的节点。在查找元素时,我们首先计算出元素的哈希值,并在对应的桶中查找与该元素键相同的节点,如果找到,则返回其值;否则,返回 `None`。
阅读全文