哈希表（Hashtable）及哈希冲突处理

简介

哈希表（Hashtable），也称为散列表，是一种常用的数据结构，用于存储键值对（key-value pairs）。它基于哈希函数（hash function）将键映射到一个固定的数组索引位置上，从而实现快速的查找、插入和删除操作。哈希表的时间复杂度通常为O(1)，在大多数情况下具有较好的性能表现。

哈希表原理

哈希表的基本原理是通过哈希函数将键映射到一个数组索引位置上。当需要插入或查找一个键值对时，先使用哈希函数计算键的哈希值，然后将哈希值映射到数组索引。通过将键存储在对应的数组索引位置上，可以快速地进行查找和访问操作。

下面是一个简单的示例代码，演示了如何使用哈希表存储和访问键值对。

class Hashtable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        
    def hash_func(self, key):
        return key % self.size
    
    def put(self, key, value):
        index = self.hash_func(key)
        self.table[index] = value
    
    def get(self, key):
        index = self.hash_func(key)
        return self.table[index]

在上面的代码中，Hashtable类实现了一个简单的哈希表，使用了取模运算作为哈希函数。size参数指定了哈希表的大小，table是一个用于存储键值对的数组。put方法用于插入键值对，get方法用于根据键获取对应的值。

哈希冲突

在哈希表中，不同的键可能会映射到相同的数组索引位置上，这就是哈希冲突（hash collision）。哈希冲突会导致键值对无法正确存储和访问，因此需要采取适当的方法来处理。

常见的处理哈希冲突的方法有两种：开放地址法（Open Addressing）和链地址法（Chaining）。

开放地址法

开放地址法是一种解决哈希冲突的方法，它尝试在数组中寻找下一个可用的位置来存储冲突的键值对。具体的方法有线性探测、二次探测和双重哈希等。

以下是使用线性探测法处理哈希冲突的示例代码：

class Hashtable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        
    def hash_func(self, key):
        return key % self.size
    
    def put(self, key, value):
        index = self.hash_func(key)
        while self.table[index] is not None:
            index = (index + 1) % self.size
        self.table[index] = value
    
    def get(self, key):
        index = self.hash_func(key)
        while self.table[index] is not None:
            if self.table[index] == key:
                return index
            index = (index + 1) % self.size
        return None

在上述代码中，当发生哈希冲突时，使用线性探测的方式找到下一个可用的位置。在插入操作中，从哈希值位置开始向后查找，直到找到一个空位置。在查找操作中，从哈希值位置开始向后查找，直到找到键对应的位置或者遇到空位置。

链地址法

链地址法是一种解决哈希冲突的方法，它使用链表来存储冲突的键值对。当发生哈希冲突时，将键值对添加到对应索引位置的链表中。

以下是使用链地址法处理哈希冲突的示例代码：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class Hashtable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        
    def hash_func(self, key):
        return key % self.size
    
    def put(self, key, value):
        index = self.hash_func(key)
        if self.table[index] is None:
            self.table[index] = Node(key, value)
        else:
            node = self.table[index]
            while node.next is not None:
                node = node.next
            node.next = Node(key, value)
    
    def get(self, key):
        index = self.hash_func(key)
        node = self.table[index]
        while node is not None:
            if node.key == key:
                return node.value
            node = node.next
        return None

在上述代码中，当发生哈希冲突时，将键值对添加到链表中。在插入操作中，如果哈希值位置为空，则直接存储键值对；否则，遍历链表直到找到空位置，然后插入键值对。在查找操作中，遍历链表查找对应的键。

示例

为了演示哈希表的使用，我们定义一个示例哈希表，并插入和查找一些键值对。

hash_table = Hashtable(10)
hash_table.put(1, "Alice")
hash_table.put(11, "Bob")
hash_table.put(21, "Charlie")
print(hash_table.get(1))  # 输出：Alice
print(hash_table.get(11))  # 输出：Bob
print(hash_table.get(21))  # 输出：Charlie

输出结果为：

Alice
Bob
Charlie

总结

哈希表是一种常用的数据结构，它通过哈希函数将键映射到一个固定的数组索引位置上，实现快速的查找、插入

和删除操作。哈希表的时间复杂度通常为O(1)，在大多数情况下具有较好的性能表现。

开放地址法通过在数组中寻找下一个可用的位置来处理哈希冲突，常见的方法有线性探测、二次探测和双重哈希等。链地址法使用链表来存储冲突的键值对，将键值对添加到对应索引位置的链表中。