Question

什么是哈希算法，哈希函数主要有哪些？

Answer 1

额。。LZ是不是看了小说绘的终极解密啊？
我也蛮感兴趣滴。。嘿嘿，
哈希函数是一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系。
将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为：
　　Addr = H（key）
　　为此在建立一个哈希表之前需要解决两个主要问题：
　　⑴构造一个合适的哈希函数
　　均匀性 H（key）的值均匀分布在哈希表中；
　　简单　以提高地址计算的速度
　　⑵冲突的处理
　　冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）= H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。 　无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。
1.拉链
　　拉出一个动态链表代替静态顺序储存结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。
2.多哈希法
　　设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低（除非人品太差，否则几乎不可能冲突）。
3.开放地址法
　　开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）
　　其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称线性探测再散列。
　　如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2）
　　称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。
4.建域法
　　假设哈希函数的值域为[0,m-1]，则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
LZ先把自己现阶段的函数搞定，会慢慢接触高等的函数滴，感觉蛮刺激的。。