Python字典底层实现原理详解
作者:answer3lin 发布时间:2021-04-09 12:58:28
在Python中,字典是通过散列表或说哈希表实现的。字典也被称为关联数组,还称为哈希数组等。也就是说,字典也是一个数组,但数组的索引是键经过哈希函数处理后得到的散列值。哈希函数的目的是使键均匀地分布在数组中,并且可以在内存中以O(1)的时间复杂度进行寻址,从而实现快速查找和修改。哈希表中哈希函数的设计困难在于将数据均匀分布在哈希表中,从而尽量减少哈希碰撞和冲突。由于不同的键可能具有相同的哈希值,即可能出现冲突,高级的哈希函数能够使冲突数目最小化。Python中并不包含这样高级的哈希函数,几个重要(用于处理字符串和整数)的哈希函数是常见的几个类型。
通常情况下建立哈希表的具体过程如下:
数据添加:把key通过哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。
数据查询:再次使用哈希函数将key转换为对应的数组下标,并定位到数组的位置获取value。
哈希函数就是一个映射,因此哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。本质上看哈希函数不可能做成一个一对一的映射关系,其本质是一个多对一的映射,这也就引出了下面一个概念–哈希冲突或者说哈希碰撞。哈希碰撞是不可避免的,但是一个好的哈希函数的设计需要尽量避免哈希碰撞。
Python2中使用使用开放地址法解决冲突。
CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节,只有可哈希的对象才能作为字典的键。字典的三个基本操作(添加元素,获取元素和删除元素)的平均事件复杂度为O(1)。
Python中所有不可变的内置类型都是可哈希的。
可变类型(如列表,字典和集合)就是不可哈希的,因此不能作为字典的键。
常见的哈希碰撞解决方法:
1 开放寻址法(open addressing)
开放寻址法中,所有的元素都存放在散列表里,当产生哈希冲突时,通过一个探测函数计算出下一个候选位置,如果下一个获选位置还是有冲突,那么不断通过探测函数往下找,直到找个一个空槽来存放待插入元素。
开放地址的意思是除了哈希函数得出的地址可用,当出现冲突的时候其他的地址也一样可用,常见的开放地址思想的方法有线性探测再散列,二次探测再散列等,这些方法都是在第一选择被占用的情况下的解决方法。
2 再哈希法
这个方法是按顺序规定多个哈希函数,每次查询的时候按顺序调用哈希函数,调用到第一个为空的时候返回不存在,调用到此键的时候返回其值。
3 链地址法
将所有关键字哈希值相同的记录都存在同一线性链表中,这样不需要占用其他的哈希地址,相同的哈希值在一条链表上,按顺序遍历就可以找到。
4 公共溢出区
其基本思想是:所有关键字和基本表中关键字为相同哈希值的记录,不管他们由哈希函数得到的哈希地址是什么,一旦发生冲突,都填入溢出表。
5 装填因子α
一般情况下,处理冲突方法相同的哈希表,其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为表中填入的记录数和哈希表长度的比值,也就是标志着哈希表的装满程度。直观看来,α越小,发生冲突的可能性就越小,反之越大。一般0.75比较合适,涉及数学推导。
在python中一个key-value是一个entry,
entry有三种状态。
Unused: me_key == me_value == NULL
Unused是entry的初始状态,key和value都为NULL。插入元素时,Unused状态转换成Active状态。这是me_key为NULL的唯一情况。
Active: me_key != NULL and me_key != dummy 且 me_value != NULL
插入元素后,entry就成了Active状态,这是me_value唯一不为NULL的情况,删除元素时Active状态刻转换成Dummy状态。
Dummy: me_key == dummy 且 me_value == NULL
此处的dummy对象实际上一个PyStringObject对象,仅作为指示标志。Dummy状态的元素可以在插入元素的时候将它变成Active状态,但它不可能再变成Unused状态。
为什么entry有Dummy状态呢?这是因为采用开放寻址法中,遇到哈希冲突时会找到下一个合适的位置,例如某元素经过哈希计算应该插入到A处,但是此时A处有元素的,通过探测函数计算得到下一个位置B,仍然有元素,直到找到位置C为止,此时ABC构成了探测链,查找元素时如果hash值相同,那么也是顺着这条探测链不断往后找,当删除探测链中的某个元素时,比如B,如果直接把B从哈希表中移除,即变成Unused状态,那么C就不可能再找到了,因为AC之间出现了断裂的现象,正是如此才出现了第三种状态---Dummy,Dummy是一种类似的伪删除方式,保证探测链的连续性。
提示
一般情况下普通的顺序表数组存储结构也可以认为是简单的哈希表,虽然没有采用哈希函数(取余),但同样可以在O(1)时间内进行查找和修改。但是这种方法存在两个问题:扩展性不强;浪费空间。
set集合和dict一样也是基于散列表的,只是他的表元只包含键的引用,而没有对值的引用,其他的和dict基本上是一致的,所以在此就不再多说了。并且dict要求键必须是能被哈希的不可变对象,因此普通的set无法作为dict的键,必须选择被“冻结”的不可变集合类:frozenset。顾名思义,一旦初始化,集合内数据不可修改。
来源:https://blog.csdn.net/answer3lin/article/details/84523332
猜你喜欢
- 本文实例讲述了Python实现矩阵加法和乘法的方法。分享给大家供大家参考,具体如下:本来以为python的矩阵用list表示出来应该很简单可
- gzip 是什么东东呢?百科跟我们说gzip是GNU zip的缩写,它是一个 GNU 自由软件的文件压缩程序。…gzip 的基础是 DEFL
- MySQL 客户端连接成功后,通过 show [session|global]status 命令 可以提供服务器状态信息,也可以在操作系统上
- 1、现象a.用localhost访问,正常b.用IP地址访问,则出现403错误2、分析a.怀疑是ACL问题,设置Everyone为完全控制,
- 重复的数据可能有这样两种情况,第一种: 表中只有某些字段一样,第二种是两行记录完全一样。一、对于部分字段重复数据的删除 1.查询重复的数据
- 其实网上已经有许多python语言书写的串口,但大部分都是python2写的,没有找到一个合适的python编写的串口助手,只能自己来写一个
- 如下所示:def save(data, path): f = xlwt.Workbook() # 创建工作簿 she
- 使用MySQL,目前你可以在三种基本数据库表格式间选择。当你创建一张表时,你可以告诉MySQL它应该对于表使用哪个表类型。MySQL将总是创
- collections中defaultdict的用法一、字典的键映射多个值将下面的列表转换成字典一个字典就是一个键对应一个单值得映射,而上面
- 本文实例讲述了Python使用chardet判断字符编码的方法。分享给大家供大家参考。具体分析如下:Python中chardet 用来实现字
- 通信信息包是发送至MySQL服务器的单个SQL语句,或发送至客户端的单一行。在MySQL 5.1服务器和客户端之间最大能发送的可能信息包为1
- 人脸检测方法有许多,比如opencv自带的人脸Haar特征分类器和dlib人脸检测方法等。对于opencv的人脸检测方法,有点是简单,快速;
- 一:命名空间里的namespace关键字和__NAMESPACE__常量的运用PHP支持两种抽象的访问当前命名空间内部元素的方法,__NAM
- 随着短视频的大火,不仅可以给人们带来娱乐,还有热点新闻时事以及各种知识,刷短视频也逐渐成为了日常生活的一部分。本文以一个简单的小例子,简述如
- 在使用AJAX开发网站时,经常有朋友遇到乱码的问题,而且一下子难以找到解决方法。其实解决AJAX中文乱码问题很简单。1、服务端程序:<
- 前言:Requests简介Requests 是使用Apache2 Licensed 许可证的 HTTP 库。用 Python 编写,真正的为
- 本文通过Python3+pyqt5实现了python Qt GUI 快速编程的19章的页面索引器应用程序例子。/home/yrd/eric_
- 一、安装一个基于Python的强大的信号库,它既支持简单的对象到对象通信,也支持针对多个对象进行组播支持注册全局命名信号,支持自定义命名信号
- #/usr/bin/env/python#coding=utf-8import sys,re,time,osmaxdata = 50000
- 插件很多从事互联网行业或者开发的人员来不是很陌生,wordpress之所以为什么那么受欢迎,很大部分是因为他的强大的插件库,还要譬如就是大家