聊一聊喜闻乐见的哈希表

简介: 聊一聊喜闻乐见的哈希表


楔子


Python 的字典是一种映射型容器对象,保存了键(key)值(value)的映射关系。通过字典,我们可以实现快速查找,JSON 这种数据结构也是借鉴了 Python 的字典。另外字典是经过高度优化的,因为 Python 底层也在大量地使用字典。

在 Python 里面我们要如何创建一个字典呢?

# 创建一个字典
d = {"a": 1, "b": 2}
print(d)  # {'a': 1, 'b': 2}
# 或者我们还可以调用 dict,传入关键字参数即可
d = dict(a=1, b=2, c=3, d=4)
print(d)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# 当然 dict 里面还可以接收位置参数,但是最多接收一个
d1 = dict({"a": 1, "b": 2}, c=3, d=4)
d2 = dict([("a", 1), ("b", 2)], c=3, d=4)
print(d1)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
print(d2)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# 还可以根据已有字典创建新的字典
d = {**{"a": 1, "b": 2}, "c": 3, **{"d": 4}}
print(d)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# 当然通过调用 dict 也是可以的
# 但是注意:** 这种方式本质上是把字典变成多个关键字参数
# 所以里面的 key 一定要符合 Python 的变量命名规范
d = dict(**{"a": 1, "b": 2}, c=3, **{"d": 4})
print(d)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
try:
    # 这种是不合法的,因为 **{1: 1} 等价于 1=1
    d = dict(**{1: 1})
except Exception as e:
    print(e)  # keywords must be strings
# 但下面是合法的
d = {**{1: 1, 2: 2}}
print(d)  # {1: 1, 2: 2}

字典的底层是借助哈希表实现的,关于哈希表我们一会儿说,总之字典添加元素、删除元素、查找元素等操作的平均时间复杂度是 O(1)。


我们来测试一下字典的执行效率吧,看看它和列表之间的区别。

import time
import numpy as np
def test(count: int, value: int):
    """
    :param count: 循环次数
    :param value: 查询的元素
    :return:
    """
    # 包含一千个随机数的列表
    lst = list(np.random.randint(0, 2 ** 30, size=1000))
    # 基于列表构建一个字典
    d = dict.fromkeys(lst)
    # 查询元素 value 是否在列表中,循环 count 次,并统计时间
    t1 = time.perf_counter()
    for _ in range(count):
        value in lst
    t2 = time.perf_counter()
    print("列表查询耗时:", round(t2 - t1, 2))
    # 查询元素 value 是否在字典中,循环 count 次,并统计时间
    t1 = time.perf_counter()
    for _ in range(count):
        value in d
    t2 = time.perf_counter()
    print("字典查询耗时:", round(t2 - t1, 2))
# 分别查询一千次、一万次、十万次、二十万次
test(10 ** 3, 22333)
"""
列表查询耗时: 0.13
字典查询耗时: 0.0
"""
test(10 ** 4, 22333)
"""
列表查询耗时: 1.22
字典查询耗时: 0.0
"""
test(10 ** 5, 22333)
"""
列表查询耗时: 12.68
字典查询耗时: 0.01
"""
test(10 ** 5 * 2, 22333)
"""
列表查询耗时: 25.72
字典查询耗时: 0.01
"""

字典的查询速度非常快,从测试中我们看到,随着循环次数越来越多,列表所花费的总时间越来越长。但是字典由于查询所花费的时间极少,查询速度非常快,所以即便循环 50 万次,花费的总时间也不过才 0.01 秒左右。

此外字典还有一个特点,就是它的不会受到数据量的影响,从含有一万个键值对的字典中查找,和从含有一千万个键值对的字典中查找,两者花费的时间几乎是没有区别的。

那么哈希表到底是什么样的数据结构,为什么能这么快呢?下面来分析一下。


什么是哈希表


映射型容器的使用场景非常广泛,基本上所有的主流语言都支持。例如 C++ 里面的 map 就是一种映射型容器,但它是基于红黑树实现的。红黑树是一种平衡二叉树,元素的插入、删除、查询等操作的时间复杂度均为 O(logN),另外 Linux 的 epoll 也使用了红黑树。

而对于 Python 来讲,映射型容器指的就是字典,我们说字典在 Python 内部是被高度优化的。因为不光我们在用,虚拟机在运行时也在大量使用,比如类对象、自定义类的实例对象都有自己的属性字典,还有全局变量也是通过字典存储的。因此基于以上种种原因,Python 对字典的性能要求会更加苛刻。

所以 Python 字典采用的数据结构,在添加、删除、查询元素等方面肯定是要优于红黑树的,没错,就是哈希表。其原理是将 key 通过哈希函数进行运算,得到一个哈希值,再将这个哈希值映射成索引。

我们举例说明:

ba3a27674a440e33b5c0e5222182bf1c.png

我们发现除了 key、value 之外,还有一个 index,因为哈希表本质上也是使用了索引。虽然数组在遍历的时候是个时间复杂度为 O(n) 的操作,但通过索引定位元素则是一个 O(1) 的操作,不管数组有多长,通过索引总是能瞬间定位到指定元素。

所以哈希表本质上就是一个数组,通过将 key 映射成一个数值,作为数组的索引,然后将键值对存在数组里面。至于它是怎么映射的,我们后面再谈,现在就假设是按照我们接下来说的方法映射的。

比如这里有一个能容纳 8 个元素的字典,如上图所示。我们先设置 d["koishi"]=79,那么会对 "koishi" 这个字符串进行哈希运算,得到一个哈希值,然后再让哈希值对当前的总容量进行取模,这样的话是不是能够得到一个小于 8 的数呢?假设是 3,那么就存在索引为 3 的位置。

然后 d["scarlet"]=95,按照同样的规则运算得到 6,那么就存在索引为 6 的位置;同理第三次设置 d["satori"]=80,对字符串 satori 进行哈希、取模,得到 1,那么存储在索引为 1 的位置。

同理当我们根据键来获取值的时候,比如:d["satori"],那么同样会对字符串 "satori" 进行哈希、取模,得到索引发现是1,然后就把索引为 1 的 value 给取出来。

当然这种方式肯定存在缺陷,比如:

  • 不同的 key 进行哈希、取模运算之后得到的结果一定是不同的吗?
  • 在运算之后得到索引的时候,发现这个位置已经有人占了怎么办?
  • 取值的时候,索引为 1,可如果索引为 1 对应的 key 和我们指定的 key 不一致怎么办?

所以哈希运算是会冲突的,如果冲突,那么 Python 底层会改变策略重新映射,直到映射出来的索引没有人用。比如我们设置一个新的键值对 d["tomoyo"]=88,可是 "tomoyo" 这个 key 映射之后得到的结果也是 1,而索引为 1 的地方已经被 key 为 "satori" 的键值对给占了,那么 Python 就会改变规则来对 "tomoyo" 重新映射,直到找到一个空位置。

但如果我们再次设置 d["satori"]=100,那么对 satori 映射得到的结果也是 1,而 key 是一致的,那么就会把对应的值进行修改。

同理,当我们获取值的时候,比如 d["tomoyo"],那么对 key 进行映射,得到索引。但是发现该索引对应的 key 不是 "tomoyo" 而是 "satori",于是改变规则(这个规则跟设置 key 冲突时,采用的规则是一样的),重新映射,得到新的索引,然后发现 key 是一致的,于是将值取出来。

所以从这里就已经能说明问题了,就是把 key 转换成数组的索引。可能有人问,这些键值对貌似不是连续的啊。对的,肯定不是连续的。并不是说你先存,你的索引就小、就在前面,这是由 key 进行哈希运算之后的结果决定的。

另外哈希表、或者说字典也会扩容,并且它还不是像列表那样,容量不够才扩容,而是当键值对个数达到容量的三分之二的时候就会扩容。

因为字典不可能会像列表那样,键值对之间是连续、一个一个挨在一起的。既然是哈希运算,得到的哈希值肯定是随机的,再根据哈希值映射出的索引也是随机的。那么在键值对个数达到容量三分之二的时候,计算出来的索引发生碰撞的概率会非常大,不可能等到容量不够了再去扩容,而是在键值对个数达到容量的三分之二时就要扩容,也就是申请一个更大的哈希表。

一句话总结:哈希表就是一种空间换时间的方法。

假设容量为 1024,那么就相当于数组有 1024 个位置,每个 key 都会映射成索引,找到自己的位置,将键值对存在里面。但很明显各自的位置是不固定的,肯定会空出来很多,但是无所谓,只要保证通过索引能在相应的位置找到它即可。

大量的文字会有些枯燥,我们用两张图来解释一下设置元和获取元素的整个过程。

dfe577eb8bf7cddbe15585e22b729336.png

以上是设置元素,还是比较清晰的,果然图像是个好东西。再来看看获取元素:

2abb2df803ffbcbd6f9097023ce23c22.png

以上就是哈希表的基本原理,说白了它就是个数组。存储键值对的时候,先将 key 映射成索引,然后基于索引找到数组中的指定位置,将键值对存进去。


小结


目前介绍的正是 Python 早期所采用的哈希表,但是它有一个严重的问题,就是内存浪费严重。下一篇文章我们就来看看字典的底层结构,以及 Python 是如何对哈希表进行优化的。

相关文章
|
算法
带你读《图解算法小抄》六、哈希表(2)
带你读《图解算法小抄》六、哈希表(2)
|
29天前
|
数据安全/隐私保护 索引
第三章 哈希表
第三章 哈希表
27 1
|
6月前
|
存储 Java Serverless
从 0 到 1 读懂:哈希表
从 0 到 1 读懂:哈希表
|
6月前
|
存储 算法 Java
数据结构与算法面试题:实现一个哈希表,并考虑哈希冲突的解决方案。
数据结构与算法面试题:实现一个哈希表,并考虑哈希冲突的解决方案。
50 0
|
算法 索引
带你读《图解算法小抄》六、哈希表(1)
带你读《图解算法小抄》六、哈希表(1)
带你读《图解算法小抄》六、哈希表(1)
|
存储 缓存 算法
【C++进阶】九、哈希表
目录 一、哈希概念 二、哈希冲突 三、哈希函数 四、哈希冲突解决 4.1 闭散列(开放定址法) 4.1.1 线性探测 4.1.2 二次探测 4.1.3 研究表明 五、哈希表的闭散列实现 5.1 闭散列哈希表的结构 5.2 闭散列的插入 5.2 闭散列的查找 5.3 闭散列的查找 5.4 哈希表取模问题 5.5 string类型无法取模问题 5.6 完整代码 四、哈希冲突解决 4.2 开散列(链地址法、哈希桶) 六、哈希表的开散列实现(哈希桶) 6.1 哈希桶的结构 6.2 哈希桶的插入 6.3 哈希桶的查找 6.4 哈希桶的删除 6.5 完整代码
114 0
【C++进阶】九、哈希表
|
存储 缓存 算法
【第五天】算法图解--哈希表(散列表)Hash函数
【第五天】算法图解--哈希表(散列表)Hash函数
|
算法
算法竞赛100天第四天 —— 设计哈希表(散列表)
算法竞赛100天第四天 —— 设计哈希表(散列表)
129 0
算法竞赛100天第四天 —— 设计哈希表(散列表)
|
存储 Serverless