杂凑算法

出自 MBA智库百科(https://wiki.mbalib.com/)

杂凑算法（Hashing algorithms）

　　杂凑(Hashing) 是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为杂凑函数/算法）将要检索的项与用来检索的索引（称为杂凑，或者杂凑值）关联起来，生成一种便于搜索的数据结构（称为杂凑表）。也译为散列。旧译哈希（误以为是人名而采用了音译）。它也常用作一种资讯安全的实作方法，由一串资料中经过杂凑算法 (Hashing algorithms) 计算出来的资料指纹 (data fingerprint)，经常用来识别档案与资料是否有被窜改，以保证档案与资料确实是由原创者所提供。

　　如今，杂凑算法也被用来加密存在数据库中的密码 (password) 字串，由于杂凑算法所计算出来的杂凑值 (Hash Value) 具有不可逆 (无法逆向演算回原本的数值) 的性质，因此可有效的保护密码。

　　有时候杂凑函数是一个压缩映像，因此不可避免会发生冲突，因此在建造hash’函数的时候不仅要设定一个好的hash函数，还要设定一种处理冲突的方法，哈希造表，散列表。

　　1、直接定址法 ：地址集合和关键字集合大小相同

　　2、数字分析法 ：根据需要hash的 关键字的特点选择合适hash算法，尽量寻找每个关键字的不同点。

　　3、平方取中法：取关键字平方之后的中间极为作为哈希地址，一个数平方之后中间几位数字与数的每一位都相关，取得位数由表长决定。比如：表长为512,=2^9,可以取平方之后中间9位二进制数作为哈希地址。

　　4、折叠法：关键字位数很多，而且关键字中每一位上的数字分布大致均匀的时候，可以采用折叠法得到哈希地址，

　　5、除留取余法除P取余，可以选P为质数，或者不含有小于20的质因子的合数

　　6、随机数法：通常关键字不等的时候采用此法构造哈希函数较恰当。

　　实际工作中需要视不同的情况采用不同的hash函数：

　　1、考虑因素：计算哈希函数所需要的时间，硬件指令等因素。

　　2、关键字长度

　　3、哈希表大小

　　4、关键字分布情况

　　5、记录查找的频率。（huffeman树）

　　处理冲突的方法：

　　开放地址法：现行探测再散列，只要哈希表为填满，总能找到一个不冲突的地址，二次探测再散列 表长为素数时才可能保证总能找到一个不冲突的地址，随机探测再散列取决于伪随机数列。

　　再哈希法：不易发生聚集，但是增加了计算的时间

　　链地址法；Chord协议中，一致性hash有应用。

　　对不同hash函数以及处理冲突的方法，计算了查找成功的平均长度以及不成功的平均长度。这些结果主要取决于装填因子，装填因子，可以将平均查找长度限定在一个范围内。