发布于 由admin

Python高级技术之：`Python`的哈希算法：`dict`和`set`的内部实现与哈希冲突的解决策略。

各位观众，晚上好！很高兴今晚能跟大家一起聊聊Python里一个既重要又有点神秘的话题：哈希算法，特别是它在dict（字典）和set（集合）中的应用，以及我们如何应对哈希冲突这个小麻烦。

咱们都知道，dict和set是Python里非常常用的数据结构，它们查找元素的速度非常快，基本上可以认为是O(1)的时间复杂度。但你知道这背后是什么在默默支撑吗？没错，就是哈希算法。

一、什么是哈希？Hash是个啥？

首先，咱得明白啥叫哈希。简单来说，哈希就像一个“指纹提取器”，它可以把任何大小的数据（比如字符串、数字、甚至一个复杂的对象）转换成一个固定大小的整数，这个整数就是哈希值。这个过程就叫做哈希。

想象一下，你去图书馆借书，图书馆的书都是按照编号排列的，这个编号就相当于哈希值。图书管理员（也就是哈希函数）拿到书名（也就是你的数据），经过一番计算（也就是哈希算法），得到一个编号，然后就可以快速找到这本书的位置。

二、哈希函数：算法界的月老

哈希函数是哈希算法的核心。一个好的哈希函数应该具备以下特点：

  1. 一致性：对于相同的输入，每次都应该产生相同的哈希值。这就像月老给一对男女牵线，不能今天说他们合适，明天又说他们不合适。
  2. 高效性：计算哈希值的速度要快。毕竟，咱们用dict和set就是图个快，要是哈希函数计算得慢吞吞的，那就没意义了。
  3. 均匀性：尽可能地将不同的输入均匀地映射到不同的哈希值。这就像月老给很多人牵线，不能总是把人往同一个对象上牵，要雨露均沾。

Python自带的hash()函数就是一种常用的哈希函数。它适用于大多数内置类型，比如整数、浮点数、字符串、元组等等。

print(hash("hello"))  # 输出一个整数
print(hash(123))      # 输出一个整数
print(hash((1, 2, 3))) # 输出一个整数

三、dict的内部实现：哈希表的秘密

dict的底层实现是哈希表（Hash Table）。哈希表是一个数组，数组的每个元素被称为桶（Bucket）。每个桶可以存储一个键值对。

当我们向dict中添加一个键值对时，Python会首先使用哈希函数计算键的哈希值。然后，将哈希值对哈希表的大小取模，得到一个索引，这个索引就是键值对应该存储在哪个桶的位置。

my_dict = {"name": "Alice", "age": 30, "city": "New York"}
#  当添加 "name": "Alice" 时：
#  1. 计算 "name" 的哈希值：hash("name")  假设结果是 12345
#  2. 假设哈希表的大小是 16，则计算索引：12345 % 16 = 9
#  3. 将 ("name", "Alice") 存储到哈希表的第 9 个桶中

当我们查找一个键时，Python也会首先计算键的哈希值，然后找到对应的桶，最后在桶中查找键值对。

四、set的内部实现：dict的马甲

set的内部实现其实很简单，它本质上就是一个dict，只不过set只存储键，不存储值。可以将set看作是一个所有值都为None的dict。

当我们向set中添加一个元素时，Python会计算元素的哈希值，然后将元素存储到对应的桶中。

当我们查找一个元素时，Python也会计算元素的哈希值，然后找到对应的桶，最后在桶中查找元素。

五、哈希冲突：月老也会犯错

理想情况下，每个键都应该被映射到不同的桶中。但现实往往很残酷，不同的键可能会产生相同的哈希值，或者哈希值取模后得到相同的索引，这就是哈希冲突。

# 假设哈希表大小为 10
# 键 "A" 的哈希值 % 10 = 5
# 键 "B" 的哈希值 % 10 = 5  (发生了冲突)

哈希冲突是不可避免的，因为哈希函数的输出空间通常比输入空间小得多。就像世界上有几十亿人，但只有几百种指纹一样，总会有人指纹相似。

六、解决哈希冲突的策略：月老补救措施

解决哈希冲突的方法有很多，常见的有以下几种：

  1. 开放寻址法（Open Addressing）：如果发生冲突，就按照某种规则寻找下一个空闲的桶。常见的开放寻址法有线性探测、二次探测、双重哈希等。

    • 线性探测：如果当前桶被占用，就检查下一个桶，如果还是被占用，就继续检查下一个桶，直到找到一个空闲的桶为止。就像排队买票，如果前面的人挡住了你，你就往后挪一位。

      # 假设哈希表大小为 10，键 "A" 和 "B" 都被哈希到索引 5
# "A" 先插入到索引 5
# "B" 插入时发现索引 5 被占用，使用线性探测，检查索引 6，如果空闲，则插入到索引 6，否则继续探测

    • 二次探测：如果当前桶被占用，就按照 i^2 的步长寻找下一个桶，其中 i 是冲突的次数。

      # 假设哈希表大小为 10，键 "A" 和 "B" 都被哈希到索引 5
# "A" 先插入到索引 5
# "B" 插入时发现索引 5 被占用，使用二次探测：
#   第一次探测：(5 + 1^2) % 10 = 6
#   第二次探测：(5 + 2^2) % 10 = 9
#   第三次探测：(5 + 3^2) % 10 = 4
#   ...

    • 双重哈希：使用两个哈希函数，如果第一个哈希函数发生冲突，就使用第二个哈希函数计算新的哈希值，然后找到对应的桶。

  2. 链地址法（Separate Chaining）：每个桶都存储一个链表，如果发生冲突，就将新的键值对添加到链表的末尾。就像图书馆里，每个书架上都挂着一个链子，链子上可以挂很多本书。

    # 假设哈希表大小为 10，键 "A" 和 "B" 都被哈希到索引 5
# 索引 5 的桶存储一个链表，链表中存储了 ("A", value_A) 和 ("B", value_B)

Python的dict和set采用的是开放寻址法，具体来说是探测链（probing sequence）的一种变体。Python的哈希表会动态调整大小，当哈希表中的元素数量超过一定比例（负载因子，load factor）时，就会自动扩容，以减少哈希冲突的概率。

七、dict和set的性能分析：速度与激情

正是因为哈希算法的存在，dict和set才拥有了近乎O(1)的查找速度。无论dict或set中有多少元素，查找一个元素的时间几乎是恒定的。

当然，这只是理想情况。在哈希冲突严重的情况下，查找速度会下降。但Python的哈希表实现经过了精心的优化，即使在最坏的情况下，也能保证较好的性能。

下面是一些简单的性能测试，可以让你更直观地感受到dict和set的速度：

import time

# 创建一个包含 100 万个元素的列表
my_list = list(range(1000000))

# 创建一个包含 100 万个元素的集合
my_set = set(range(1000000))

# 创建一个包含 100 万个元素的字典
my_dict = {i: i for i in range(1000000)}

# 测试列表的查找速度
start_time = time.time()
for i in range(1000):
    if 500000 in my_list:
        pass
end_time = time.time()
print(f"List search time: {end_time - start_time}")

# 测试集合的查找速度
start_time = time.time()
for i in range(1000):
    if 500000 in my_set:
        pass
end_time = time.time()
print(f"Set search time: {end_time - start_time}")

# 测试字典的查找速度
start_time = time.time()
for i in range(1000):
    if 500000 in my_dict:
        pass
end_time = time.time()
print(f"Dict search time: {end_time - start_time}")

运行结果会发现，set和dict的查找速度明显快于list。

八、自定义哈希函数：打造专属指纹

对于自定义的类，如果你想让它们能够作为dict的键或者set的元素，你需要实现__hash__()方法和__eq__()方法。

  • __hash__()方法用于计算对象的哈希值。
  • __eq__()方法用于判断两个对象是否相等。

注意：如果两个对象相等，它们的哈希值必须相等。

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __eq__(self, other):
        if isinstance(other, Person):
            return self.name == other.name and self.age == other.age
        return False

    def __hash__(self):
        return hash((self.name, self.age))

person1 = Person("Alice", 30)
person2 = Person("Alice", 30)
person3 = Person("Bob", 25)

print(person1 == person2)  # True
print(person1 == person3)  # False
print(hash(person1) == hash(person2)) # True
print(hash(person1) == hash(person3)) # False

my_set = {person1, person2, person3}
print(len(my_set))  # 2  (person1 和 person2 被认为是同一个元素)

九、哈希算法的应用：无处不在的指纹

除了dict和set，哈希算法在计算机科学中还有很多其他的应用，比如：

  • 数据校验：可以使用哈希算法来校验数据的完整性。如果数据被篡改，哈希值就会发生变化。
  • 密码存储：可以使用哈希算法来存储密码。存储密码的哈希值而不是明文密码，可以提高安全性。
  • 负载均衡：可以使用哈希算法将请求均匀地分配到不同的服务器上。
  • 数据结构：哈希算法可以用于实现各种数据结构，比如哈希表、布隆过滤器等等。

十、总结：哈希的魅力

哈希算法是一种非常重要的算法，它在计算机科学中有着广泛的应用。dict和set是Python中非常常用的数据结构，它们之所以能够拥有近乎O(1)的查找速度，正是因为哈希算法的存在。

希望今天的讲座能够让你对哈希算法有一个更深入的了解。下次当你使用dict或set的时候，不妨想想它们背后的哈希算法，感受一下哈希的魅力。

最后，用一句幽默的话来结束今天的讲座：哈希就像月老，虽然有时候会犯错，但总能帮你找到对的人（或数据）。谢谢大家！

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注