碰撞问题及其解决方法

7.1 哈希表中的碰撞定义

哈希表中的碰撞发生在两个不同的键哈希到数组中的同一个索引时。这导致多个元素尝试占用哈希表中的同一单元。

碰撞例子：

假设我们有一个简单的哈希函数，它返回键除以表大小的余数。对于键5和15，当表大小为10时，两个键都会得到相同的索引：5 % 10 = 5 和 15 % 10 = 5。这就是碰撞。

另一个例子：

假如你在编写一个名字的字典，而你的简单哈希函数返回名字的首字母。但80%的名字都以字母“A”开头。这不仅是碰撞，这还算个问题。

7.2 解决碰撞的方法 – 链表法

解决哈希表碰撞的方法有几种。最常见的两种方法是链表法（chaining）和开放寻址法（open addressing）。

链表法 (Chaining)

优点：

• 实现简单。
• 在少量碰撞时效率高。
• 对哈希表填充密度的依赖较小。

缺点：

• 需要额外的内存来存储链表中的指针。
• 在大量碰撞时性能会下降，因为链表变长。

链表法实现示例：

你可以只研究insert函数的工作原理，但我决定提供完整的代码以方便使用。

class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# 使用示例:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 输出: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # 输出: None

7.3 第二种方法 – 开放寻址

开放寻址方法是在发生碰撞时在数组中寻找下一个可用单元。寻找新单元的方法有多种策略：线性探测、平方探测和双重哈希。

优点：

• 不需要额外的内存来存储指针。
• 更紧凑的数据表示。

缺点：

• 当表填充密度高时性能会显著下降。
• 需要更多计算资源来解决碰撞。

开放寻址策略示例

线性探测 (Linear Probing)：

• 步长为1的探测：index = (index + 1) % size。
• 简单，但可能导致“聚簇化”。

平方探测 (Quadratic Probing)：

• 步长按平方增加的探测：index = (index + i^2) % size。
• 减少了聚簇化问题，但实现复杂。

双重哈希 (Double Hashing)：

• 使用第二个哈希函数计算步长：index = (index + i * hash2(key)) % size。
• 聚簇化问题较少，但实现复杂。

开放寻址法实现示例（线性探测）：我会提供完整的代码，为了简单可以只研究insert函数的工作原理。

class HashTableOpenAddressing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

# 使用示例:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 输出: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # 输出: None

7.4 碰撞对哈希表的影响

碰撞对性能的影响。

平均访问时间：

• 在理想条件下（无碰撞），哈希表中元素的平均访问时间是O(1)。
• 碰撞增加了访问时间，因为需要处理链表或探测单元，增加了操作数量。

链表长度增加：

• 在链表法中，链表长度的增加会使大量碰撞导致线性访问时间 O(n) 用于搜索、插入和删除操作。
• 长链表增加了搜索或插入元素所需的比较次数。

空间复杂度：

• 链表法需要额外的内存来存储链表中的指针。
• 在开放寻址法中，表的填充超过一定水平（通常约70-80%）会显著增加碰撞次数，进而增加访问时间。

聚簇化：在开放寻址法中（特别是在线性探测中），聚簇化发生于连续的单元被占用，增加了碰撞的概率并影响性能。

碰撞对性能影响的分析示例：

喜欢深挖的朋友可以试试

import time
import random

# 线性探测
class HashTableOpenAddressing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

# 生成大量数据进行插入
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# 插入数据并测量时间
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"插入时间: {time.time() - start_time:.6f} 秒")

# 搜索数据并测量时间
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"搜索时间: {time.time() - start_time:.6f} 秒")