散列函数（哈希函数）的设计有多种，我们
折叠法：
折叠法设计散列函数的基本步骤是：将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余，得到散列值。
例如对电话号码62767255，可以分为4端（62、76、72、55）相加的265，散列表包含11个槽，那么求余得1，所以h(62767255)=1。
有时候折叠法还会对包括一个隔数反转的步骤，比如（62、76、72、55）隔数反转为（62、67、72、55），再累加为256，所以h(62767255)=3.
平方取中法：
平方取中法首先将数据项做平方运算，然后取平方数的中间两位，最后对散列表大小求余，得到散列值。
例如对44进行散列，=1936，取中即93，求余得5。
散列函数的设计：非数项
这两种都是完美散列函数，分散度都很好，但平方取中法计算量较大。但如果数据项是非数字，则使用上面两种方法需要把字符串的每个字符看作是ASCII码，再将这些数累加后求余。如cat：
非数项
代码如下：
def hash(astring,tablesize):
sum = 0
for pos in range(len(astring)):
sum = sum + ord(astring[pos])
return sum%tablesize
#ord() 函数是 chr() 函数（对于8位的ASCII字符串）或 unichr() 函数（对于Unicode对象）的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值。而函数的入参astring是一个列表。
但是如果字符串是回文，则返回相同的散列值，为了防止这个问题，可以将字符串所在的位置作为权重因子，乘以ord值。如下：
方法优化
当然还可以设计出更多的散列函数方法，但是散列函数不能过于复杂，因为散列函数不能成为存储过程和查找过程的计算负担，否则失去了散列本身的意义。
如果散列不是完美散列函数，就可能出现冲突，因此解决散列冲突成为散列方法中很重要的一部分。
解决散列的一种方法就是为冲突的数据项再找一个开放的空槽来保存。最简单的就是从冲突的槽开始往后扫描，直到碰到一个空槽，如果到散列尾部还未找到，则从首部接着扫描。这种寻找空槽的技术成为“开放定址”（open addressing）。向后逐个槽寻址的方法则是开放定址技术中的“线性探测”（linear probing）。
例如我们把77、44、55、20逐个插入散列表中，会得到如下结果：
结果
当0号槽被77占则44往后空槽保存，55、20也是如此。
采用线性探测方法来解决散列冲突的话，则散列表的查找也遵循同样的规则。如果在散列位置没有找到查找项的话，就必须向后做顺序查找。直到找到查找项，或者碰到空槽（即查找失败）。
但是线性探测法的一个缺点是有聚集(clustering)的趋势。即如果同一个槽冲突的数据项较多的话，这些数据项就会在槽附近聚集起来，从而连锁式影响其他数据项的插入。
所以避免聚集的一种方法就是将线性探测扩展，从逐个探测改为跳跃性探测。这就是线性探测的改进。下图是“+3”探测插入44、55、20。
跳跃性探测
重新寻找空槽的过程可以用一个更为通用的“再散列rehashing”来概括：
newhashvalue = rehash(oldhashvalue)
对于线性探测来说，rehash(pos) = (pos + 1)%sizeoftable
"+3"的跳跃式探测则是：rehash(pos) = (pos + 3)%sizeoftable
跳跃式探测的再散列通式是：rehash(pos) = (pos + skip)%sizeoftable
⚠️注意，跳跃式探测中，skip的取值不能被散列表大小整除，否则会产生周期，造成很多空槽永远无法探测到。例如上面的例子里，skip不能为11。有一个技巧就是，把散列表的大小设为素数，例如11。
还可以将线性探测变为“二次探测”，不再固定skip的值，而是逐步增加skip的值，如1、3、5、7、9，这样槽号就会是原散列值以平方数增加：h,h+1,h+1+3=h+4,h+1+3+5=h+9,h+16...
冲突解决方法：数据项链Chaining
除了寻找空槽的开放定址技术外，另一种解决冲突的方案是将容纳单个数据项的槽扩展为容纳数据项集合，这样散列表中的每个槽就可以容纳多个数据项了。如果有散列冲突发生，只需要简单的将数据项添加到数据项集合中。查找数据项时则需要查找同一个槽中的整个集合。当然，随着散列冲突的增加，对数据项的查找时间也会相应增加。
数据项链Chaining
网友评论