数据结构-哈希表

哈希表是一种高效的数据结构，它可以提供快速的插入、删除和查找操作。哈希表的基本思想是将键通过一个哈希函数映射到一个连续的地址空间上，然后在这个地址空间上进行查找、插入和删除操作。下面将详细介绍哈希表的相关概念和实现方法。

哈希函数

哈希函数是哈希表的核心，它将键映射到哈希表的索引上。一个理想的哈希函数应该易于计算，并且能够将不同的键均匀地分布到哈希表中。哈希函数的设计取决于键的类型和哈希表的大小。常见的哈希函数包括：

• 直接寻址法：对于整型键，可以直接使用键本身或者键与一个常数相乘的结果作为哈希值。
• 除留余数法：将键除以哈希表的大小，并取余数作为哈希值。
• 多项式累积法：对于字符串类型的键，可以将字符串视为一个多项式，并通过特定的算法计算其哈希值。

冲突解决

由于哈希函数将键映射到一个有限的地址空间上，因此可能会出现两个或多个键映射到同一个地址上的情况，这种情况称为冲突。解决冲突的方法主要有两种：

• 链地址法：每个哈希桶维护一个链表，当冲突发生时，将键值对添加到对应桶的链表中。查找、插入和删除操作需要遍历链表。
• 开放地址法：当冲突发生时，通过一个探测序列找到下一个空闲的哈希桶，并将键值对存储在那里。常见的探测方法包括线性探测、二次探测和双重哈希等。

负载因子和动态扩展

负载因子是哈希表中已存储的键值对数量与哈希表大小的比值。当负载因子超过某个阈值时，哈希表的性能会下降，因此需要动态扩展哈希表。动态扩展通常包括创建一个更大的新表，然后将所有现有的键值对重新插入到新表中。

哈希表的操作

• 查找：给定一个键，通过哈希函数计算其哈希值，然后根据冲突解决策略在对应的哈希桶中查找键值对。
• 插入：给定一个键值对，通过哈希函数计算键的哈希值，然后将键值对插入到对应的哈希桶中。如果发生冲突，根据冲突解决策略处理。
• 删除：给定一个键，通过哈希函数计算其哈希值，然后根据冲突解决策略在对应的哈希桶中删除键值对。
  哈希表的时间复杂度取决于哈希函数的设计和冲突解决策略。在理想情况下，哈希表的查找、插入和删除操作的时间复杂度可以达到O(1)。然而，当冲突频繁发生时，这些操作的时间复杂度可能会退化。因此，哈希表的设计和实现需要仔细考虑哈希函数的选择、冲突解决策略以及负载因子的设置，以确保哈希表能够提供高效的性能。

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        for kvp in self.table[index]:
            if kvp[0] == key:
                kvp[1] = value
                return
        self.table[index].append([key, value])

    def search(self, key):
        index = self.hash_function(key)
        for kvp in self.table[index]:
            if kvp[0] == key:
                return kvp[1]
        return None

    def delete(self, key):
        index = self.hash_function(key)
        for i, kvp in enumerate(self.table[index]):
            if kvp[0] == key:
                del self.table[index][i]
                return