知识点

Map 中的 hash 算法

1. hash

1.散列值

把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间。

根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

2.常用的哈希函数

  • 直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址
  • 数字分析法：提取关键字中取值比较均匀的数字作为哈希地址
  • 除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址
  • 分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址
  • 平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址
  • 伪随机数法：采用一个伪随机数当作哈希函数

3.碰撞

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。

解决碰撞的方法：

  • 开放定址法：就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
  • 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
  • 再哈希法：当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。
  • 建立公共溢出区：将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

2. HashMap 的数据结构

hash01

3. hash方法

以 JDK 1.7 的 HashMap 为例，其中定义了一个 final int hash(Object k) 方法，其主要被以下方法引用。

hash02

上面的方法主要都是增加和删除方法，当我们要对一个链表数组中的某个元素进行增删的时候，首先要知道他应该保存在这个链表数组中的哪个位置，即他在这个数组中的下标。而 hash() 方法的功能就是根据 Key 来定位其在 HashMap 中的位置。HashTable、ConcurrentHashMap 同理。

4. 源码解析

在同一个版本的 JDK 中，HashMap、HashTable 以及 ConcurrentHashMap 里面的 hash 方法的实现是不同的。在不同的版本的JDK中（Java7 和 Java8）中也是有区别的。

1. 基本原理

调用 Object 对象的 hashCode() 方法，该方法会返回一个整数，然后用这个数对 HashMap 或者 HashTable 的容量进行取模。在具体实现上，由两个方法 int hash(Object k) 和 int indexFor(int h, int length) 来实现。但是考虑到效率等问题，HashMap 的实现会稍微复杂一点。

  • hash ：该方法主要是将 Object 转换成一个整型
  • indexFor ：该方法主要是将 hash 生成的整型转换成链表数组中的下标

5. HashMap In Java 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
   int h = hashSeed;
   if (0 != h && k instanceof String) {
       return sun.misc.Hashing.stringHash32((String) k);
   }

   h ^= k.hashCode();
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
   return h & (length-1);
}

1. int indexFor(int h, int length)

return h & (length-1) 就是取模。使用位运算(&)来代替取模运算(%)以提供效率。

只要保证 length 的长度是 2n 的话，就可以实现取模运算了。HashMap 中的 length 也确实是 2 的倍数，初始值是 16，之后每次扩充为原来的 2 倍。

使用位运算代替取模运算，除了性能之外，还有一个好处就是可以很好的解决负数的问题。因为 hashcode 的结果是 int 类型，而 int 的取值范围是 -231 ~ 231 - 1，即 [-2147483648, 2147483647]，其中包含负数，对于一个负数取模比较麻烦。

如果使用二进制的位运算的话就可以很好的避免这个问题。

  1. 无论 hashcode 的值是正数还是负数。length-1 这个值一定是个正数
  2. 它的二进制的第一位一定是0（有符号数用最高位作为符号位，“0”代表“+”，“1”代表“-”）
  3. 这样两个数做按位与运算之后，第一位一定是个0，也就是得到的结果一定是个正数

2. int hash(Object k)

由于 HashMap 使用位运算代替了取模运算，这有可能发生冲突。

1
2
3
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

这段代码是为了对 key 的 hashCode 进行扰动计算，防止不同 hashCode 的高位不同但低位相同导致的hash冲突。

hash03

经过扰动的算法最终的计算结果：

hash04

6. HashTable In Java 7

以下是Java 7中线程安全HashTable的hash方法的实现。

1
2
3
4
private int hash(Object k) {
    // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

相当于只是对 k 做了个简单的 hash，取了一下其 hashCode。而 HashTable 中也没有 indexOf 方法，取而代之的是这段代码：

1
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap 和 HashTable 对于计算数组下标这件事，采用了两种方法。HashMap采用的是位运算，而 HashTable 采用的是直接取模。

hash 值和 0x7FFFFFFF 做一次按位与操作，主要是为了保证得到的 index 的的二进制的第一位为0（一个32位的有符号数和0x7FFFFFFF做按位与操作，其实就是在取绝对值。），也就是为了得到一个正数。

HashTable 简单的取模是有一定的考虑在的。这就要涉及到HashTable的构造函数和扩容函数了。

HashTable 默认的初始大小为 11，之后每次扩充为原来的 2n+1。也就是说，HashTable 的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。由于 HashTable 会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。

7. .ConcurrentHashMap In Java 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int hash(Object k) {
   int h = hashSeed;

   if ((0 != h) && (k instanceof String)) {
       return sun.misc.Hashing.stringHash32((String) k);
   }

   h ^= k.hashCode();

   // Spread bits to regularize both segment and index locations,
   // using variant of single-word Wang/Jenkins hash.
   h += (h <<  15) ^ 0xffffcd7d;
   h ^= (h >>> 10);
   h += (h <<   3);
   h ^= (h >>>  6);
   h += (h <<   2) + (h << 14);
   return h ^ (h >>> 16);
}

int j = (hash >>> segmentShift) & segmentMask;

上面这段关于 ConcurrentHashMap 的 hash 实现其实和 HashMap 如出一辙。都是通过位运算代替取模，然后再对 hashcode 进行扰动。区别在于，ConcurrentHashMap 使用了一种变种的 Wang/Jenkins 哈希算法，其主要目的也是为了把高位和低位组合在一起，避免发生冲突。至于为啥不和 HashMap 采用同样的算法进行扰动，可能是程序员个人的选择吧。

8. HashMap In Java 8

在 Java 8 之前，HashMap 和其他基于 map 的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。

为了解决在频繁冲突时hashmap性能降低的问题，Java 8 中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。

如果恶意程序知道我们用的是Hash算法，则在纯链表情况下，它能够发送大量请求导致哈希碰撞，然后不停访问这些 key 导致 HashMap 忙于进行线性查找，最终陷入瘫痪，即形成了拒绝服务攻击（DoS）。

关于 Java 8 中的 hash 函数，原理和 Java 7 中基本类似。Java 8 中这一步做了优化，只做一次 16 位右位移异或混合，而不是四次，但原理是不变的。

1
2
3
4
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode() 的高 16 位异或低 16 位实现的 (h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的。以上方法得到的 int 的 hash 值，然后再通过 h & (table.length -1) 来得到该对象在数据中保存的位置。

9. HashTable In Java 8

在 Java 8 的 HashTable 中，已经不在有 hash 方法了。但是哈希的操作还是在的，比如在 put 方法中就有如下实现：

1
2
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

10. ConcurrentHashMap In Java 8

Java 8 里面的求 hash 的方法从 hash 改为了 spread。实现方式如下：

1
2
3
static final int spread(int h) {
  return (h ^ (h >>> 16)) & HASH_BITS;
}

Java 8 的 ConcurrentHashMap 同样是通过 Key 的哈希值与数组长度取模确定该Key在数组中的索引。

不同的是，Java 8 的 ConcurrentHashMap 作者认为引入红黑树后，即使哈希冲突比较严重，寻址效率也足够高，所以作者并未在哈希值的计算上做过多设计，只是将 Key 的 hashCode 值与其高 16 位作异或并保证最高位为0（从而保证最终结果为正整数）。