HashMap（一）

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

基于 jkd1.8 源码认识 HashMap。包含以下内容：

  1. 扰动函数
  2. 初始化容量
  3. 负载因子

扰动函数

在 HashMap 存放元素时候有这样一段代码来处理哈希值，用于优化散列效果：

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

1.运算符

  • >>>：无符号右移。无论是正数还是负数，高位通通补0；
  • ^：异或运算符。相同为 0，不同为 1；
  • &：与运算符。同为 1 时才为 1，否则为 0。

2.元素在数组中的位置

1
2
// 找到元素在数组中的位置，n为数组长度。
i = (n - 1) & hash

3.为什么 HashMap 数组的长度 n 要是2的整数幂

为使 hash 值散列分布在数组的下标当中。

假设我们有一个长度为16的数组，则他的下标范围为 0~15。而任何一个2的整数幂，减1得到的二进制位全部是1。让 hash 值与其就行与运算，结果将保留 hash 值小于数组下标范围的低位。当 hash 足够散列时，得到的结果必为在数组下标内散列的值。

1
2
3
4
    00100100 10100101 11000100 00100101    // Hash值
&   00000000 00000000 00000000 00001111    // 16 - 1 = 15
----------------------------------
    00000000 00000000 00000000 00000101    // 高位全部归零，只保留末四位。

4.扰动函数里为何无符号右移16位

为使 hash 值的高位也能影响到该元素在数组中的位置，提高散列性。

因为获取元素在数组中的位置时取的是 hash 值在数组下标范围内的低位，则将Hash值的高16位右移并与原Hash值取异或运算（^），混合高16位和低16位的值，会得到一个更加散列的低16位的Hash值。

初始化容量

在 HashMap 的初始化中，有这样一段方法：

1
2
3
4
5
public HashMap(int initialCapacity, float loadFactor) {
        ...
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

其中 threshold 的取值为比 initialCapacity 大的最小2的整数幂：

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

负载因子

负载因子决定了数据量达到多少了以后，hashmap 会进行扩容，默认值为 0.75。