文章目录 一、散列（务实的小天鹅）函数设计方法1. 折叠法2. 平方取中法 二、散列函数设计：非数项总结
一、散列（务实的小天鹅）函数设计方法 1. 折叠法
折叠法设计散列函数的基本步骤：
将数据项按照位数分为若干段；将几段数字相加；对散列表大小求余，得到散列值。例如：对于电话号码62767255，可以两位两位分为4段（62、76、72、55），相加（62+76+72+55=265），散列表包括11个槽，那么就是265%11=1。所以， h ( 62767255 ) = 1 h(62767255)=1 h(62767255)=1。
有时候折叠法还会包括一个隔数反转的步骤。比如（62、76、72、55）隔数反转为（62、67、72、55），再累加（62+67+72+55=256），对11求余，（256%11=3），所以 h ′ ( 62767255 ) = 3 h'(62767255)=3 h′(62767255)=3。
虽然隔数反转从理论上看来毫无必要，但这个步骤确实为折叠法得到散列函数提供了一种微调手段。当我们发现折叠法得到的结果不太好时，就可以加入隔数反转，以便更好符合散列特性。
2. 平方取中法平方取中法的基本步骤：
将数据项做平方运算；取平方数的中间两位；对散列表的大小求余，得到散列值。例如：对44进行散列，首先 4 4 2 = 1936 44^2=1936 442=1936，然后取中间的93，对散列表大小11求余 93 % 11 = 5 93\%11=5 93%11=5，散列值为5。
?
折叠法和平方取中法都是完美散列函数，分散度都很好，但平方取中法计算量稍大。
二、散列函数设计：非数项对非数字的数据项进行散列时，把字符串中的每个字符看作ASCII码即可。
如字符串“cat”，ord('c')等于99，ord('a')等于96，ord('t')等于116。再将这些整数累加，对散列表大小求余。
当然，这样的散列函数对所有的变位词都返回相同的散列值，为了防止这一点，可以将字符串中字符所在的位置（“cat”中，“c”是第一位，“t”是第三位）作为权重因子，乘以ord值。即 99 × 1 + 97 × 2 + 116 × 3 = 641 99\times1+97\times2+116\times3=641 99×1+97×2+116×3=641，然后再去求余。
总结我们还可以设计出更多的散列函数方法，但要坚持的一个基本出发点是，散列函数不能成为存储过程和查找过程的计算负担。否则，在散列身上花费太多计算资源，可能还不如简单地进行顺序查找或者二分查找，失去了散列本身的意义。
97276843