拉链法解决哈希冲突代码

拉链法是一种哈希表中解决哈希冲突的方法，它通过在哈希表中每个桶的位置上维护一个链表，将哈希到同一位置的元素都存储在该链表上。当需要查找某个元素时，首先计算该元素的哈希值，然后在对应的桶中查找与该元素哈希值相同的元素，如果该元素存在，则返回其对应的值；否则，返回不存在的信息。

以下是使用拉链法解决哈希冲突的代码示例：

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`。