Python dict内部实现及Hash表冲突解决方法

Dict简介

Python中dict是一种能够实现key-value映射的数据结构，其内部使用Hash散列表实现。类似于C++中的unordered_map。

如果我们在python中定义了一个这样的dict，那么它储存的方式如图所示。注意我们平时在数据结构书上看到的往往只有key，没有value的。图中hash表存在hash冲突，即John Smith和Sandra Dee计算出的哈希值是重复的。

{
    "John Smith": "521-1234", 
    "Lisa Smith": "521-8976",
    "Sam Doe": "521-5030",
    "Sandra Dee": "521-9655",
    "Ted Baker": "418-4165",
}

dict内部实现

Python内部使用散列表实现dict，首先介绍散列函数的概念。
散列函数：一个把关键字映射为该关键字地址的函数，记作\(Hash(Key)=Addr\)。散列函数把两个不同的key映射为相同的哈希值时会发生冲突。
散列表：散列表可以理解为就是一个数组，但是需要用hash值去访问其中的元素。

散列函数的构造方法

散列函数好好坏直接影响了散列表的性能，一个好的散列函数应该具有以下几点性质：

1. 散列函数的定义域应该包含了所有需要存储的关键字。
2. 散列函数计算出的地址能够均匀地分布于地址空间中，减少冲突发生地概率。
3. 散列函数尽可能简单，计算时间不能太长。

散列函数有以下构造方法：

1. 直接地址法：\(H(key)=a*key+b\)
2. 除留余数法：假设散列表的长度为m，取一个小于等于m且最接近m的质数p，并且\(Hash(key)=key \% p\)。至于为什么取质数，详见参考资料[1]。
3. 数字分析法。
4. 平方取中法。

哈希冲突解决方法

任何一个设计出来的散列函数都不可避免地发生冲突，那么在\(H_1\)发生冲突时候就必须给发生冲突的key一个合适的位置\(H_2\)。

开放地址法

开放地址法，即Hash表中空闲的位置即可向它的同义词表项开放，又可向它的非同义词表项开放。也就是key发生地址冲突时，找一个空闲地址存这个key。数学公式为：\(H_i(key)=(H(key)+d_i) \% m, i=1,2,...,k (k\leq m-1)\)。其中H为哈希函数，m为散列表长度，\(d_i\)为增量序列。根据\(d_i\)的取值方法不同，开放地址法又分为以下几种。

1. 线性探测法。\(d_i=0,1,2,...,m-1\)。
2. 平方探测法。\(d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2,k\leq m/2\)，散列表的长度必须是一个可以表示成\(4k+3\)的素数。
3. 再散列法。再使用一个哈希函数计算地址增量。\(H_i=(H(key)+i\times Hash_2(key))\%m\)。i初始为0，最多经过m-1次探测就会遍历表中所有的位置。
4. 伪随机数法。\(d_i\)取值为伪随机数。

拉链法

所谓拉链法就是将发生哈希冲突的key用同一个链表存储起来，如下图。这种方法对于需要频繁插入和删除的散列表比较适用。

重哈希

重哈希就是将哈希表进行扩容，然后将旧哈希表中的元素重新放在新hash表中。如下图：

参考资料

[1] Hash时取模一定要模质数吗？ - 我只想做一只懒猫的回答 - 知乎