MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值。
 
 
SHA（Secure Hash Algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值。
 
 
MAC（Message Authentication Code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息，常见的是HMAC（用于消息认证的密钥散列算法）。
 
 
CRC（Cyclic Redundancy Check）：循环冗余校验码，CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。
 

1 散列函数的设计原则
 
  作为好的散列函数hash()，首先必须具有确定性。无论所含数据项如何，词条E在散列表中的映射地址hash(E.key)必须完全取决于其关键码key。其次映射过程资深不能过于复杂，唯此房能保证散列地址的计算可快速完成，从而保证查询或修改操作整体的O(1)期望执行时间。再次，所有关键码经映射后尽量覆盖整个地址空间[0,M)，方可充分利用有限空间。也就是说，函数hash()最好是满射。
   由于定义域规模远远大于取值域规模，hash()不可能是单射。这就意味着，不同的词条可能被映射到同一散列地址（散列冲突）难以避免。所以设计和选择散列函数阶段要做好充分的考量，以便尽可能地降低冲突发生的概率。
   在此，最为重要的一条原则就是，关键码映射到各桶的概率应尽量相等，这等效于将关键码“均匀地”映射到散列地址空间，从而避免导致极端低效的情况，比如，关键码集中分布于某一区间，而加剧散列冲突。
   总而言之，随机越强、规律性越弱的散列函数越好。
 
2 常见设计方法
 
2.1 除余法
 
设计方法
 
  符合上述设计原则的一种最简单的映射方法，就是将散列表长度M取作素数，并将关键码key映射至key关于M整除的余数：
     hash(key) = key mod M
 
 
 
一般散列表的长度M与词条关键码间隔T之间的最大公约数越大，发生冲突的可能性也将越大，因此将M取作素数
 
 
实例分析
 
  以校园电话簿为例，取M=90001，则以下关键码{6278-5001，5153-1876，6277-0211}—>{54304，51304，38514}
 
 
不足之处
 
  以素数为表长的除余法尽管可在一定程度上保证词条的均匀分布，但从关键码空间到散列地址空间映射的角度看，依然残留某种连续性。比如，相邻关键码所对应的散列地址，总是彼此相邻；极小的关键码，通常都被集中映射到散列表的起始区段一一其中特别是0值居然是一个“不动点”，其散列地址总是0。
 
2.2 MAD法
 
设计方法
 
  所谓的MAD法是multply-add-divide的缩写，其将关键码key映射至key与常数a之积再于常数b之和对M求余数（M的取值方法与除余法相同）：
     hash(key) = (a x key + b) mod M
   MAD法尽管运算量略有增加，但只要常数a和b选取得当可以很好地克服除余法原有的连续性缺陷。
 
实例分析
 
  当取a=31和b=2时，关键码集合a{2011，2012，2013，2014，2015，2016}，经过散列函数得出集合b{1，4，6，9，12，15}。连续的关键码经过散列后并不连续，各关键码散列的均匀性和随机性有了很大的改善。
 
 
2.3 数字分析法
 
设计方法
 
  数字分析法从关键码key特定进制的展开中抽取出特定的若干位，构成一个整型地址。比如，取十进制展开中奇位数，则有
     hash(123456789) = 13579
 
2.4 平方取中法
 
设计方法
 
  平方取中法，从关键码key的平方的十进制或二进制展开中取居中的若干位，构成一个整型地址。比如，去平方后十进制展开中居中的三位，则有
     hash(123) = 512 (1232=15129)
 
2.5 折叠法
 
设计方法
 
  折叠法，是将关键码的十进制或二进制展开分割成等宽的若干段，取其总和作为散列地址。比如，若以三个数位为分割单位，则有
     hash(123456789) = 123 + 456 + 789 = 1368
 
2.6 位异或法
 
设计方法
 
  位异或法，是将关键码的二进制展开分割成等宽的若干段，经异或运算得到散列地址。比如，仍以三个数位为分割单位，则有
     hash(411) = hash(110011011b) = 110 ^ 011 ^ 011 = 110b = 6
 
3 散列冲突解决方案
 
冲突的普遍性
 
  无论散列函数设计得如何巧妙，也不可能保证不同的关键码之间互不冲突。事实上在实际应用中，不发生任何冲突的概率远远低于我们的想象。我们来看下面这个例子，某课堂的所有学生中，是否有某两位生日相同？需要多少学生才能是这样的概率大于50%呢？
   不难证明上述的答案是，只要学生人数大于23，生日相同的概率将大于50%。若将全年各天视作365个桶，并将学生视作词条，则可按生日将他们组织为散列表，则该问题便可转化为：若长度为365的散列表中存在n个词条，则至少发生一次冲突的概率是多大？由此可见，解决散列冲突是涉及散列表中非常重要的部分。
 
3.1 多槽位法
 
  最简单的解决冲突策略是，将彼此冲突的每一组词条组织为一个小规模的子词典，分别存放他们共同对应的桶单元。多槽位法是将各桶细分为更小的槽位，每一组槽位使用向量存储数据。
 
   多槽位法优点是速度快，但是使用向量需要提前申请空间，导致空间利用率低。
 
3.2 独立链法
 
  独立链法与多槽位法是同样的策略，不过子词典采用链表结构。
 
   采用独立链法可以有效避免向量的空间浪费问题，缺点是操作时间增加。
 
3.3 公共溢出区法
 
  公共溢出区法的思路是，在原散列表职位另设一个词典结构，相当于一个公共缓存区，一旦发生冲突就将该词条转存至公共缓存区。
 
   该策略构思简单、易于实现，在冲突不甚频繁的场合不失为一种好的选择。
 
闭散列策略
 
  尽管逻辑结构而言，独立链等策略便捷而紧凑，但绝非上策。比如需要引进次级关联结构，在查找过程中将需要做更多地I/O操作，时间成本大大增加。实际上仅仅依靠基本的散列表结构就地解决冲突，反而是更好的选择。
   闭散列策略，即当词条存在冲突时，只允许在散列表内部为其寻找另一空桶。因闭散列策略不得使用附加控件，装填因子需要适度降低，通常取λ≤0.5
 
3.4 线性试探法
 
  线程试探法采用闭散列策略，当关键码key词条插入时，发现桶单元hash(key)已被占用，则转而试探下一个桶单元hask(key)+1， 如此不断试探，直到发现一个可用空桶。当然为确保桶地址的合法，最后还需要统一对M取模。
   在查找过程中只有查找到对应关键码或第一个空桶才停止，否则须转入下一个桶单元继续试探。
   在删除时采用假删除策略，将被删除的桶单元关键码改为特定的数（如-1）表示删除，以便查找时不至于找不到关键码。
 
   线性试探法在物理上保持了一定的连贯性，具有良好的数据局部性，故系统缓存的作用可以充分发挥。尽管闭散列策略同时也会一定程度上增加冲突发生的可能，但只要散列表的规模不是很小，装填因子不大，则相对于I/O的负担降低而言，这些问题都微不足道。
 
3.5 平方试探法
 
  由于数据的局部性，数据往往会聚集在散列表中的某个地方，采用MAD散列函数可缓解一定的聚集现象。而平方试探法，则是更为有效的一种方法。
   在发生冲突时，按如下规则确定第j次试探的桶地址：
     ( hash(key) + j2 ) mod M   （j=0,1,2……）
   平方试探法的删除和查找策略与线性试探法大致相同。
 
   平方试探法能很好解决词条的聚集现象，但线性试探法中，只要散列表中尚有空桶，则试探过程必将会终止。而平方试探法是否能保证这一点呢？
   事实上平方试探法无法保证有空桶必将终止，但是能保证散列表长度M为素数且装填因子λ≤50%时，必将终止于某个空桶。
 
3.6 再散列法
 
  在散列法也是一个解决聚集现象的有效办法。为此，需要选取一个适宜的二级散列函数hash2()，一旦在插入词条时发现桶单元hash(key)已被占用，则以hash2(key)为偏移增量继续尝试，直到发现一个空桶。如此，被尝试的桶地址依次应为：
     [ hash(key) + 1 x hash2(key) ] % M
     [ hash(key) + 2 x hash2(key) ] % M
     [ hash(key) + 3 x hash2(key) ] % M
   可见再散列法也是一种线性试探，只不过不同的key的增量不同。
 
 
 
本文内容来自 邓俊辉老师的 《数据结构与算法》
 

 

  散列函数
 
 
 

   
 
 
 

  在以下的讨论中，我们假设处理的是值为整型的关键码，否则我们总可以建立一种关键码与正整数之间的一一对应关系，从而把该关键码的检索转化为对与其对应的正整数的检索；同时，进一步假定散列函数的值落在0到M－1之间。散列函数的选取原则是：运算尽可能简单；函数的值域必须在散列表的范围内；尽可能使得结点均匀分布，也就是尽量让不同的关键码具有不同的散列函数值。需要考虑各种因素：关键码长度、散列表大小、关键码分布情况、记录的检索频率等等。下面我们介绍几种常用的散列函数。
 
 
 

  1、除余法
 
 
 

  顾名思义，除余法就是用关键码x除以M（往往取散列表长度），并取余数作为散列地址。除余法几乎是最简单的散列方法，散列函数为： h(x) ＝ x mod M。
 
 
 

   
 
 
 

  2、乘余取整法
 
 
 

  使用此方法时，先让关键码key乘上一个常数A (0< A < 1)，提取乘积的小数部分。然后，再用整数n乘以这个值，对结果向下取整，把它做为散列的地址。散列函数为： hash ( key ) = _LOW( n × ( A × key % 1 ) )。 其中，“A × key % 1”表示取 A × key 小数部分，即： A × key % 1 = A × key - _LOW(A × key), 而_LOW(X)是表示对X取下整。
 
 
 

   
 
 
 

  3、平方取中法
 
 
 

  由于整数相除的运行速度通常比相乘要慢，所以有意识地避免使用除余法运算可以提高散列算法的运行时间。平方取中法的具体实现是：先通过求关键码的平方值，从而扩大相近数的差别，然后根据表长度取中间的几位数（往往取二进制的比特位）作为散列函数值。因为一个乘积的中间几位数与乘数的每一数位都相关，所以由此产生的散列地址较为均匀。
 
 
 

   
 
 
 

  4、数字分析法
 
 
 

  设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种符号出现的几率均等; 在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
 
 
 

   
 
 
 

  5、基数转换法
 
 
 

   
 
 
 

  将关键码值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。
 
 
 

   
 
 
 

  6、折叠法
 
 
 

  有时关键码所含的位数很多，采用平方取中法计算太复杂，则可将关键码分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址，这方法称为折叠法。
 
 
 

   
 
 
 

  7、ELFhash字符串散列函数
 
 
 

  ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format，即ELF )中会用到，ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效，字符串中每个字符都有同样的作用，它巧妙地对字符的ASCII编码值进行计算，ELFhash函数对于能够比较均匀地把字符串分布在散列表中。
 
 
转载于:https://www.cnblogs.com/anzhi/p/7536448.html

 1、散列表(hash table) ，也叫哈希表，是根据关键码而直接进行访问的数据结构。也就是说，它通过把关键码映射到表中一个位置
 
 来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
 
 
 
 2、若结构中存在关键码为x的记录，则必定在hash(x)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系hash
 
 为散列函数(hash function)，按这个思想建立的表为散列表。
 
 3、散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到
 
 同一个散列地址上，这就产生了冲突 (Collision)。即key1≠ key2，而hash(key1)=hash(key2)，这种现象称冲突。我们将key1与key2称
 
 做同义词。
 
 
 
 4、由于关键码集合比地址集合大得多，冲突很难避免。所以对于散列方法，需要讨论以下两个问题：
 
 
 
 
 对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；
 
 
 拟订解决冲突的方案。
 
 
 5、散列函数的选择有两条标准：简单和均匀
 
 
 
 
 简单指散列函数的计算简单快速，能在较短时间内计算出结果。
 
 
 均匀指散列函数计算出来的地址能均匀分布在整 个地址空间。若key是从关键字码集合中随机抽取的一个关键码，散列函数能
 
 
 以等概率均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。
 
 二，散列函数的构造方法 
 
 
 （一）、直接定址法
 
 此类函数取关键码的某个线性函数值作为散列地址：hash ( key ) = a * key + b      { a, b为常数 }
 
 
 这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。
 
 
 
 
 
 （二）、数字分析法
 
 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。
 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。
 
 例：  有80个记录，关键字为8位十进制数，哈希地址为2位十进制数
 
 （三）、平方取中法
 
 取关键字平方后中间几位作哈希地址。适于关键字位数不定情况。
 
 
 具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间
 
 几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀
 
 （四）、折叠法
 
 此方法把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
 
 
 
 把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。有两种叠加方法：
 
 
 
 
 移位法 — 把各部分的最后一位对齐相加；
 
 
 分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。
 
 
 一般当关键码的位数很多，而且关键码每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。
 
 （五）、随机数法
 
 选择一个随机函数，取关键字的随机函数值为它的散列地址，即 hash(key) = random(key) ；其中random为伪随机函数，但要保证函
 
 数值是在0到m-1之间。
 
 
 
 
 
 （六）、除留余数法
 
 设散列表中允许的地址数为 m, 散列函数为：
 
 
 
 
  hash ( key ) = key % p    p <=  m
 
 
 若p取100，则关键字159、259、359互为同义词。我们选取的p值应尽可能使散列函数计算得到的散列地址与各位相关，根据经
 
 验，p最好取一个不大于 m，但最接近于或等于 m 的质数 p,  或选取一 个不小于 20 的质因数的合数作为除数（比如8 = 2*2*2，2 是 
 
 8 的质因数，8 是合数）
 
 
 
 示例：有一个关键码 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址
 
 为 hash ( 962148 ) = 962148 % 23 = 12
 
 
 
 可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地
 
 址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。
 
 
 
 
 （七）、乘余取整法
 
 使用此方法时，先让关键码 key 乘上一个常数  A (0 < A < 1)，提取乘积的小数部分。然后，再用整数 n 乘以这个值，对结果向下取
 
 整，把它做为散列的地址。
 

 
 常见散列函数 请查看 链接：http://blog.csdn.net/makenothing/article/details/40894603