详解Python字典的底层原理——哈希表(Python面试必备)_python中字典的底层实现原理-程序员宅基地

技术标签：高效查询 Python原理字典 Python 原理

详解Python字典的底层原理——哈希表(Python面试必备)

作者：Loren no hurry
2019-06-9

Python面试经常会被问到：

你能说一说Python字典的底层实现原理吗？

这个问题可以从三个方面来回答：

1.python字典及其特性

字典是Python的一种可变、无序容器数据结构，它的元素以键值对的形式存在，键值唯一，它的特点搜索速度很快：数据量增加10000倍，搜索时间增加不到2倍；当数据量很大的时候，字典的搜索速度要比列表快成百上千倍¹。

2.哈希表

Python字典的底层实现是哈希表。什么是哈希表，简单来说就是一张带索引和存储空间的表，对于任意可哈希对象，通过哈希索引的计算公式：hash(hashable)%k（对可哈希对象进行哈希计算，然后对结果进行取余运算），可将该对象映射为0到k-1之间的某个表索引，然后在该索引所对应的空间进行变量的存储/读取等操。

哈希运算结果	取余运算结果	索引	键值对
hash(‘小王’)=2360347816510736229	2360347816510736229%3=0	0	’小王‘：26
hash(‘大熊’)=4284897975392025871	4284897975392025871%3=1	1	‘大熊’：28
hash(‘牛牛’)=-7069010861127204901	-7069010861127204901%3=2	2	‘牛牛’：3

3.Python字典如何运用哈希表

我们通过描述插入，查询，删除，扩容，哈希碰撞这几个过程来解释这一切。

插入：

对键进行哈希和取余运算，得到一个哈希表的索引，如果该索引所对应的表地址空间为空，将键值对存入该地址空间；

更新：

对键进行哈希和取余运算，得到一个哈希表的索引，如果该索引所对应的地址空间中健与要更新的健一致，那么就更新该健所对应的值；

查询：

对要查找的健进行哈希和取余运算，得到一个哈希表的索引，如果该索引所对应的地址空间中健与要查询的健一致，那么就将该键值对取出来；

扩容：

字典初始化的时候，会对应初始化一个有k个空间的表，等空间不够用的时候，系统就会自动扩容，这时候会对已经存在的键值对重新进行哈希取余运算（重新进行插入操作）保存到其它位置；

碰撞：

有时候对于不同的键，经过哈希取余运算之后，得到的索引值一样，这时候怎么办？这时采用公开寻址的方式，运用固定的模式将键值对插入到其它的地址空间，比如线性寻址：如果第i个位置已经被使用，我们就看看第i+1个，第i+2个，第i+3个有没有被使用…直到找到一个空间或者对空间进行扩容。²

比如：我们想存储 {’小小‘：18}这个键值对，经过哈希和取余运算之后，我们发现，其对应的索引值是0，但是0所指向的空间已经被’小王‘占用了，这就是碰撞。怎么办呢？我们看看0+1对应的所以有没有被占用，如果没有，我们就把’小小‘放在索引1所对应的地址空间中。取的时候，也按照同样的规则，进行探查。

哈希运算	取余运算	索引值	键值对
hash(‘小王’)=2360347816510736229	2360347816510736229%3=0	0	’小王‘：26
hash(‘小小’)=-2310146166101152587	-2310146166101152587%3=0	1	’小小‘：18
		2

为啥字典比列表查找高效

假设有一栋楼，住着1000人，你有个好朋友小王，住在这栋楼，你有急事要找他，你不知道他住几楼几号房间。这时你怎么办？你找到门卫处，向门卫说，我找小王。

列表的方法：

门卫说：我们这里每一个房间住着谁都有记录，这是记录本，你自己找吧！这个记录本有1000条记录，你从第一条开始翻，一条一条往下看，终于在第177条记录的时候找到了你的朋友小王所在的房间号。

字典的方法

门卫说: 我这里有一个公式，只要你记得你的朋友的名字，就能很快的找到你朋友在几号房间。

这个公式是：hash(姓名)%1001

对你的朋友小王的名字进行hash运算，然后对得到的结果对1001进行取余操作，得到的数字就是你的朋友小王的房间号了，经过计算，你发现hash(‘小王’)%1001=177。

总结：

列表查找是按顺序一个一个遍历，当列表越大，查找所用的时间就越久

字典是通过键值直接计算得到对应的地址空间，查找一步到位

注意

1、Cython 中哈希表的计算公式为：hash(‘hashable’)&k，其中k 为2的n次方减1，其实与hash(‘hashable’)%(k+1)的结果一致。

2、解决碰撞的方法，Python用的不是线性寻址，而是一种更为复杂的寻址模式。²

参考文献

Ramalho L. Fluent Python[M]. 2015,pp.63-93 ︎
Oram A, Wilson G. Beautiful code[M]. 2007,pp. 293–301. ︎ ︎

本文链接：https://blog.csdn.net/qq_42815145/article/details/91353624

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

元素选择器之排除特定元素_input排他选择器-程序员宅基地

文章浏览阅读2.1k次。需求如下:该搜索框是对整个页面的input检索，但与弹出层中的input冲突博主几经辗转简单处理解决问题，思路如下：排除掉特定class的input。代码如下：$('input:not(.pop)', this.footer()).on('keyup change', function () { if (that.search() !== th..._input排他选择器

使用JAXB进行XML与JavaBean的转换（支持泛型）_jaxb 泛型-程序员宅基地

文章浏览阅读5.6k次，点赞6次，收藏20次。看到别人有个1024的勋章，特意留了一篇在今年的10.24日，看看会不会获得。在日常开发中可能涉及接口之间的相互调用，虽然在现在微服务的理念推广下，很多公司都采用轻量级的JSON格式做为序列化的格式，但是不乏有些公司还是有一些XML格式的报文，最近就在对接某个合作方的时候遇到了XML报文。在JSON报文爽快的转换下很难试用一个一个的拿报文参数，还是希望能直接将报文转换成Bean。接下来就了解到..._jaxb 泛型

python numpy学习笔记_ndarray的位置-程序员宅基地

文章浏览阅读1.2k次。numpy的主要数据对象是多维数组，其中包含相同类型的元素，通常是数字类型，每个元素都有一个索引。使用numpy前通常要导入包。import numpy as np目录类型维度创建运算索引和切片类型numpy的数组被称为ndarray。numpy.array只处理一维数组，而ndarray对象才提供更多功能。a = np.array([[1, 2, 3], [4, 5, 6]])type(a) # <class 'numpy.ndarray'>dtype属性可以获得元素的数_ndarray的位置

我的世界java版gamemode指令_《我的世界》Java版常用指令代码大全！你想要的都在这里了！...-程序员宅基地

文章浏览阅读1.6w次。还在苦于网上找到的一些指令已经不适用了吗？还在苦于有些地方的指令有误吗？还在苦于有些地方整理的指令不够全面吗？那么你来对地方了！小编为大家整理了《我的世界》原版游戏常用的指令，这些基本足以满足各位的基本需求了！大家来一起看看吧！注：表示的是必须输入的部分，[方括号]表示的是可选择性输入的部分基本命令列表命令描述/?/help的替代命令，提供命令使用帮助。/ban + 玩家名字将玩家加入封禁列表。/..._gamemode指令java

Spring Boot 结合shiro做第三方登录验证_shiro 第三方token登录-程序员宅基地

文章浏览阅读1.5w次，点赞3次，收藏3次。Spring Boot 结合shiro做第三方登录验证1、首先，说一下我的具体实现思路。在做spring boot拦截器的过程中，开始我准备用spring security来实现，但是研究了一段时间之后发现spring security的集成度太高，需要修改的东西比较多，而且对它本身的使用方法不是很了解，后来转而使用Apache shiro。由于是第三方登录，是不需要我来验证密码的。最开始，我陷入了_shiro 第三方token登录

labelme UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0xaf in position 227: illegal mult_file "c:\rgzn\labelme-main\setup.py", line 91, in -程序员宅基地

文章浏览阅读1.9k次，点赞4次，收藏4次。[INFO ] __init__:get_config:71 - Loading config file from:C:\Users\xxx\.labelmercTraceback (most recent call last): File .... line 191, in <module> main() File ...., line 145, in main config = get_config(config_file_or_yaml, config_fro_file "c:\rgzn\labelme-main\setup.py", line 91, in main if sys.argv[1] == "re