参考链接：数据结构（严蔚敏）
 文章发布很久了，具体细节已经不清晰了，不再回复各种问题
 文章整理自严蔚敏公开课视频
 可以参考
 https://www.bilibili.com/video/av22258871/
 如果链接失效 可以自行搜索 数据结构严蔚敏视频
 @2021/07/12
 
一、什么是Hash表
 
要想知道什么是哈希表，那得先了解哈希函数
 哈希函数
 
对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树，它们的查找都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较。那么，有没有一种函数H，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就**“预先知道”**key所在的位置，直接找到数据，提升效率。
 即
 地址index=H（key）
 说白了，hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表
 
二、哈希函数的构造方法
 
根据前人经验，统计出如下几种常用hash函数的构造方法：
 直接定制法
 哈希函数为关键字的线性函数如 H（key）=a*key+b
 这种构造方法比较简便，均匀，但是有很大限制，仅限于地址大小=关键字集合的情况
 使用举例：
 假设需要统计中国人口的年龄分布，以10为最小单元。今年是2018年，那么10岁以内的分布在2008-2018，20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据，那么关键字应该是2018，2008，1998……
 那么可以构造哈希函数H（key）=（2018-key）/10=201-key/10
 那么hash表建立如下
 
index
key
年龄
人数（假设数据）
0
2018
 0-10
200W
1
2008
 10-20
250W
2
1998
 20-30
253W
3
1988
 30-40
300W
……
 
数字分析法
 假设关键字集合中的每个关键字key都是由s位数字组成（$k_1,k_2,\dots \dots ,k_n$）,分析key中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体
 
使用举例
 我们知道身份证号是有规律的，现在我们要存储一个班级学生的身份证号码，假设这个班级的学生都出生在同一个地区，同一年，那么他们的身份证的前面数位都是相同的，那么我们可以截取后面不同的几位存储，假设有5位不同，那么就用这五位代表地址。
 H（key）=key%100000
 此种方法通常用于数字位数较长的情况，必须数字存在一定规律，其必须知道数字的分布情况，比如上面的例子，我们事先知道这个班级的学生出生在同一年，同一个地区。
 平方取中法
 如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。
 使用举例
 比如key=1234 1234^2=1522756 取227作hash地址
 比如key=4321 4321^2=18671041 取671作hash地址
 这种方法适合事先不知道数据并且数据长度较小的情况
 折叠法
 如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址
 使用举例
 比如key=123 456 789
 我们可以存储在61524，取末三位，存在524的位置
 该方法适用于数字位数较多且事先不知道数据分布的情况
 除留余数法用的较多
 H（key）=key MOD p （p<=m m为表长）
 很明显，如何选取p是个关键问题。
 
使用举例
 比如我们存储3 6 9，那么p就不能取3
 因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
 p应为不大于m的质数或是不含20以下的质因子的合数，这样可以减少地址的重复（冲突）
 
比如key = 7，39，18，24，33，21时取表长m为9 p为7 那么存储如下
 
index
0
1
2
3
4
5
6
7
8
key
7
21（冲突后移）
24
*39*
18（冲突后移）
33冲突后移）
 **随机数法** H（key） =Random（key） 取关键字的随机函数值为它的散列地址 
hash函数设计的考虑因素
 
1.计算散列地址所需要的时间（即hash函数本身不要太复杂）
 2.关键字的长度
 3.表长
 4.关键字分布是否均匀，是否有规律可循
 5.设计的hash函数在满足以上条件的情况下尽量减少冲突
 
三、哈希冲突
 
即不同key值产生相同的地址，H（key1）=H（key2）
 比如我们上面说的存储3 6 9，p取3是
 3 MOD 3 == 6 MOD 3 == 9 MOD 3
 此时3 6 9都发生了hash冲突
 
哈希冲突的解决方案
 
不管hash函数设计的如何巧妙，总会有特殊的key导致hash冲突，特别是对动态查找表来说。
 hash函数解决冲突的方法有以下几个常用的方法
 1.开放定制法
 2.链地址法
 3.公共溢出区法
 建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
 4.再散列法
 准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……
 重点了解一下开放定制法和链地址法
 
开放定制法
 
首先有一个H（key）的哈希函数
 如果H（key1）=H（keyi）
 那么keyi存储位置$H_i=(H(key)+d_i)MODm$m为表长
 $d_i$有三种取法
 1）线性探测再散列
 $d_i=c\ast i$
 2）平方探测再散列
 $d_i=1^2,-1^2,2^2,-2^2$……
 3）随机探测在散列（双探测再散列）
 $d_i$是一组伪随机数列
 注意
 增量di应该具有以下特点（完备性）：产生的Hi（地址）均不相同，且所产生的s（m-1）个Hi能覆盖hash表中的所有地址
 
平方探测时表长m必须为4j+3的质数（平方探测表长有限制）
随机探测时m和di没有公因子（随机探测di有限制）
 三种开放定址法解决冲突方案的例子
 
 
废话不多说，上例子就明白了
 有一组数据
 19 01 23 14 55 68 11 86 37要存储在表长11的数组中，其中H（key）=key MOD 11
 那么按照上面三种解决冲突的方法，存储过程如下：
 （表格解释：从前向后插入数据，如果插入位置已经占用，发生冲突，冲突的另起一行，计算地址，直到地址可用，后面冲突的继续向下另起一行。最终结果取最上面的数据（因为是最“占座”的数据））
 线性探测再散列
 我们取di=1，即冲突后存储在冲突后一个位置，如果仍然冲突继续向后
 
index
0
1
2
3
4
5
6
7
8
9
10
key
55
1
14
19
86
23冲突
23
68冲突
68冲突
68
11冲突
11冲突
11冲突
11冲突
11冲突
11
37冲突
37冲突
37
最终存储结果
55
1
23
14
68
11
37
19
86
 **平方探测再散列** 
index
0
1
2
3
4
5
6
7
8
9
10
key
55
1
14
37
19
86
23冲突
H（23）+1
H（68）-1冲突
68冲突
H（68）+1冲突
H（68）+4
11冲突
H（11）+1冲突
H（11）-1
最终存储结果
55
1
23
14
37
68
19
86
11
 **随机探测在散列（双探测再散列）** 发生冲突后 H（key）‘=(H(key)+di)MOD m 在该例子中 H（key）=key MOD 11 我们取di=key MOD 10 +1 则有如下结果： 
index
0
1
2
3
4
5
6
7
8
9
10
key
55
1
68
14
19
86
23冲突
H（23）+3+1
11冲突
H（11）+1+1冲突
H（11）+1+1+1+1
（H（37）+8）模11冲突
37冲突
（H（37）+8+8+8）模11
（H（37）+8+8）模11冲突
最终存储结果
55
1
68
14
23
11
37
19
86
 
链地址法
 
产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据
 上面的例子，用链地址法则是下面这样：
 

 四、hash表的查找
 
查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
 对于给定的key，计算hash地址index = H（key）
 如果数组arr【index】的值为空 则查找不成功
 如果数组arr【index】== key 则查找成功
 否则 使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null
 
hash表的查找效率
 
决定hash表查找的ASL因素：
 1）选用的hash函数
 2）选用的处理冲突的方法
 3）hash表的饱和度，装载因子 α=n/m(n表示实际装载数据长度 m为表长)
 一般情况，假设hash函数是均匀的，则在讨论ASL时可以不考虑它的因素
 hash表的ASL是处理冲突方法和装载因子的函数
 前人已经证明，查找成功时如下结果：
 

 可以看到无论哪个函数，装载因子越大，平均查找长度越大，那么装载因子α越小越好？也不是，就像100的表长只存一个数据，α是小了，但是空间利用率不高啊，这里就是时间空间的取舍问题了。通常情况下，认为α=0.75是时间空间综合利用效率最高的情况。
 
上面的这个表可是特别有用的。假设我现在有10个数据，想使用链地址法解决冲突，并要求平均查找长度<2
 那么有1+α/2 <2
 α<2
 即 n/m<2 (n=10)
 m>10/2
 m>5 即采用链地址法，使得平均查找长度< 2 那么m>5
 
之前我的博客讨论过各种树的平均查找长度，他们都是基于存储数据n的函数，而hash表不同，他是基于装载因子的函数，也就是说，当数据n增加时，我可以通过增加表长m，以维持装载因子不变，确保ASL不变。
 那么hash表的构造应该是这样的：
 

 五、hash表的删除
 
首先链地址法是可以直接删除元素的，但是开放定址法是不行的，拿前面的双探测再散列来说，假如我们删除了元素1，将其位置置空，那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据，比如-1

  
public class HashAlgorithms
 {
 /**//**
 * 加法hash
 * @param key 字符串
 * @param prime 一个质数
 * @return hash结果
 */
 public static int additiveHash(String key, int prime)
 {
    int hash, i;
    for (hash = key.length(), i = 0; i < key.length(); i++)
     hash += key.charAt(i);
    return (hash % prime);
 }
 
/**//**
 * 旋转hash
 * @param key 输入字符串
 * @param prime 质数
 * @return hash值
 */
 public static int rotatingHash(String key, int prime)
 {
    int hash, i;
    for (hash=key.length(), i=0; i<key.length(); ++i)
      hash = (hash<<4)^(hash>>28)^key.charAt(i);
    return (hash % prime);
 //   return (hash ^ (hash>>10) ^ (hash>>20));
 }
 
// 替代：
 // 使用：hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask;
 // 替代：hash %= prime;
 

 /**//**
 * MASK值，随便找一个值，最好是质数
 */
 static int M_MASK = 0x8765fed1;
 /**//**
 * 一次一个hash
 * @param key 输入字符串
 * @return 输出hash值
 */
 public static int oneByOneHash(String key)
 {
    int   hash, i;
    for (hash=0, i=0; i<key.length(); ++i)
    {
      hash += key.charAt(i);
      hash += (hash << 10);
      hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
 //   return (hash & M_MASK);
    return hash;
 }
 
/**//**
 * Bernstein's hash
 * @param key 输入字节数组
 * @param level 初始hash常量
 * @return 结果hash
 */
 public static int bernstein(String key)
 {
    int hash = 0;
    int i;
    for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
    return hash;
 }
 
//
 /**/ Pearson's Hash
 // char pearson(char[]key, ub4 len, char tab[256])
 // {
 //   char hash;
 //   ub4 i;
 //   for (hash=len, i=0; i<len; ++i) 
 //     hash=tab[hash^key[i]];
 //   return (hash);
 // }
 
/**/ CRC Hashing，计算crc,具体代码见其他
 // ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab[256])
 // {
 //   ub4 hash, i;
 //   for (hash=len, i=0; i<len; ++i)
 //     hash = (hash >> 8) ^ tab[(hash & 0xff) ^ key[i]];
 //   return (hash & mask);
 // }
 
/**//**
 * Universal Hashing
 */
 public static int universal(char[]key, int mask, int[] tab)
 {
    int hash = key.length, i, len = key.length;
    for (i=0; i<(len<<3); i+=8)
    {
      char k = key[i>>3];
      if ((k&0x01) == 0) hash ^= tab[i+0];
      if ((k&0x02) == 0) hash ^= tab[i+1];
      if ((k&0x04) == 0) hash ^= tab[i+2];
      if ((k&0x08) == 0) hash ^= tab[i+3];
      if ((k&0x10) == 0) hash ^= tab[i+4];
      if ((k&0x20) == 0) hash ^= tab[i+5];
      if ((k&0x40) == 0) hash ^= tab[i+6];
      if ((k&0x80) == 0) hash ^= tab[i+7];
    }
    return (hash & mask);
 }
 
/**//**
 * Zobrist Hashing
 */ 
 public static int zobrist( char[] key,int mask, int[][] tab)
 {
    int hash, i;
    for (hash=key.length, i=0; i<key.length; ++i)
      hash ^= tab[i][key[i]];
    return (hash & mask);
 }
 
// LOOKUP3 
 // 见Bob Jenkins(3).c文件
 
// 32位FNV算法
 static int M_SHIFT = 0;
 /**//**
 * 32位的FNV算法
 * @param data 数组
 * @return int值
 */
     public static int FNVHash(byte[] data)
     {
         int hash = (int)2166136261L;
         for(byte b : data)
             hash = (hash * 16777619) ^ b;
         if (M_SHIFT == 0)
             return hash;
         return (hash ^ (hash >> M_SHIFT)) & M_MASK;
     }
     /**//**
      * 改进的32位FNV算法1
      * @param data 数组
      * @return int值
      */
     public static int FNVHash1(byte[] data)
     {
         final int p = 16777619;
         int hash = (int)2166136261L;
         for(byte b:data)
             hash = (hash ^ b) * p;
         hash += hash << 13;
         hash ^= hash >> 7;
         hash += hash << 3;
         hash ^= hash >> 17;
         hash += hash << 5;
         return hash;
     }
     /**//**
      * 改进的32位FNV算法1
      * @param data 字符串
      * @return int值
      */
     public static int FNVHash1(String data)
     {
         final int p = 16777619;
         int hash = (int)2166136261L;
         for(int i=0;i<data.length();i++)
             hash = (hash ^ data.charAt(i)) * p;
         hash += hash << 13;
         hash ^= hash >> 7;
         hash += hash << 3;
         hash ^= hash >> 17;
         hash += hash << 5;
         return hash;
     }
 
    /**//**
      * Thomas Wang的算法，整数hash
      */ 
     public static int intHash(int key)
     {
       key += ~(key << 15);
       key ^= (key >>> 10);
       key += (key << 3);
       key ^= (key >>> 6);
       key += ~(key << 11);
       key ^= (key >>> 16);
       return key;
     }
     /**//**
      * RS算法hash
      * @param str 字符串
      */
     public static int RSHash(String str)
     {
         int b    = 378551;
         int a    = 63689;
         int hash = 0;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash = hash * a + str.charAt(i);
           a    = a * b;
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of RS Hash Function */
 
    /**//**
      * JS算法
      */
     public static int JSHash(String str)
     {
        int hash = 1315423911;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of JS Hash Function */
 
    /**//**
      * PJW算法
      */
     public static int PJWHash(String str)
     {
         int BitsInUnsignedInt = 32;
         int ThreeQuarters     = (BitsInUnsignedInt * 3) / 4;
         int OneEighth         = BitsInUnsignedInt / 8;
         int HighBits          = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);
         int hash              = 0;
         int test              = 0;
 
       for(int i = 0; i < str.length();i++)
        {
           hash = (hash << OneEighth) + str.charAt(i);
 
          if((test = hash & HighBits) != 0)
           {
              hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
           }
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of P. J. Weinberger Hash Function */
 
    /**//**
      * ELF算法
      */
     public static int ELFHash(String str)
     {
         int hash = 0;
         int x    = 0;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash = (hash << 4) + str.charAt(i);
           if((x = (int)(hash & 0xF0000000L)) != 0)
           {
              hash ^= (x >> 24);
              hash &= ~x;
           }
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of ELF Hash Function */
 
    /**//**
      * BKDR算法
      */
     public static int BKDRHash(String str)
     {
         int seed = 131; // 31 131 1313 13131 131313 etc..
         int hash = 0;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash = (hash * seed) + str.charAt(i);
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of BKDR Hash Function */
 
    /**//**
      * SDBM算法
      */
     public static int SDBMHash(String str)
     {
         int hash = 0;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of SDBM Hash Function */
 
    /**//**
      * DJB算法
      */
     public static int DJBHash(String str)
     {
        int hash = 5381;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash = ((hash << 5) + hash) + str.charAt(i);
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of DJB Hash Function */
 
    /**//**
      * DEK算法
      */
     public static int DEKHash(String str)
     {
         int hash = str.length();
 
       for(int i = 0; i < str.length(); i++)
        {
           hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
        }
 
       return (hash & 0x7FFFFFFF);
     }
     /**//* End Of DEK Hash Function */
 
    /**//**
      * AP算法
      */
     public static int APHash(String str)
     {
         int hash = 0;
 
       for(int i = 0; i < str.length(); i++)
        {
           hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str.charAt(i) ^ (hash >> 3)) :
                                    (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
        }
 
//       return (hash & 0x7FFFFFFF);
        return hash;
     }
     /**//* End Of AP Hash Function */
     
     /**//**
      * JAVA自己带的算法
      */
     public static int java(String str)
 {
    int h = 0;
    int off = 0;
    int len = str.length();
    for (int i = 0; i < len; i++)
    {
     h = 31 * h + str.charAt(off++);
    }
    return h;
 }
     
     /**//**
      * 混合hash算法，输出64位的值
      */
     public static long mixHash(String str)
     {
     long hash = str.hashCode();
     hash <<= 32;
     hash |= FNVHash1(str);
     return hash;
     }
 }
  
 

一.概念
 
 
哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
 
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
 
使用哈希查找有两个步骤:
 
1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突
 
2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。
 
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
 
 
 
 
 
在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。使ASL趋近与0.
 
 
 
              1)   哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地       址集合的大小不超出允许范围即可；
 
             2)  由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1！=key2，而  f  (key1) = f(key2)。
 
              3).  只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字， 而地址集合的元素仅为哈希表中的地址值
 
 
 
       在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一 种“处理冲突” 的方法。
 
 
二.Hash构造函数的方法
 
 
 
   1.直接定址法：
 
                         
 
 直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k  或 H（k）=a×k+b ； (其中a,b为常数)
 
  例1，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图(1)：
 
 
地址
 
 
A1
 
 
A2
 
 
……
 
 
A99
 
 
A100
 
 
年龄
 
 
1
 
 
2
 
 
……
 
 
99
 
 
100
 
 
人数
 
 
980
 
 
800
 
 
……
 
 
495
 
 
107
 
 
可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。
 
 
 
 
地址
 
 
A0
 
 
A1
 
 
……
 
 
A99
 
 
A100
 
 
年龄
 
 
1980
 
 
1981
 
 
……
 
 
1999
 
 
2000
 
 
人数
 
 
980
 
 
800
 
 
……
 
 
495
 
 
107
 
 
 
 
如果我们要统计的是80后出生的人口数，如上表所示，那么我们队出生年份这个关键字可以用年份减去1980来作为地址，此时f(key)=key-1980
 
这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。[2]↑
 
  此法仅适合于：地址集合的大小 = = 关键字集合的大小，其中a和b为常数。
 
 
 
 
2.数字分析法：
 
             假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
 
数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。
 
   例2，要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示：
 
K1=61317602      K2=61326875      K3=62739628      K4=61343634
 
K5=62706815      K6=62774638      K7=61381262      K8=61394220
 
分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：2，75，28，34，15，38，62，20。           
 
 
 
 此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。
 
             
 
3.折叠法：
 
            将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分 割后的几部分低位对齐相加；边界叠加:从一端沿分割界来回折叠，然后对齐相加。
 
所谓折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。
 
  折叠法中数位折叠又分为移位叠加和边界叠加两种方法，移位叠加是将分割后是每一部分的最低位对齐，然后相加；边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
 
例4，当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则这两种叠加情况如图：
 
       移位叠加                                 边界叠加
 
       8 9 1                                     8 9 1
 
       1 1 9                                     9 1 1
 
       3 3 1                                     3 3 1
 
       1 0 8                                     8 0 1
 
    +  1 1 0                                   + 1 1 0              
 
   (1) 5 5 9                                  (3)0 4 4
 
                 图（2）由折叠法求哈希地址
 
     用移位叠加得到的哈希地址是559，而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串，则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。
 
            此法适于：关键字的数字位数特别多。
 
 
 
4.平方取中法
 
  这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。
 
哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。
 
例5，若设哈希表长为1000则可取关键字平方值的中间三位，如图所示：
 
 
关键字
 
 
关键字的平方
 
 
哈希函数值
 
 
1234
 
 
1522756
 
 
227
 
 
2143
 
 
4592449
 
 
924
 
 
4132
 
 
17073424
 
 
734
 
 
3214
 
 
10329796
 
 
297 
 
 
  
 
下面给出平方取中法的哈希函数
 
     //平方取中法哈希函数，结设关键字值32位的整数
 
     //哈希函数将返回key * key的中间10位
 
       Int  Hash (int key)
 
         {
 
     //计算key的平方
 
      Key * = key ;
 
     //去掉低11位
 
     Key>>=11;
 
     // 返回低10位（即key * key的中间10位）
 
       Return key %1024;
 
          }
 
   此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象
 

 
 
 
5.减去法
 
 
 
减去法是数据的键值减去一个特定的数值以求得数据存储的位置。
 
例7，公司有一百个员工，而员工的编号介于1001到1100，减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息，因为编号1000以前并没有数据，所有员工编号都从1001开始编号。
 
 
 
 
6.基数转换法
 
  将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。
 
 
 
例Hash(80127429)=(80127429)13=8*137+0*136+1*135+2*134+7*133+4*132+2*131+9=(502432641)10如果取中间三位作为哈希值，得Hash（80127429）=432
 
 为了获得良好的哈希函数，可以将几种方法联合起来使用，比如先变基，再折叠或平方取中等等，只要散列均匀，就可以随意拼凑。
 
 
 
 
 
 
  7.除留余数法：
 
              
 
 假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为
 
 h（k）=k  %  p ，其中%为模p取余运算。
 
 例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有
 
     h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
 
     h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
 
     h(46)=46 % 7=4
 
 此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：
 
     h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
 
     h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   
 
     h(46)=46 % 13=7
 
 此时没有冲突，如图8.25所示。
 
  
 
 0      1      2     3     4     5      6     7     8     9     10     11    12
 
  
 
 
 
 
  
 
 
  
 
 
 54
 
 
  
 
 
 43
 
 
 18
 
 
  
 
 
 46
 
 
 60
 
 
  
 
 
 75
 
 
  
 
 
 90
 
 
 
                       
 
 
 
 
 除留余数法求哈希地址
 
 
 
 
理论研究表明，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）
 
 
 
 
 
8.随机数法：
 
           设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数
 
           此法适于：对长度不等的关键字构造哈希函数。
 
 
 
         实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表    长度（哈希地址范围），总的原则是使产生冲突的可能性降到尽可能地小。
 
 
 
9．随机乘数法
 
  亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k 的小数部分，即f*k%1=f*k-「f*k」
 
  例10，对下列关键字值集合采用随机乘数法计算哈希值，随机数f=0.103149002 哈希表长度n=100得图：
 
 
 
 
k
 
 
f*k
 
 
n*((f*k)的小数部分)
 
 
Hash(k)
 
 
319426
 
 
32948.47311
 
 
47.78411
 
 
47
 
 
718309
 
 
74092.85648
 
 
86.50448
 
 
86
 
 
629443
 
 
64926.41727
 
 
42.14427
 
 
42
 
 
919697
 
 
84865.82769
 
 
83.59669
 
 
83
 
 
  此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329...比较理想。
 

 
 
10．字符串数值哈希法
 
在很都情况下关键字是字符串，因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数
 
Int Hash _ char (char *X)
 
{
 
  int I ,sum  
 
  i=0;
 
  while (i 10 && X[i])
 
  Sum +=X[i++];
 
  sum%=N;      //N是记录的条数
 
  }
 
这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内，因此这个函数还是可用的。对于N很大的情形，可使用下列函数
 
int ELFhash (char *key )
 
{
 
 Unsigned long h=0,g;
 
whie (*key)
 
{ 
 
h=(h<<4)+ *key;
 
key++;
 
g=h & 0 xF0000000L;
 
if (g) h^=g>>24;
 
h & =～g;
 
}
 
h=h % N
 
return （h）;
 
}
 
  这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置不可能不均匀分布。
 

 
 
11.旋转法
 
  旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。
 
  例11，某学校同一个系的新生（小于100人）的学号前5位数是相同的，只有最后2位数不同，我们将最后一位数，旋转放置到第一位，其余的往右移。
 
 
新生学号
 
 
旋转过程
 
 
旋转后的新键值
 
 
5062101
 
 
5062101
 
 
1506210
 
 
5062102
 
 
5062102
 
 
2506210
 
 
5062103
 
 
5062103
 
 
3506210
 
 
5062104
 
 
5062104
 
 
4506210
 
 
5062105
 
 
5062105
 
 
5506210
 
 
                    如图
 
 运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。
 
 
 
 
 
在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素 ：
 
l 计算哈希函数所需时间 （简单）。
 
l 关键字的长度。
 
l 哈希表大小。
 
l 关键字分布情况。
 
l 记录查找频率
 
 
 

 
 

 
 
三.Hash处理冲突方法
 
 
    通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：
 
 
 
  通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：
 
 1.         开放定址法
 
 这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
 
           Hi=（H（key）+di）% m   i=1，2，…，n
 
     其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
 
 l         线性探测再散列
 
     dii=1，2，3，…，m-1
 
 这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
 
 l         二次探测再散列
 
     di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )
 
     这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
 
 l         伪随机探测再散列
 
     di=伪随机数序列。
 
 具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
 
 例如，已知哈希表长度m=11，哈希函数为：H（key）= key  %  11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元，参图8.26 (a)。如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元，参图8.26 (b)。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元，参图8.26 (c)。
 
  
 
  
 
 0        1       2      3      4      5       6      7      8       9      10    
 
  
 
 
 
 
  
 
 
  
 
 
  
 
 
 47
 
 
 26
 
 
 60
 
 
 69
 
 
  
 
 
  
 
 
  
 
 
  
 
 
 
          （a） 用线性探测再散列处理冲突
 
  
 
  
 
 0        1       2      3      4      5       6      7      8       9      10    
 
  
 
 
 
 
  
 
 
  
 
 
 69
 
 
 47
 
 
 26
 
 
 60
 
 
  
 
 
  
 
 
  
 
 
  
 
 
  
 
 
 
          （b） 用二次探测再散列处理冲突
 
  
 
  
 
 0        1       2      3      4      5       6      7      8       9      10    
 
  
 
 
 
 
  
 
 
  
 
 
  
 
 
 47
 
 
 26
 
 
 60
 
 
  
 
 
  
 
 
 69
 
 
  
 
 
  
 
 
 
          （c） 用伪随机探测再散列处理冲突
 
  
 
                       图8.26开放地址法处理冲突
 
 从上述例子可以看出，线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。例如，当表中i, i+1 ,i+2三个单元已满时，下一个哈希地址为i, 或i+1 ,或i+2，或i+3的元素，都将填入i+3这同一个单元，而这四个元素并非同义词。线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。
 
 
 
 2. 再哈希法
 
     这种方法是同时构造多个不同的哈希函数：
 
     Hi=RH1（key）  i=1，2，…，k
 
 当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
 
 3. 链地址法
 
     这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
 
 例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图
 
  
 

 

 
 
 
  
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
 
 
 
 图链地址法处理冲突时的哈希表
 
 本例的平均查找长度 ASL=(1*7+2*4+3*1)=1.5
 
 4.建立公共溢出区
 
 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
 

  

 
 
 hash算法就学习总结到这里了，今天度过了22岁生日，晚上还是坚持完成了写这篇博客，今天暂时不写了，明天来总结Java中的hashcode和equals方法，
 
转载请指明出处http://blog.csdn.net/tanggao1314/article/details/51457585
 
参考资料
 
大话数据结
 
算法导论
 

 

HashMap中哈希算法的关键代码
 
//重新计算哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key如果是null 新hashcode是0 否则 计算新的hashcode
}

//计算数组槽位
 (n - 1) & hash
 
HashMap的细节我们不谈，只看这个哈希算法的细节(h = key.hashCode()) ^ (h >>> 16)
 
^按位异或运算，只要位不同结果为1，不然结果为0
 
>>> 无符号右移：右边补0
 
为什么要无符号右移16位后做异或运算
 
根据上面的说明我们做一个简单演练
 
 将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算，可以将高低位二进制特征混合起来
 
从上文可知高区的16位与原hashcode相比没有发生变化，低区的16位发生了变化
 
我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？
 
我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算，计算公式：(n - 1) & hash，假如这时数组槽位有16个，则槽位计算如下：
 
 仔细观察上文不难发现，高区的16位很有可能会被数组槽位数的二进制码锁屏蔽，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征
 
也许你可能会说，即使丢失了高区特征不同hashcode也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现
 
使用异或运算的原因
 
异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢
 
为什么槽位数必须使用2^n
 
1、为了让哈希后的结果更加均匀
 
这个原因我们继续用上面的例子来说明
 
假如槽位数不是16，而是17，则槽位计算公式变成：(17 - 1) & hash
 
 从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难
 
2、可以通过位运算e.hash & (newCap - 1)来计算，a % (2^n) 等价于 a & (2^n - 1) ，位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算
 
总结
 
说了这么多点，上面提到的所有问题，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率