HashMap源码(上)

HashMap 最早出现在JDK1.2中，底层基于散列算法实现

  • HashMap 允许null 键和null 值，在计算哈键的哈希值时，null 键哈希值为0。
  • HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。
  • HashMap 是非线程安全类，在多线程环境下可能会存在问题。

HashMap在JDK 1.8中包括；1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分、6、链表树化、7、红黑树、8、插入、9、查找、10、删除、11、遍历、12、分段锁等等
这里我们先把目光放在前五项上，也就是关于数据结构的使用上。

散列表实现（一个简单的HashMap）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        list.add("one");
        list.add("power");
        list.add("technology");
        list.add("environment");
        list.add("hello");
        list.add("world");

        String[] tab = new String[list.size()];

        for (String value : list) {
            // 计算索引: 指定value的hash值 按位与 tab最大下标 保证不越界
            int key = value.hashCode() & (tab.length - 1);
            System.out.println(String.format("key: %d, value: %s",key,value));
            // 如果数组当前索引中不存在value,赋值
            if (null == tab[key]) {
                tab[key] = value;
                continue;
            }
            // 存在则将其链接起来
            tab[key] = tab[key]+ "->"+ value;
        }

        System.out.println(Arrays.toString(tab));
    }
}

hashmap-simple

所存在的问题

  1. 所有的元素存放都需要一个索引位置，如果索引位置不够导致散列碰撞严重，那就没有达到预期的性能，也就失去了散列表的意义
  2. 在获取索引 ID 的计算公式中，需要数组长度是 2 的倍数（需要保证能进行按位与操作不越界），数组大小如何设定？
  3. 数组越小碰撞越大，数组越大碰撞越小，如何取舍时间与空间？
  4. 目前存放 7 个元素，已经有两个位置都存放了 2 个字符串，那么链表越来越长怎么优化？
  5. 随着元素的不断添加，数组长度不足扩容时，怎么把原有的元素拆分到新的位置上去？

以上这些问题可以归纳为；扰动函数、初始化容量、负载因子、扩容方法以及链表和红黑树转换的使用等。

扰动函数

hashmap-扰动函数
在 HashMap 存放元素时候有这样一段代码来处理哈希值，这是 Java 8 的散列值扰动函数，用于优化散列效果。
理论上来说字符串的 hashCode是一个 int 类型值，那可以直接作为数组下标了，且不会出现碰撞。但是这个 hashCode 的取值范围是[-2147483648, 2147483647]， 有将近 40 亿的长度，谁也不能把数组初始化的这么大，内存也是放不下的。 我们默认初始化的 Map 大小是 16 个长度。DEFAULT_INITIAL_CAPACITY = 1 << 4， 所以获取的 Hash 值并不能直接作为下标使用，需要与数组长度进行取模运算得到一个下标值，也就是我们上面做的散列列子。
hashMap 源码这里不只是直接获取哈希值，还进行了一次扰动计算，(h = key.hashCode()) ^ (h >>> 16)。把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。
HashMap-扰动函数.drawio
使用扰动函数就是为了增加随机性，让数据元素更加均衡的散列，减少hash碰撞，让数据存放和获取的效率更好

初始化容量

散列数组需要一个 2 的倍数的长度，因为只有 2 的 倍数在减 1 的时候，才会出现 01111 这样的值。那么这里就有一个问题，我们在初始化 HashMap 的时候，如果传一个 17 个的值 new HashMap<>(17);，它会怎么处理呢？

寻找最小二进制数

hashmap-寻找最小2的n方数

  • 在 HashMap 的初始化中，阀值 threshold，通过方法 tableSizeFor 进行计算，是根据初始化大小来计算的。
  • 这个方法也就是要寻找比初始值大的，最小的那个 2 进制数值。比如传了 17，我应该找到的是 32。

计算阀值大小的方法：
hashmap-tableSizeFor

  • MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最大容量。
  • 乍一看可能有点晕😵怎么都在向右移位 1、2、4、8、16，这主要是为了 把二进制的各个位置都填上 1，当二进制的各个位置都是 1 以后，就是 一个标准的 2 的倍数减 1 了，最后把结果加 1 再返回即可。

HashMap-计算阈值.drawio

负载因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子，可以理解成一辆车可承重重量超过某个阀值时，把货放到新的车上。
在 HashMap 中，负载因子决定了数据量多少了以后进行扩容。
这里要提到上面做的 HashMap 例子，我们准备了 6 个元素，但是最后还有 2 个位置空余，2 个
位置存放了 2 个元素。
所以可能即使你数据与数组容量一样大时也不一定能正正好好的把数组占满的，而是在某些小标位置出现了大量的碰撞，只能在同一个位置用链表存放，那么这样就失去了 Map 数组的性能。
要选择一个合理的大小下进行扩容，默认值 0.75 就是说当阀值容量占了 3/4 时赶紧扩容，减少 Hash 碰撞。同时 0.75 是一个默认构造值，在创建 HashMap 也可以调整，比如你希望用更多的空间换取时间，可以把负载因子调的更小一些，减少碰撞。

扩容元素拆分

为什么扩容，因为数组长度不足了。那扩容最直接的问题，就是需要把元素拆分到新的数组中。拆分元素的过程中，原 jdk1.7 中会需要重新计算哈希值，但是到 jdk1.8 中已经进行优化，不在需要重新计算，提升了拆分的性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        list.add("one");
        list.add("power");
        list.add("technology");
        list.add("environment");
        list.add("hello");
        list.add("world");
        list.add("good");
        list.add("sad");
        list.add("god");
        list.add("yeah");
        list.add("uncle");
        list.add("Java");
        list.add("PHP");
        list.add("C#");
        list.add("C");
        list.add("Python");
        list.add("GO");

        for (String value : list) {
            int hash = value.hashCode() ^ (value.hashCode() >>> 16);
            int key16 = hash & (16 - 1);
            int key32 = hash & (32 - 1);
            System.out.println(
                "value:" + value +
                "\n\tkey(16):" + key16 +
                "\tBit值:" + Integer.toBinaryString(hash) + " - " + Integer.toBinaryString(hash & 16) +
                "\n\tkey(32):" + key32 +
                "\tBit值:" + Integer.toBinaryString(hash) + " - " + Integer.toBinaryString(hash & (32 - 1))
            );
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
value:one
key(16):7	Bit值:11010111001100111 - 0
key(32):7	Bit值:11010111001100111 - 111
value:power
key(16):11	Bit值:110010111101000111101011011 - 10000
key(32):27	Bit值:110010111101000111101011011 - 11011
value:technology
key(16):11	Bit值:10011011111001110001111011101011 - 0
key(32):11	Bit值:10011011111001110001111011101011 - 1011
value:environment
key(16):2	Bit值:11111010111000011100100011110010 - 10000
key(32):18	Bit值:11111010111000011100100011110010 - 10010
value:hello
key(16):11	Bit值:101111010010001110100111011 - 10000
key(32):27	Bit值:101111010010001110100111011 - 11011
value:world
key(16):3	Bit值:110110000010001110101010011 - 10000
key(32):19	Bit值:110110000010001110101010011 - 10011
value:good
key(16):13	Bit值:1100001000000010001101 - 0
key(32):13	Bit值:1100001000000010001101 - 1101
value:sad
key(16):7	Bit值:11011101111010111 - 10000
key(32):23	Bit值:11011101111010111 - 10111
value:god
key(16):13	Bit值:11001000001111101 - 10000
key(32):29	Bit值:11001000001111101 - 11101
value:yeah
key(16):11	Bit值:1110001000100000001011 - 0
key(32):11	Bit值:1110001000100000001011 - 1011
value:uncle
key(16):7	Bit值:110101001000011100101000111 - 0
key(32):7	Bit值:110101001000011100101000111 - 111
value:Java
key(16):1	Bit值:1000110001111001100001 - 0
key(32):1	Bit值:1000110001111001100001 - 1
value:PHP
key(16):9	Bit值:10011010101011001 - 10000
key(32):25	Bit值:10011010101011001 - 11001
value:C#
key(16):0	Bit值:100001000000 - 0
key(32):0	Bit值:100001000000 - 0
value:C
key(16):3	Bit值:1000011 - 0
key(32):3	Bit值:1000011 - 11
value:Python
key(16):15	Bit值:10001111011000111001001110011111 - 10000
key(32):31	Bit值:10001111011000111001001110011111 - 11111
value:GO
key(16):8	Bit值:100011101000 - 0
key(32):8	Bit值:100011101000 - 1000

Process finished with exit code 0

这里我们随机使用一些字符串计算他们分别在 16 位长度和 32 位长度数组下的索引分配情况，看哪些数据被重新路由到了新的地址
同时，这里还可以观察出一个非常重要的信息，原哈希值与扩容新增出来的长度 16，进行&运算，如果值等于 0，则下标位置不变。如果不为 0，那么新的位置则是原来位置上加 16。多次测试发现这里的16可以扩展为 2 的n次方。即：
原哈希值（扰动哈希）与扩容新增出来的长度 2 的 n 次方，进行&运算

  • 如果值等于 0，则下标位置不变。
  • 如果不为 0，那么新的位置则是原来位置上加 2 的 n 次方。

由此可见,java 8 的散列值扰动函数，在优化散列效果的同时，也让扩容元素变得更加的方便。

补充：

hashCode的计算逻辑中，为什么是31作为乘数?

hashcode源码

在获取hashCode的源码中可以看到，有一个固定值31，在for循环每次执行时进行乘积计算，循环后的公式：s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]

那么这里为什么选择31作为乘积值呢？

  1. 31作为一个奇质数，如果选择偶数会导致乘积运算数据溢出
  2. 在2进制中，2的5次方是32，也就是 31i == （i<<5）-1; ，这主要是说明乘积运算可以用位移提升性能。同时*JVM虚拟机也自动支持这类优化
  3. 在不同的乘数下测试hash碰撞的结果发现：当31作为乘数时，碰撞概率很小，基本稳定，再往下走，199的碰撞概率虽然更小，但乘积运算之后的范围值已经完全超过int的取值范围【-2^31 ~ 2^31-1】，如果用 199 这个数，再返回int值，就会发生数据丢失的问题。所以我们选择碰撞概率较小 ，且乘积运算之后在int范围内的最小数。也就是31
  4. 31作为乘数时，数据更加分散，散列分布的效果更明显，基本在每个范围内都有数据存放