首页 JDK 源码

# jdk1.8 HashMap 中 hash 值计算源码

1
2
3
4
5
6
7
8
9
10
/**
 * 扰动函数
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 其中的key.hashCode调用的是底层的native方法。
public native int hashCode();
  • Q: 为什么不直接使用 key 的 hashCode 值呢？

如果直接使用 key 的 hashCode () 函数的时候，将 hash 值作下标访问 Map 的数组的话，由于 2 进制的取值范围是 [-231,231), 加起来大于有 40 亿的映射空间。只要 hash 函数散列的比较松散，那么久很难出现碰撞。当然，40 亿的数据，内存也是放不下的。所以不能直接拿 key 的 hashCode。

  • Q: 为什么要进行 h = key.hashCode()) ^ (h >>> 16) 这个运算呢？

这个问题就要从计算出的 hash 值的作用上来切入了，hashMap 计算这个 hash 值就是为了什么？增删改查的时候确定元素在数组中的位置。那么 hashMap 是怎么确定位置的呢？我们知道 HashMap 中的数组是 tab 字段。根据 tab 找到，在 final HashMap.Node<K,V> getNode(int hash, Object key) 方法中，有这么 tab[(n - 1) & hash] 使用。 n 是数组的长度.
这里 n-1 相当于一个 低位掩码 ，和 hash 进行与操作的结果就是散列值的高位全部归零，保留低位，用来做下标访问。这么看，就算我们的 hash 散列分布再松散，冲突也会很严重。以默认长度 16 为例。

1
2
3
4
  11111111  11111111 11110000 11101010  # native方法 HashCode()
& 00000000  00000000 00000000 00001111  # 默认初始长度 15 = 16 -1
  -------------------------------------
  00000000  00000000 00000000 00001010  # 进行&操作，计算出的下标为10

我们看下使用扰动函数计算后的结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 扰动函数计算过程:
   h=hashCode():  11111111  11111111  11110000  11101010  # native方法 HashCode()
   -------------------------------------------------------------------------------
              h:  11111111  11111111  11110000  11101010  # native方法 HashCode()计算出的值。
   ^     h>>>16:  00000000  00000000  11111111  11111111  # hashCode左移16位=>高16位变低位
   -----------------------------------------------------------------------------------
hash=h^(h>>>16):  11111111  11111111  00001111  00010101  # 扰动函数计算出的值


# 与掩码做&运算=>计算数组下标
hash=h^(h>>>16):  11111111  11111111  00001111  00010101  # 扰动函数计算出的值
            &  :  00000000  00000000  00000000  00001111  # 低位掩码=> hashMap中数组的长度
    -----------------------------------------------------------------------------------
                             ....                  00101  # =>计算出的下标为5.

# Peter Lawley 的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验

hashMap扰动函数的作用.png

结果显示，当 HashMap 数组长度为 512 的时候，也就是用掩码取低 9 位的时候，在没有扰动函数的情况下，发生了 103 次碰撞，接近 30%。而在使用了扰动函数之后只有 92 次碰撞。碰撞减少了将近 10%。看来扰动函数确实还是有功效的。

# JDK7 中的 HashMap 计算 hash 的方式

# 参考文章

HashMap 中的 hash 函数

# 最后

期望与你一起遇见更好的自己

期望与你一起遇见更好的自己