⼀、字典的实现原理
胡济荣
python中的字典底层依靠哈希表(hash table)实现, 使⽤开放寻址法解决冲突, 哈希表是key-value类型的数据结构, 可以理解为⼀个键值需要按照⼀定规则存放的数组, ⽽哈希函数就是这个规则
字典本质上是⼀个散列表(总有空⽩元素的数组, python⾄少保证1/3的数组是空的), 字典中的每个键都占⽤⼀个单元, ⼀个单元分为两部分, 分别是对键的引⽤和对值的引⽤, 使⽤hash函数获得键的散列值, 散列值对数组长度取余, 取得的值就是存放位置的索引 哈希冲突(数组的索引相同), 使⽤开放寻址法解决
这也是python中要求字典的key必须可hash的原因
数组中1/3的位置为空, 增加元素可能会导致扩容, 引发新的散列冲突, 导致新的散列表中键的次序发⽣变化, 这也是字典遍历时不能添加和删除的原因
字典在内存中开销很⼤, 实际上是以空间换时间
⼆、hash算法与哈希冲突
哈希算法
根据设定的哈希函数H（key）和处理冲突⽅法将⼀组关键字映象到⼀个有限的地址区间上的算法。也称为散列算法、杂凑算法。
哈希表
server 2003数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在⼀定的关系，可以根据这种关系快速查询。
⾮哈希表
与哈希表相对应，集合中的数据和其存放位置没任何关联关系的集合。
教养的芬芳由此可见，哈希算法是⼀种特殊的算法，能将任意数据散列后映射到有限的空间上，通常计算机软件中⽤作快速查或加密使⽤。
哈希冲突
由于哈希算法被计算的数据是⽆限的，⽽计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。三、解决哈希冲突的⽅法
解决哈希冲突的⽅法⼀般有：开放定址法、链地址法（拉链法）、再哈希法、建⽴公共溢出区等⽅法。
俄勒冈州火山爆发
1 开放定址法
从发⽣冲突的那个单元起，按照⼀定的次序，从哈希表中到⼀个空闲的单元。然后把发⽣冲突的元素存⼊到该单元的⼀种⽅法。开放定址法需要的表长度要⼤于等于所需要存放的元素。
在开放定址法中解决冲突的⽅法有：线⾏探查法、平⽅探查法、双散列函数探查法。 开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查错误，只能做⼀个特殊标记。只到有下个元素插⼊才能真正删除该元素。
线⾏探查法
线⾏探查法是开放定址法中最简单的冲突处理⽅法，它从发⽣冲突的单元起，依次判断下⼀个单元是否为空，当达到最后⼀个单元时，再从表⾸依次判断。直到碰到空闲的单元或者探查完全部单元为⽌。
平⽅探查法
平⽅探查法即是发⽣冲突时，⽤发⽣冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²...直到到空闲单元。
在实际操作中，平⽅探查法不能探查到全部剩余的单元。不过在实际应⽤中，能探查到⼀半单元也就可以了。若探查到⼀半单元仍不到⼀个空闲单元，表明此散列表太满，应该重新建⽴。
双散列函数探查法
这种⽅法使⽤两个散列函数hl和h2。其中hl和前⾯的h⼀样，以关键字为⾃变量，产⽣⼀个0⾄m—l之间的数作为散列地址；h2也以关键字为⾃变量，产⽣⼀个l⾄m—1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)，探查序列的步长值是固定值l；对于平⽅探查法，探查序列的步长值是探查次数i的两倍减l；对于双散列函数探查法，其探查序列的步长值是同⼀关键字的另⼀散列函数的值。
2 链地址法（拉链法）
链接地址法的思路是将哈希值相同的元素构成⼀个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查、插⼊和删除主要在同义词链表中进⾏。链表法适⽤于经常进⾏插⼊和删除的
情况。
如下⼀组数字,(32、40、36、53、16、46、71、27、42、24、49、64)哈希表长度为13，哈希函数为H(key)=key%13，则链表法结果如下：
1 -> 40 -> 27 -> 53
固定宽带接入速率测试方法2
3 -> 16 -> 42
4
5
6 -> 32 -> 71
7 -> 46
8
9
10 -> 36 -> 49
11 -> 24
歌剧伤逝12 -> 64
注：在java中，链接地址法也是HashMap解决哈希冲突的⽅法之⼀，jdk1.7完全采⽤单链表来存储同义词，jdk1.8则采⽤了⼀种混合模式，对于链表长度⼤于8的，会转换为红⿊树存储。
3 再哈希法
就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 ... k;
当H1 = RH1(key) 发⽣冲突时，再⽤H2 = RH2(key) 进⾏计算，直到冲突不再产⽣，这种⽅法不易产⽣聚集，但是增加了计算时间。
4 建⽴公共溢出区
将哈希表分为公共表和溢出表，当溢出发⽣时，将所有溢出数据统⼀放到溢出区。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议