python数据结构教程 Day10
本节重点：
- 散列
- 散列函数
- 完美散列函数
- hashlib
- 散列函数设计
- 冲突解决方案
一、散列
能够使得查找的次数降低到常数级别，我们对数据项所处的位置就必须有更多的先验知识。如果我们事先能知道要找的数据项应该出现在数据集中的什么位置，就可以直接到那个位置看看数据项是否存在即可，由数据项的值来确定其存放位置
散列表（哈希表）
是一 种数据集，其中数据项的存储方式尤其有利于将来快速的查找定位。散列表中的每一个存储位置，称为槽（slot），可以用来保存数据项，每个槽有一个唯一的名称。
在插入数据项之前，每个槽的值都是 None，表示空槽。
二、散列函数
实现从数据项到存储槽名称的转换的，称为散列函数（hash function），示例中散列函数接受数据项作为参数，返回整数值0～10，表示数据项存储的槽号（名称）。
示例：
数据项：54，26，93，17，77，31
散列函数1：求余数
将数据项除以散列表的大小，得到的余数作为槽号。实际上“求余数”方法会以不同形式出现在所有 散列函数里，因为散列函数返回的槽号必须在散列表大小范围之内，所以一般会对散列表大小求余。
公式：h(item)= item % 11，计算出对应结果为10,4,5,6,0,9
当6个数据项插入后，占据了散列表 11个槽中的6个。槽被数据项占据的比例称为散列表的“负载因子” ，这里负载因子为6/11。
要查找某个数据项是否存在于表中，我们只需要使用同一个散列函数，对查找项进行计算，测试下返回的槽号所对应的槽中是否有数据项即可，实现了O(1)时间复杂度的查找算法。
缺陷：
假如还要保存44，h(44)=0，它跟77被分配到同一个0#槽中，这种情况称为“冲突collision”
三、完美散列函数
定义：
给定一组数据项，如果一个散列函数能把 每个数据项映射到不同的槽中，那么这个散列函数就可以称为“完美散列函数”。如果数据固定，总是可以想办法设计出完美散列函数，但如果数据项经常性的变动，很难有一个系统性的方法来设计对应的完美散列函数，一般是如果出现了冲突，再解决冲突。
获得完美散列函数数的一种方法是扩大散列表的容量，大到所有可能出现的数据项都能够占据不同的槽。但是这种方式如果数据项很大时，空间开销太高。退而求其次，一般我们找到一个较好的散列函数即可。冲突最少（近似完美）、计算难度低（额外开销小）、充分分散数据项（节约空间）
运用完美散列函数能够对任何不同的数据生成不同的散列值，如果把散列值当作数据的“指纹”或者“摘要” ，这种特性被广泛应用在数据的一致性校验上。设计巧妙的“准完美”散列函数能在实用范围 内做到这一点，满足压缩性、易计算性、抗修改性、抗冲突性四个原则。
应用：MD5、SHA1、SHA2，用于数据的一致性校验较多，如彩票投注应用、文件内容、网络文件完整与否、加密形式保存密码。
四、hashlib
Python自带MD5和SHA系列的散列函数 库：hashlib。
>>>import hashlib
>>>hashlib.md5("hello world").hexdigest()
'fc3ff98e8c6a0d3087d515c0473f8677'
可以使用update方法对任意长度的数据进行分部分计算，解决数据内存不足的问题。
m = hashlib.md5()
m.update("hello world!")
m.update("this is part 2")
五、散列函数设计
1、折叠法：
将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余，得到散列值，有时可能加入隔数反转等微调操作。
示例：
例如，对电话号码62767255
可以两位两位分为4段（62、76、72、55）
相加（62+76+72+55=265）
散列表包括11个槽，那么就是265%11=1
所以h(62767255)=1
隔数反转：
比如（62、76、72、55）隔数反转为（62、67
、72、55）
再累加（62+67+72+55=256）
对11求余（256%11=3），所以h'(62767255)=3
2、平方取中法：
首先将数据项做平方运算，然后取平方数的中间两位，再对散列表的大小求余。
示例：
例如，对44进行散列
首先44*44=1936
然后取中间的93
对散列表大小11求余，93%11=5
3、非数项：
ASCII码转换数字后累加对散列表求余，该方法对变位词得到的散列值相同，考虑在不同位置对应不同的权重。
示例：
如cat，ord('c')==99, ord('a')==96,
ord('t')==116
再将这些整数累加，对散列表大小求余
当然，这样的散列函数对所有的变位词都返回相同的散列值，如eat与tea。为了防止这一点，可以将字符串所在的位置作为权重因子，乘以ord值。
坚持的一个基本出发点是，散列函数不能成为存储过程和查找过程的计算负担。如果散列函数设计太过复杂，去花费大量的计算资源计算槽号，可能还不如简单地进行顺序查找或者二分查找，失去了散列本身的意义。
六、冲突解决方案
如果两个数据项被散列映射到同一个槽， 需要一个系统化的方法在散列表中保存第二个数据项，这个过程称为“解决冲突”。
散列函数中冲突的解决方案：
1、开放定址（寻找空槽、又称再散列）
1）线性探测（逐个槽寻找）
我们把44、55、20逐个插入到散列表中
h(44)=0，但发现0#槽已被77占据，向后找到第一个空槽1#，保存
h(55)=0，同样0#槽已经被占据，向后找到第一个空槽2#，保存
h(20)== 9，发现9#槽已经被31占据了，向后，再从头开始找到3#槽保存
缺点：如果同一个槽冲突的数据项较多的话，这些数据项就会在槽附近聚集起来，从而连锁式影响其它数据项的插入。
2）跳跃式探测：
newhashvalue = rehash(oldhashvalue)
对于线性探测来说，rehash(pos)= (pos+ 1)%sizeoftable
“+3”的跳跃式探测则是：rehash(pos)=(pos+ 3)% sizeoftable
跳跃式探测的再散列通式是：rehash(pos)=(pos+skip)% sizeoftable
跳跃式探测的再散列通式是：rehash(pos)=(pos+skip)% sizeoftable。跳跃式探测中，需要注意的是skip的取值，不能被散列表大小整除，否则会产生周期，造成很多空槽永远无法探测到一个技巧是，把散列表的大小设为素数，如例子中的11。
3）二次探测
基于跳跃式探测，不再固定skip的值，而是逐步增加skip值，如1、3、5、7、9。这样槽号就会是原散列值以平方数增加：h, h+1, h+4, h+9, h+16...
2、数据项链
将容纳单个数据项的槽扩展为容纳数据项集合（或者对数据项链表的引用），查找数据项时则需要查找同一个槽中的整个集合，当然，随着散列冲突的增加，对数据项的查找时间也会相应增加。
