Python中哈希表的冲突处理方法

2023-04-11 00:00:00 python 方法 冲突

哈希表是一种基于哈希函数实现的映射数据结构，它利用哈希函数将关键字映射到一个地址上存储数据，但是由于哈希函数的性质，不同的关键字可能会映射到同一个地址上，这就造成了哈希冲突。Python中哈希表的冲突处理方法有以下几种。

  1. 链地址法

链地址法是一种解决哈希冲突的简单而有效的方法。它的思想是将哈希表中每个桶里的元素都放到一个链表中，当发生冲突时，就将新元素插入到对应桶的链表末尾即可。Python实现代码如下：

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.table = [None] * self.size

    def _hash(self, key):
        return key % self.size

    def put(self, key, value):
        index = self._hash(key)
        if not self.table[index]:
            self.table[index] = ListNode(key, value)
        else:
            head = self.table[index]
            while head:
                if head.key == key:
                    head.val = value
                    return
                if not head.next:
                    break
                head = head.next
            head.next = ListNode(key, value)

    def get(self, key):
        index = self._hash(key)
        head = self.table[index]
        while head:
            if head.key == key:
                return head.val
            head = head.next
        return -1

    def remove(self, key):
        index = self._hash(key)
        head = prev = self.table[index]
        if not head:
            return
        if head.key == key:
            self.table[index] = head.next
        else:
            head = head.next
            while head:
                if head.key == key:
                    prev.next = head.next
                    break
                head, prev = head.next, prev.next
  1. 线性探测法

线性探测法是一种将冲突的元素放到下一个空桶中的方法。如果当前桶已经被占用，就向后探测一格，直到找到一个空桶。这里需要注意的是，在使用线性探测法的时候，在插入和查找的时候需要遍历一遍哈希表，找到可用的空桶或者查找到对应的元素。Python实现代码如下：

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.table = [-1] * self.size

    def _hash(self, key):
        return key % self.size

    def put(self, key, value):
        index = self._hash(key)
        while self.table[index] != -1 and self.table[index][0] != key:
            index = (index + 1) % self.size
        self.table[index] = (key, value)

    def get(self, key):
        index = self._hash(key)
        while self.table[index] != -1:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
        return -1

    def remove(self, key):
        index = self._hash(key)
        while self.table[index] != -1:
            if self.table[index][0] == key:
                self.table[index] = -1
                return
            index = (index + 1) % self.size

无论是链地址法还是线性探测法，在实际运用中都有其适用性和局限性，需要根据具体情况进行选择。

相关文章