在Python中,字典是通过散列表或说哈希表实现的。字典也被称为关联数组,还称为哈希数组等。也就是说,字典也是一个数组,但数组的索引是键经过哈希函数处理后得到的散列值。哈希函数的目的是使键均匀地分布在数组中,并且可以在内存中以O(1)的时间复杂度进行寻址,从而实现快速查找和修改。哈希表中哈希函数的设计困难在于将数据均匀分布在哈希表中,从而尽量减少哈希碰撞和冲突。由于不同的键可能具有相同的哈希值,即可能出现冲突,高级的哈希函数能够使冲突数目最小化.Python中并不包含这样高级的哈希函数,几个重要(用于处理字符串和整数)的哈希函数是常见的几个类型。
<强>数据添加:把关键通过哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将价值存储在以该数字为下标的数组空间里。
<强>数据查询:再次使用哈希函数将钥匙转换为对应的数组下标,并定位到数组的位置获取价值。
哈希函数就是一个映射,因此哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。本质上看哈希函数不可能做成一个一对一的映射关系,其本质是一个多对一的映射,这也就引出了下面一个概念——哈希冲突或者说哈希碰撞。哈希碰撞是不可避免的,但是一个好的哈希函数的设计需要尽量避免哈希碰撞。
Python2中使用使用开放地址法解决冲突。
CPython的使用伪随机探测(伪随机探测)的散列表(哈希表)作为字典的底层数据结构,由于这个实现细节,只有可哈希的对象才能作为字典的键。字典的三个基本操作(添加元素,获取元素和删除元素)的平均事件复杂度为O (1)。
Python中所有不可变的内置类型都是可哈希的。
可变类型(如列表,字典和集合)就是不可哈希的,因此不能作为字典的键。
<强> 1开放寻址法(开放寻址)
开放寻址法中,所有的元素都存放在散列表里,当产生哈希冲突时,通过一个探测函数计算出下一个候选位置,如果下一个获选位置还是有冲突,那么不断通过探测函数往下找,直到找个一个空槽来存放待插入元素。
开放地址的意思是除了哈希函数得出的地址可用,当出现冲突的时候其他的地址也一样可用,常见的开放地址思想的方法有线性探测再散列,二次探测再散列等,这些方法都是在第一选择被占用的情况下的解决方法。
<强> 2再哈希法
这个方法是按顺序规定多个哈希函数,每次查询的时候按顺序调用哈希函数,调用到第一个为空的时候返回不存在,调用到此键的时候返回其值。
<强> 3链地址法
将所有关键字哈希值相同的记录都存在同一线性链表中,这样不需要占用其他的哈希地址,相同的哈希值在一条链表上,按顺序遍历就可以找到。
<强> 4公共溢出区
其基本思想的是:所有关键字和基本表中关键字为相同哈希值的记录,不管他们由哈希函数得到的哈希地址是什么,一旦发生冲突,都填入溢出表。
<强> 5装填因子α
一般情况下,处理冲突方法相同的哈希表,其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为表中填入的记录数和哈希表长度的比值,也就是标志着哈希表的装满程度。直观看来,α越小,发生冲突的可能性就越小,反之越大。一般0.75比较合适,涉及数学推导。
在python中一个键-值是一个条目,
<强>未使用: me_key==me_value=https://www.yisu.com/zixun/=空
未使用的是条目的初始状态,键和值都为NULL。插入元素时,未使用的状态转换成活跃状态。这是me_key为零的唯一情况。
<>强活跃: me_key !=NULL和me_key !=假且me_value !=NULL
插入元素后,入口就成了活跃的状态,这是me_value唯一不为零的情况,删除元素时活跃状态刻转换成假状态。
<强>假: me_key==假且me_value=https://www.yisu.com/zixun/=空
此处的虚拟对象实际上一个PyStringObject对象,仅作为指示标志.Dummy状态的元素可以在插入元素的时候将它变成活跃的状态,但它不可能再变成未使用的状态。
为什么条目有虚状态呢?这是因为采用开放寻址法中,遇到哈希冲突时会找到下一个合适的位置,例如某元素经过哈希计算应该插入到一处,但是此时一处有元素的,通过探测函数计算得到下一个位置B,仍然有元素,直到找到位置C为止,此时ABC构成了探测链,查找元素时如果散列值相同,那么也是顺着这条探测链不断往后找,当删除探测链中的某个元素时,比如B,如果直接把B从哈希表中移除,即变成未使用的状态,那么C就不可能再找到了,因为交流之间出现了断裂的现象,正是如此才出现了第三种状态——假,假是一种类似的伪删除方式,保证探测链的连续性。
