杂凑算法-详解.docx

杂凑算法-详解
 
   
 
 
 
 
 
 
 
     
 
 
 
 
 
杂凑算法（Hashing algorithms）
目录
1 什么是杂凑算法
2 常见的杂凑算法
什么是杂   
 
   
杂凑算法-详解
 
   
 
 
 
 
 
 
 
     
 
 
 
 
 
杂凑算法（Hashing algorithms）
目录
1 什么是杂凑算法
2 常见的杂凑算法
什么是杂凑算法
　　杂凑(Hashing) 是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为杂凑函数/算法）将要检索的项与用来检索的索引（称为杂凑，或者杂凑值）关联起来，生成一种便于搜索的数据结构（称为杂凑表）。也译为散列。旧译哈希（误以为是人名而采用了音译）。它也常用作一种资讯安全的实作方法，由一串资料中经过杂凑算法 (Hashing algorithms) 计算出来的资料指纹 (data fingerprint)，经常用来识别档案与资料是否有被窜改，以保证档案与资料确实是由原创者所提供。
　　如今，杂凑算法也被用来加密存在数据库中的密码 (password) 字串，由于杂凑算法所计算出来的杂凑值 (Hash Value) 具有不可逆 (无法逆向演算回原本的数值) 的性质，因此可有效的保护密码。
常见的杂凑算法
　　有时候杂凑函数是一个压缩映像，因此不可避免会发生冲突，因此在建造hash’函数的时候不仅要设定一个好的hash函数，还要设定一种处理冲突的方法，哈希造表，散列表。
　　1、直接定址法 ：地址集合和关键字集合大小相同
　　2、数字分析法 ：根据需要hash的 关键字的特点选择合适hash算法，尽量寻找每个关键字的不同点。
　　3、平方取中法：取关键字平方之后的中间极为作为哈希地址，一个数平方之后中间几位数字与数的每一位都相关，取得位数由表长决定。比如：表长为
512,=2^9,可以取平方之后中间9位二进制数作为哈希地址。
　　4、折叠法：关键字位数很多，而且关键字中每一位上的数字分布大致均匀的时候，可以采用折叠法得到哈希地址，
　　5、除留取余法除P取余，可以选P为质数，或者不含有