了解理解 hashcode 和 hash 算法
摘要
- 二进制计算的一些基础知识
- 为什么使用 hashcode
- String 类型的 hashcode 方法
- 为什么大部分 hashcode 方法使用 31
- HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或）
- HashMap 为什么使用 & 与运算代替模运算？
- HashMap 的容量为什么建议是 2的幂次方？
- 我们自定义 HashMap 容量最好是多少？
-
Hash函数可以简单的划分为如下几类
1. 二进制计算的一些基础知识
首先，因为今天的文章会涉及到一些位运算，因此楼主怕大家忘了（其实楼主自己也忘了），因此贴出一些位运算符号的意思，以免看代码的时候懵逼。
好了，大概了解一下就好了，因为位运算平时在项目里真的用不上，在我们普通的业务项目里，代码易读性比这点位运算性能要重要的多。
2. 为什么使用 hashcode
那么我们就说说为什么使用 hashcode ，hashCode 存在的第一重要的原因就是在 HashMap(HashSet 其实就是HashMap) 中使用（其实Object 类的 hashCode 方法注释已经说明了 ），我知道，HashMap 之所以速度快，因为他使用的是散列表，根据 key 的 hashcode 值生成数组下标（通过内存地址直接查找，没有任何判断），时间复杂度完美情况下可以达到 n1（和数组相同，但是比数组用着爽多了，但是需要多出很多内存，相当于以空间换时间）。
3. String 类型的 hashcode 方法
JDK 中，我们经常把 String 类型作为 key，那么 String 类型是如何重写 hashCode 方法的呢？
我们看看代码：
代码非常简单，就是使用 String 的 char 数组的数字每次乘以 31 再叠加最后返回，因此，每个不同的字符串，返回的 hashCode 肯定不一样。那么为什么使用 31 呢？
4. 为什么大部分 hashcode 方法使用 31
在名著 《Effective Java》第 42 页就有对 hashCode 为什么采用 31 做了说明：
5. HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或）
好了，知道了 hashCode 的生成原理了，我们要看看今天的主角，hash 算法。
其实，这个也是数学的范畴，从我们的角度来讲，只要知道这是为了更好的均匀散列表的下标就好了，但是，就是耐不住好奇心啊！ 能多知道一点就是一点，我们来看看 HashMap 的 hash 算法（JDK 8）.
乍看一下就是简单的异或运算和右移运算，但是为什么要异或呢？为什么要移位呢？而且移位16？
在分析这个问题之前，我们需要先看看另一个事情，什么呢？就是 HashMap 如何根据 hash 值找到数组种的对象，我们看看 get 方法的代码：
我们看看代码中注释下方的一行代码：first = tab[(n - 1) & hash])。
使用数组长度减一 与运算 hash 值。这行代码就是为什么要让前面的 hash 方法移位并异或。
6. HashMap 为什么使用 & 与运算代替模运算？
好了，知道了 hash 算法的实现原理还有他的一些取舍，我们再看看刚刚说的那个根据hash计算下标的方法：
tab[(n - 1) & hash]；
其中 n 是数组的长度。其实该算法的结果和模运算的结果是相同的。但是，对于现代的处理器来说，除法和求余数（模运算）是最慢的动作。
上面情况下和模运算相同呢？
a % b == (b-1) & a ,当b是2的指数时，等式成立。
我们说 & 与运算的定义：与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0；
当 n 为 16 时， 与运算 101010100101001001101 时，也就是
1111 & 101010100101001001000 结果：1000 = 8
1111 & 101000101101001001001 结果：1001 = 9
1111 & 101010101101101001010 结果： 1010 = 10
1111 & 101100100111001101100 结果： 1100 = 12
7. HashMap 的容量为什么建议是 2的幂次方？
到这里，我们提了一个关键的问题： HashMap 的容量为什么建议是 2的幂次方？正好可以和上面的话题接上。楼主就是这么设计的。
为什么要 2 的幂次方呢？
我们说，hash 算法的目的是为了让hash值均匀的分布在桶中（数组），那么，如何做到呢？试想一下，如果不使用 2 的幂次方作为数组的长度会怎么样？
假设我们的数组长度是10，还是上面的公式：
1010 & 101010100101001001000 结果：1000 = 8
1010 & 101000101101001001001 结果：1000 = 8
1010 & 101010101101101001010 结果： 1010 = 10
1010 & 101100100111001101100 结果： 1000 = 8
8. 我们自定义 HashMap 容量最好是多少？
那我们如何自定义呢？自从有了阿里的规约插件，每次楼主都要初始化容量，如果我们预计我们的散列表中有2个数据，那么我就初始化容量为2嘛？
绝对不行，如果大家看过源码就会发现，如果Map中已有数据的容量达到了初始容量的 75%，那么散列表就会扩容，而扩容将会重新将所有的数据重新散列，性能损失严重，所以，我们可以必须要大于我们预计数据量的 1.34 倍，如果是2个数据的话，就需要初始化 2.68 个容量。当然这是开玩笑的，2.68 不可以，3 可不可以呢？肯定也是不可以的，我前面说了，如果不是2的幂次方，散列结果将会大大下降。导致出现大量链表。那么我可以将初始化容量设置为4。 当然了，如果你预计大概会插入 12 条数据的话，那么初始容量为16简直是完美，一点不浪费，而且也不会扩容。
9.Hash函数可以简单的划分为如下几类
1. 加法Hash；
2. 位运算Hash；
3. 乘法Hash；
4. 除法Hash；
5. 查表Hash；
6. 混合Hash；
下面详细的介绍以上各种方式在实际中的运用。
一 加法Hash
所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下：
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);
}
这里的prime是任意的质数，看得出，结果的值域为[0,prime-1]。
二 位运算Hash
这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。比如，标准的旋转Hash的构造如下：
static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i
hash = (hash<<4>>28)^key.charAt(i);
return (hash % prime);
}
先移位，然后再进行各种位运算是这种类型Hash函数的主要特点。比如，以上的那段计算hash的代码还可以有如下几种变形：
hash = (hash<<5>>27)^key.charAt(i);
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
if((i&1) == 0)
{
hash ^= (hash<<7>>3);
}
else
{
hash ^= ~((hash<<11>>5));
}
hash += (hash<<5>
hash = key.charAt(i) + (hash<<6>>16) ? hash;
hash ^= ((hash<<5>>2));
三 乘法Hash
这种类型的Hash函数利用了乘法的不相关性（乘法的这种性质，最有名的莫过于平方取头尾的随机数生成算法，虽然这种算法效果并不好）。比如，
static int bernstein(String key)
{
int hash = 0;
int i;
for (i=0; i
return hash;
}
jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过，它使用的乘数是31。推荐的乘数还有：131, 1313, 13131, 131313等等。
使用这种方式的著名Hash函数还有：
// 32位FNV算法
int M_SHIFT = 0;
public 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;
}
以及改进的FNV算法：
public static int FNVHash1(String data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(int i=0;i
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
除了乘以一个固定的数，常见的还有乘以一个不断改变的数，比如：
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);
}
总结
好了，分析完了 hashCode 和 hash 算法，让我们对 HashMap 又有了全新的认识。当然，HashMap 中还有很多有趣的东西值得挖掘，楼主会继续写下去。争取将 HashMap 的衣服扒光。
总的来说，通过今天的分析，对我们今后使用 HashMap 有了更多的把握，也能够排查一些问题，比如链表数很多，肯定是数组初始化长度不对，如果某个map很大，注意，肯定是事先没有定义好初始化长度，假设，某个Map存储了10000个数据，那么他会扩容到 20000，实际上，根本不用 20000，只需要 10000* 1.34= 13400 个，然后向上找到一个2 的幂次方，也就是 16384 初始容量足够。