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;

    }

}

 

参考链接：数据结构（严蔚敏）
一、什么是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,……,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
      
4
      
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)MOD m$m为表长

$d_i$有三种取法

1）线性探测再散列

$d_i=c*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

Hash(哈希)

Hash ：散列，通过关于键值(key)的函数，将数据映射到内存存储中一个位置来访问。这个过程叫做Hash，这个映射函数称做散列函数，存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()即请求对象的哈希值。

 

Hash的优点

先分类再查找，通过计算缩小范围，加快查找速度。

例：

集合：｛13,19,25,27，17｝

若是采用数组或链表结构：

访问其中的一个元素（如18），需要遍历整个集合的元素，时间复杂度为O(n).

而采用哈希表时:

假如散列函数为H[key] = key % 5；则集合元素对应的hash值分别为｛3,4,0,2,2｝。
访问元素（18）只需要在Hash值为2的集合中寻找即可.
如果访问没有哈希冲突的元素，例如访问（25），可以直接访问哈希值为（0）的值。
故hash时间复杂度最差才为O(n),最优情况下只需要O(1);
​

由上面的例子，我们可以想象，如果由大量的数据，采用数组或是链表存储时，访问需要遍历，耗费的时间非常多，而Hash表通过哈希计算，可以直接定位到数据所在位置（发生哈希冲突时，哈希值相同，可以定位到较小范围）大大加快了 查找的速度，节省了大量时间。

 

 

散列函数（Hash函数）

Hash通过Hash函数，将Key值映射为地址，Address = F[key];

常见的几种Hash函数：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法


	
直接定址法：取Key或者Key的某个线性函数值为散列地址。Hash(k) = k，或者Hash(k) = a*k + b, (a\b均为常数).

	
如下例所示：a = 1/100,b = -5.

	
Key
				
Hash(Key)
			
1005200
				
10047
			
3009800
				
30093
			
1506400
				
15059
			
7604300
				
76038
			
 
	
	

	
数字分析法：需要知道Key的集合，并且Key的位数比地址位数多，选择Key数字分布均匀的位。如下：

	
Hash(Key) 取六位：

	
列数 ： 1   (2)   3   (4)   5   (6)   (7)   8   (9)   10   11   12   (13)

	
key1：  5    2    4    2    7    5     8     5     3     6     5     1      3

	
key2：  5    4    4    8    7    7     7     5     4     8     9     5      1

	
key3：  3    1    5    3    7    8    5      4     6     3      5     5     2

	
key4：  5    3    6    4    3    2      5    4     5      3      2    6     4

	
 

	
其中(2、4、6、7、9、13) 这6列数字无重复，分布较均匀，取此六列作为Hash(Key)的值。

	
Hash(Key1) :225833

	
Hash(Key2):487741

	
Hash(Key3):138562

	
Hash(Key4):342554

	
 
	
	

	
平方取中法：取Key平方值的中间几位作为Hash地址。因为在设置散列函数时不一定知道所有关键字，选取哪几位不确定。一个数的平方的中间几位和数本身的每一位都有关，这样可以使随机分布的Key，得到的散列地址也是随机分布的 。如下：

	
Key
				
Key值平方
				
Hash地址(5位)
			
111112113
				
12345901655324769
				
01655
			
010111101
				
00102234363432201
				
34363
			
210222134
				
44193345623513956
				
45623
			
	

	
折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案.

	
具体的叠加方法有两种，移位法和折叠法：

	
例子：若Key为下列数串，地址位数为7，两种方法的Hash(key)分别如下：

	
Key：7982374 | 1861215 | 9892154 | 56923

	
 
				
移位折叠法：
				
 
				
折叠折叠法：
				
 
			
第一段
				
7982374
				
d1-dr
				
7982374
				
d1-dr
			
第二段
				
1861215
				
d(r+1)-d(2r)
				
5121681
				
d(2r)-d(r+1)
			
第三段
				
9892154
				
d(2r+1)-d(3r)
				
4512989
				
d(3r)-d(2r+1)
			
第四段
				
+ 56923
				
d(3r+1)-d(end)
				
+ 32965
				
d(end)-d(3r+1)
			
结果：
				
19792666
				
 
				
17650009
				
 
			
Hash(key):
				
9792666
				
 
				
7650009
				
 
			
	

	
随机数法：伪随机探测再散列

	
具体实现：建立一个伪随机数发生器，Hash(Key) = random(Key). 以此伪随机数作为哈希地址。
	
	

	
除留余数法：取关键字被某个除数 p 求余，得到的作为散列地址。

	
即 H(Key) = Key % p；

	
例子如下：

	
Key
				
P
				
Hash(Key) (4位)
			
11076302
				
1000
				
6302
			
13635279
				
1000
				
5279
			
41076553
				
1000
				
6553
			
76553027
				
1000
				
3027
			
以上就是6种构造哈希函数的方法，选择时要本着尽量减少产生冲突的原则，根据Key值的位数，分布情况，范围大小做出更优的选择。

 

哈希冲突

不管选用何种散列函数，不可避免的都会产生不同Key值对应同一个Hash地址的情况，这种情况叫做哈希冲突。

 

哈希冲突的处理

当冲突发生时，我们需要想办法解决冲突，一般常用的方法有：开放定址法、单独链表法、双散列法、再散列法以及建业公共溢出取等方法。


	
开放定址法：

	
当冲突发生时，探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址)，将数据存入。根据探测时使用的增量的取法，分为：线性探测、平方探测、伪随机探测等。

	
新的Hash地址函数为 Hash_new (Key) = (Hash(Key) + d i) mod m；i = 1，2...k (k<= m-1).m表示集合的元素数，i表示已经探测的次数。

	

		
线性探测(Linear Probing)

		
d i = a * i + b; a\b为常数。

		
相当于逐个探测地址列表，直到找到一个空置的，将数据放入。
		
		

		
平方探测(Quadratic Probing)

		
d i = a * i 2 (i <= m/2) m是Key集合的总数。a是常数。

		
探测间隔 i2 个单元的位置是否为空，如果为空，将地址存放进去。
		
		

		
伪随机探测

		
d i = random(Key);

		
探测间隔为一个伪随机数。

		
 

		
 
		
	
例子：

	
Key集合为(15,36,25,46,75)，采用除留余数法，模10 ，冲突时采用线性探测法d i = i;

	


	
如图，15和36放入时无冲突发生，分别对应地址 5 和6 。

	
但是当25放入时，Hash(25) = 25%10 = 5,和Key= 15发生冲突，则令d 1 = 1,Hash(25) = (25 + 1) %10 = 6.

	
此时已然与Key = 36发生冲突，令d 2 = 2，Hash(25) = (25+2) %10 = 7,无冲突，放入。

	
此后46,75也发生冲突，解决方法同上。
	
 


	
链表法

	
将散列到同一个位置的所有元素依次存储在单链表中，或者也有存储在栈中。具体实现根据实际情况决定这些元素的数据存储结构。

	
如下图所示：

	


	
首页Hash地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。T 中各分量的初值均应为空指针。

	
在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。

	
 

	
装填因子(载荷因子)

	
散列表的载荷因子定义为：

	
​ α = 填入表中的元素个数 / 散列表的长度.

	
α 是散列表装满程度的标志因子。由于表长是定值，α 与“填入表中的元素个数”成正比，所以，α 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α 的函数，只是不同处理冲突的方法有不同的函数。

	
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。
	

hash；简单的hash取余
优点：

计算简单，快速定位

缺点：

容错和扩展差，任何的增加机器或减少机器，都会伴随着重新set值

比如原来有五台机器做缓存，现在加一台，那么余5就变成余6，那么所有值都变了

操作不当的话短时间可能会造成缓存雪崩（一般只能成倍扩展）
一致性hash：hash环
想象一个环，共有2^32-1 个节点，如果有五台机器缓存，那么就将这五台的ip分别hash后对2^32-1取余，得到的结果肯定在这个环上，我们叫这个结果为落在某一个节点上

顺时针数，每个节点到前一个节点直接的值，将属于这个节点。

举个例子：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针行走，第一台遇到的服务器就是其应该定位到的服务器。

优点：

增加机器和减少机器，对整体影响不大，尤其是机器特别多的情况下，影响更小

缺点：

如果几个ip计算出来的节点不均匀，可能会出现缓存倾斜，比如一个机器上的缓存特别多，另一个机器上的缓存特别少

但是，针对这种问题，有成熟的解决方案，例如用虚拟节点。

比如现在有两个机器a,b，那么基本上肯定会出现缓存倾斜，那么我们就做出几个虚拟节点，a_1,a_2,a_3,b_1,b_2,b_3

用这些再做计算，基本上就可以做到相对平均了，

一般生产过程中，一个机器都会做出32个虚拟节点，来防止缓存倾斜
总结
简单常见用hash就行，重要场景考虑一致性hash