发表更新1 小时读完 (大约9856个字)0次访问

【Java】HashMap核心原理解读

InterviewCoder

# 【Java】HashMap 核心原理解读

# 一、前言

得益于 Doug Lea 老爷子的操刀，让 HashMap 成为使用和面试最频繁的 API，没办法设计的太优秀了！

HashMap 最早出现在 JDK 1.2 中，底层基于散列算法实现。HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。

# 二、源码分析

# 1. 写一个最简单的 HashMap

学习 HashMap 前，最好的方式是先了解这是一种怎么样的数据结构来存放数据。而 HashMap 经过多个版本的迭代后，乍一看代码还是很复杂的。就像你原来只穿个裤衩，现在还有秋裤和风衣。所以我们先来看看最根本的 HashMap 是什么样，也就是只穿裤衩是什么效果，之后再去分析它的源码。

问题： 假设我们有一组 7 个字符串，需要存放到数组中，但要求在获取每个元素的时候时间复杂度是 O (1)。也就是说你不能通过循环遍历的方式进行获取，而是要定位到数组 ID 直接获取相应的元素。

方案： 如果说我们需要通过 ID 从数组中获取元素，那么就需要把每个字符串都计算出一个在数组中的位置 ID。字符串获取 ID 你能想到什么方式？ 一个字符串最直接的获取跟数字相关的信息就是 HashCode，可 HashCode 的取值范围太大了 [-2147483648, 2147483647] ，不可能直接使用。那么就需要使用 HashCode 与数组长度做与运算，得到一个可以在数组中出现的位置。如果说有两个元素得到同样的 ID，那么这个数组 ID 下就存放两个字符串。

以上呢其实就是我们要把字符串散列到数组中的一个基本思路，接下来我们就把这个思路用代码实现出来。

# 1.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
// 初始化一组字符串
List<String> list = new ArrayList<>();
list.add("jlkk");
list.add("lopi");
list.add("小傅哥");
list.add("e4we");
list.add("alpo");
list.add("yhjk");
list.add("plop");

// 定义要存放的数组
String[] tab = new String[8];

// 循环存放
for (String key : list) {
    int idx = key.hashCode() & (tab.length - 1);  // 计算索引位置
    System.out.println(String.format("key值=%s Idx=%d", key, idx));
    if (null == tab[idx]) {
        tab[idx] = key;
        continue;
    }
    tab[idx] = tab[idx] + "->" + key;
}
// 输出测试结果
System.out.println(JSON.toJSONString(tab));

这段代码整体看起来也是非常简单，并没有什么复杂度，主要包括以下内容；

  1. 初始化一组字符串集合，这里初始化了 7 个。
  2. 定义一个数组用于存放字符串，注意这里的长度是 8，也就是 2 的 3 次幂。这样的数组长度才会出现一个 0111 除高位以外都是 1 的特征，也是为了散列。
  3. 接下来就是循环存放数据，计算出每个字符串在数组中的位置。 key.hashCode() & (tab.length - 1) 。
  4. 在字符串存放到数组的过程，如果遇到相同的元素，进行连接操作 模拟链表的过程 。
  5. 最后输出存放结果。

测试结果

1
2
3
4
5
6
7
8
key值=jlkk Idx=2
key值=lopi Idx=4
key值=小傅哥 Idx=7
key值=e4we Idx=5
key值=alpo Idx=2
key值=yhjk Idx=0
key值=plop Idx=5
测试结果：["yhjk",null,"jlkk->alpo",null,"lopi","e4we->plop",null,"小傅哥"]
  • 在测试结果首先是计算出每个元素在数组的 Idx，也有出现重复的位置。
  • 最后是测试结果的输出，1、3、6，位置是空的，2、5，位置有两个元素被链接起来 e4we->plop 。
  • 这就达到了我们一个最基本的要求，将串元素散列存放到数组中，最后通过字符串元素的索引 ID 进行获取对应字符串。这样是 HashMap 的一个最基本原理，有了这个基础后面就会更容易理解 HashMap 的源码实现。

# 1.2 Hash 散列示意图

如果上面的测试结果不能在你的头脑中很好的建立出一个数据结构，那么可以看以下这张散列示意图，方便理解；

bugstack.cn Hash散列示意图

  • 这张图就是上面代码实现的全过程，将每一个字符串元素通过 Hash 计算索引位置，存放到数组中。
  • 黄色的索引 ID 是没有元素存放、绿色的索引 ID 存放了一个元素、红色的索引 ID 存放了两个元素。

# [#](https://bugstack.cn/md/java/interview/2020-08-07 - 面经手册・第 3 篇《HashMap 核心知识，扰动函数、负载因子、扩容链表拆分，深度学习》.html#_1-3 - 这个简单的 hashmap 有哪些问题) 1.3 这个简单的 HashMap 有哪些问题

以上我们实现了一个简单的 HashMap，或者说还算不上 HashMap，只能算做一个散列数据存放的雏形。但这样的一个数据结构放在实际使用中，会有哪些问题呢？

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

以上这些问题可以归纳为； 扰动函数 、 初始化容量 、 负载因子 、 扩容方法 以及 链表和红黑树 转换的使用等。接下来我们会逐个问题进行分析。

# 2. 扰动函数

在 HashMap 存放元素时候有这样一段代码来处理哈希值，这是 java 8 的散列值扰动函数，用于优化散列效果；

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

# 2.1 为什么使用扰动函数

理论上来说字符串的 hashCode 是一个 int 类型值，那可以直接作为数组下标了，且不会出现碰撞。但是这个 hashCode 的取值范围是 [-2147483648, 2147483647]，有将近 40 亿的长度，谁也不能把数组初始化的这么大，内存也是放不下的。

我们默认初始化的 Map 大小是 16 个长度 DEFAULT_INITIAL_CAPACITY = 1 << 4 ，所以获取的 Hash 值并不能直接作为下标使用，需要与数组长度进行取模运算得到一个下标值，也就是我们上面做的散列列子。

那么，hashMap 源码这里不只是直接获取哈希值，还进行了一次扰动计算， (h = key.hashCode()) ^ (h >>> 16) 。把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。计算方式如下图；

bugstack.cn 扰动函数

  • 说白了，使用扰动函数就是为了增加随机性，让数据元素更加均衡的散列，减少碰撞。

# 2.2 实验验证扰动函数

从上面的分析可以看出，扰动函数使用了哈希值的高半区和低半区做异或，混合原始哈希码的高位和低位，以此来加大低位区的随机性。

但看不到实验数据的话，这终究是一段理论，具体这段哈希值真的被增加了随机性没有，并不知道。所以这里我们要做一个实验，这个实验是这样做；

  1. 选取 10 万个单词词库
  2. 定义 128 位长度的数组格子
  3. 分别计算在扰动和不扰动下，10 万单词的下标分配到 128 个格子的数量
  4. 统计各个格子数量，生成波动曲线。如果扰动函数下的波动曲线相对更平稳，那么证明扰动函数有效果。
# 2.2.1 扰动代码测试

扰动函数对比方法

1
2
3
4
5
6
7
8
9
10
11
public class Disturb {

    public static int disturbHashIdx(String key, int size) {
        return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));
    }

    public static int hashIdx(String key, int size) {
        return (size - 1) & key.hashCode();
    }

}
  • disturbHashIdx 扰动函数下，下标值计算
  • hashIdx 非扰动函数下，下标值计算

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 10万单词已经初始化到words中
@Test
public void test_disturb() {
    Map<Integer, Integer> map = new HashMap<>(16);
    for (String word : words) {
        // 使用扰动函数
        int idx = Disturb.disturbHashIdx(word, 128);
        // 不使用扰动函数
        // int idx = Disturb.hashIdx(word, 128);
        if (map.containsKey(idx)) {
            Integer integer = map.get(idx);
            map.put(idx, ++integer);
        } else {
            map.put(idx, 1);
        }
    }
    System.out.println(map.values());
}

以上分别统计两种函数下的下标值分配，最终将统计结果放到 excel 中生成图表。

# [#](https://bugstack.cn/md/java/interview/2020-08-07 - 面经手册・第 3 篇《HashMap 核心知识，扰动函数、负载因子、扩容链表拆分，深度学习》.html#_2-2-2 - 扰动函数散列图表) 2.2.2 扰动函数散列图表

以上的两张图，分别是没有使用扰动函数和使用扰动函数的，下标分配。实验数据；

  1. 10 万个不重复的单词
  2. 128 个格子，相当于 128 长度的数组

未使用扰动函数

bugstack.cn 未使用扰动函数

使用扰动函数

bugstack.cn 使用扰动函数

  • 从这两种的对比图可以看出来，在使用了扰动函数后，数据分配的更加均匀了。
  • 数据分配均匀，也就是散列的效果更好，减少了 hash 的碰撞，让数据存放和获取的效率更佳。

# 3. 初始化容量和负载因子

接下来我们讨论下一个问题，从我们模仿 HashMap 的例子中以及 HashMap 默认的初始化大小里，都可以知道，散列数组需要一个 2 的幂次方的长度，因为只有 2 的幂次方在减 1 的时候，才会出现 01111 这样的值。

那么这里就有一个问题，我们在初始化 HashMap 的时候，如果传一个 17 个的值 new HashMap<>(17); ，它会怎么处理呢？

# 3.1 寻找 2 的幂次方最小值

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

1
2
3
4
5
public HashMap(int initialCapacity, float loadFactor) {
    ...
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
  • 阈值 threshold ，通过方法 tableSizeFor 进行计算，是根据初始化来计算的。
  • 这个方法也就是要寻找比初始值大的，最小的那个 2 进制数值。比如传了 17，我应该找到的是 32（2 的 4 次幂是 16<17, 所以找到 2 的 5 次幂 32）。

计算阈值大小的方法；

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;
}
  • MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最大的 Map 集合。
  • 乍一看可能有点晕😵怎么都在向右移位 1、2、4、8、16，这主要是为了把二进制的各个位置都填上 1，当二进制的各个位置都是 1 以后，就是一个标准的 2 的幂次方减 1 了，最后把结果加 1 再返回即可。

那这里我们把 17 这样一个初始化计算阈值的过程，用图展示出来，方便理解；

bugstack.cn 计算阈值

# 3.2 负载因子

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子是做什么的？

负载因子，可以理解成一辆车可承重重量超过某个阈值时，把货放到新的车上。

那么在 HashMap 中，负载因子决定了数据量多少了以后进行扩容。这里要提到上面做的 HashMap 例子，我们准备了 7 个元素，但是最后还有 3 个位置空余，2 个位置存放了 2 个元素。 所以可能即使你数据比数组容量大时也是不一定能正正好好的把数组占满的，而是在某些小标位置出现了大量的碰撞，只能在同一个位置用链表存放，那么这样就失去了 Map 数组的性能。

所以，要选择一个合理的大小下进行扩容，默认值 0.75 就是说当阈值容量占了 3/4 时赶紧扩容，减少 Hash 碰撞。

同时 0.75 是一个默认构造值，在创建 HashMap 也可以调整，比如你希望用更多的空间换取时间，可以把负载因子调的更小一些，减少碰撞。

# 4. 扩容元素拆分

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

# 4.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
@Test
public void test_hashMap() {
    List<String> list = new ArrayList<>();
    list.add("jlkk");
    list.add("lopi");
    list.add("jmdw");
    list.add("e4we");
    list.add("io98");
    list.add("nmhg");
    list.add("vfg6");
    list.add("gfrt");
    list.add("alpo");
    list.add("vfbh");
    list.add("bnhj");
    list.add("zuio");
    list.add("iu8e");
    list.add("yhjk");
    list.add("plop");
    list.add("dd0p");
    for (String key : list) {
        int hash = key.hashCode() ^ (key.hashCode() >>> 16);
        System.out.println("字符串：" + key + " \tIdx(16)：" + ((16 - 1) & hash) + " \tBit值：" + Integer.toBinaryString(hash) + " - " + Integer.toBinaryString(hash & 16) + " \t\tIdx(32)：" + ((
        System.out.println(Integer.toBinaryString(key.hashCode()) +" "+ Integer.toBinaryString(hash) + " " + Integer.toBinaryString((32 - 1) & hash));
    }
}

测试结果

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
字符串：jlkk 	Idx(16)：3 	Bit值：1100011101001000010011 - 10000 		Idx(32)：19
1100011101001000100010 1100011101001000010011 10011
字符串：lopi 	Idx(16)：14 	Bit值：1100101100011010001110 - 0 		Idx(32)：14
1100101100011010111100 1100101100011010001110 1110
字符串：jmdw 	Idx(16)：7 	Bit值：1100011101010100100111 - 0 		Idx(32)：7
1100011101010100010110 1100011101010100100111 111
字符串：e4we 	Idx(16)：3 	Bit值：1011101011101101010011 - 10000 		Idx(32)：19
1011101011101101111101 1011101011101101010011 10011
字符串：io98 	Idx(16)：4 	Bit值：1100010110001011110100 - 10000 		Idx(32)：20
1100010110001011000101 1100010110001011110100 10100
字符串：nmhg 	Idx(16)：13 	Bit值：1100111010011011001101 - 0 		Idx(32)：13
1100111010011011111110 1100111010011011001101 1101
字符串：vfg6 	Idx(16)：8 	Bit值：1101110010111101101000 - 0 		Idx(32)：8
1101110010111101011111 1101110010111101101000 1000
字符串：gfrt 	Idx(16)：1 	Bit值：1100000101111101010001 - 10000 		Idx(32)：17
1100000101111101100001 1100000101111101010001 10001
字符串：alpo 	Idx(16)：7 	Bit值：1011011011101101000111 - 0 		Idx(32)：7
1011011011101101101010 1011011011101101000111 111
字符串：vfbh 	Idx(16)：1 	Bit值：1101110010111011000001 - 0 		Idx(32)：1
1101110010111011110110 1101110010111011000001 1
字符串：bnhj 	Idx(16)：0 	Bit值：1011100011011001100000 - 0 		Idx(32)：0
1011100011011001001110 1011100011011001100000 0
字符串：zuio 	Idx(16)：8 	Bit值：1110010011100110011000 - 10000 		Idx(32)：24
1110010011100110100001 1110010011100110011000 11000
字符串：iu8e 	Idx(16)：8 	Bit值：1100010111100101101000 - 0 		Idx(32)：8
1100010111100101011001 1100010111100101101000 1000
字符串：yhjk 	Idx(16)：8 	Bit值：1110001001010010101000 - 0 		Idx(32)：8
1110001001010010010000 1110001001010010101000 1000
字符串：plop 	Idx(16)：9 	Bit值：1101001000110011101001 - 0 		Idx(32)：9
1101001000110011011101 1101001000110011101001 1001
字符串：dd0p 	Idx(16)：14 	Bit值：1011101111001011101110 - 0 		Idx(32)：14
1011101111001011000000 1011101111001011101110 1110
  • 这里我们随机使用一些字符串计算他们分别在 16 位长度和 32 位长度数组下的索引分配情况，看哪些数据被重新路由到了新的地址。
  • 同时，这里还可以观察🕵出一个非常重要的信息，原哈希值与扩容新增出来的长度 16，进行 & 运算，如果值等于 0，则下标位置不变。如果不为 0，那么新的位置则是原来位置上加 16。｛这个地方需要好好理解下，并看实验数据｝
  • 这样一来，就不需要在重新计算每一个数组中元素的哈希值了。

4.2 数据迁移

bugstack.cn 数据迁移

  • 这张图就是原 16 位长度数组元素，向 32 位扩容后数组转移的过程。
  • 对 31 取模保留低 5 位，对 15 取模保留低 4 位，两者的差异就在于第 5 位是否为 1，是的话则需要加上增量，为 0 的话则不需要改变
  • 其中黄色区域元素 zuio 因计算结果 hash & oldCap 低位第 5 位为 1，则被迁移到下标位置 24。
  • 同时还是用重新计算哈希值的方式验证了，确实分配到 24 的位置，因为这是在二进制计算中补 1 的过程，所以可以通过上面简化的方式确定哈希值的位置。

那么为什么 e.hash & oldCap == 0 为什么可以判断当前节点是否需要移位，而不是再次计算 hash;

仍然是原始长度为 16 举例:

1
2
3
4
5
6
7
8
9
old:
10: 0000 1010
15: 0000 1111
&: 0000 1010 

new:
10: 0000 1010
31: 0001 1111
&: 0000 1010

从上面的示例可以很轻易的看出，两次 indexFor () 的差别只是第二次参与位于比第一次左边有一位从 0 变为 1, 而这个变化的 1 刚好是 oldCap, 那么只需要判断原 key 的 hash 这个位上是否为 1: 若是 1, 则需要移动至 oldCap + i 的槽位，若为 0, 则不需要移动；

这也是 HashMap 的长度必须保证是 2 的幂次方的原因，正因为这种环环相扣的设计，HashMap.loadFactor 的选值是 3/4 就能理解了，table.length * 3/4 可以被优化为 ((table.length>> 2) << 2) - (table.length >> 2) == table.length - (table.length >> 2), JAVA 的位运算比乘除的效率更高，所以取 3/4 在保证 hash 冲突小的情况下兼顾了效率；

# 面试题总结

# Question

# 1. 为什么 HashMap 哈希表中数组长度总是取 2 的幂次方？

# 散列数组需要一个 2 的幂次方的长度，因为只有 2 的幂次方在减 1 的时候，才会出现 01111 这样的值。
1
2
//通过获取存储内容的hashcode，并且对长度是 2 的幂次方的数组长度-1进行与运算得到一个可以在数组中出现的位置
int idx = key.hashCode() & (tab.length - 1);
1
2
3
4
5
6
7
哈希表中数组长度总是取 2 的幂次方，这是因为对于大多数的质数来说，它们的二进制表示中只有少数位是为 1。如果使用一个不是 2 的幂次方的数组长度，那么当元素的哈希映射到索引时，就会出现某些索引永远无法被访问到的情况，这就浪费了哈希表的空间。

举个例子，比如我们要在一个大小为 5 的数组中插入 10 个元素 {a,b,c,d,e,f,g,h,i,j}，而哈希函数将他们依次映射到下标位置：[0,3,4,2,4,1,3,2,3,4]，可以看到，有三个下标（5、6、7）始终没有被映射到，完全浪费了这几个下标的存储空间。但如果数组长度为 8，那么上述元素的哈希值按照上面的映射规则可以得到的下标分别是 [0, 3, 4, 2, 4, 1, 3, 2, 3, 4] % 8 = [0, 3, 4, 2, 4, 1, 3, 2, 3, 4]，不会出现任何下标被浪费的情况。

这种情况下，如果将数组长度改为 7，那么上述元素的哈希值按照上面的映射规则可以得到的下标分别是 [0, 3, 4, 2, 4, 1, 3, 2, 3, 4] % 7 = [0, 3, 4, 2, 4, 1, 3, 2, 3, 1]，可以看到，索引为 5、6 的空间仍然被浪费了。

因此，为了避免在哈希表中浪费存储空间，我们一般都会选择使用 2 的幂次方作为哈希表的大小。这样，在计算元素的位置时，只需要对哈希码进行位运算即可，不需要进行除法等复杂的计算。同时，由于 2 的幂次方满足 2^n2*n*，所以用位运算来代替除法或取模操作也能够提高运行效率。

# 2.HashMap 怎么保证哈希表长度是 2 的幂次方？

1
2
3
4
5
6
7
在 Java 中，哈希表的长度总是 2 的幂次方。这是通过 HashMap 类中的一个名为 `tableSizeFor(int cap)` 的静态方法来实现的。

这个方法会首先将传入的参数减去 1，然后将结果右移一位，在这个值上加 1，最终得到的结果就是大于等于原始参数且最接近原始参数的 2 的幂次方。例如，如果传入的参数是 7，则按照上述算法可以得到 8：(((7 - 1) >>> 1) + 1) = ((0110)_2 >>> 1 + 1) = (0011)_2 + (0001)_2 = (0100)_2 = 8(((7−1)>>>1)+1)=((0110)2>>>1+1)=(0011)2+(0001)2=(0100)2=8。

因此，当我们创建一个新的哈希表时，只需要将初始容量设置为需要存储的元素数目除以负载因子（load factor），然后调用 `tableSizeFor` 方法进行处理即可。这样就能够保证哈希表的长度始终是 2 的幂次方，并达到较好的性能和空间利用率。

需要注意的是，虽然这种方式确实可以保证哈希表的长度是 2 的幂次方，但有时候也可能会出现哈希冲突的情况。因此，在实际应用中，还需要根据具体情况选择合适的哈希函数、负载因子等参数来避免哈希冲突，并提高哈希表的性能。

# 3. 在 HashMap 存放元素时候有这样一段代码来处理哈希值，这是 java 8 的散列值扰动函数，用于优化散列效果

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

# 4.Hash 为什么用 31 计算？

1
2
3
4
5
6
7
	使用 31 这个系数的原因是因为它既是一个质数，又可以通过移位和减法等简单的运算来实现乘法。同时，由于 31 在二进制中只有一个非零的比特位，因此用 31 进行乘法相当于进行了位运算和加法的组合，这样不仅能够保证高效运算，还能够避免哈希冲突。
	
31具有两个优点：
	1.小质数：31 是一个较小的质数，在哈希表中被用来乘以键的哈希码，使得结果不会太大，从而提高性能。相对于其他的质数，31 更易于被 CPU 缓存，这也有助于提升哈希表的查询速度。
	2.可逆性：因为 31 是质数且比较小，所以只要哈希表的大小足够大，在乘法过程中产生的数据溢出是不会影响哈希结果的。而且，31 的逆元 0x9e3779b1 是一个固定的常量，也很容易计算，这有助于在需要恢复哈希码时进行逆运算。

	在实现哈希函数时，使用系数 31 可以保证高效性、可逆性和低冲突率，因此在 Java 中被广泛使用。

# 5.HashMap 扰动函数的作用是什么，以及它可以被应用在哪些地方？

1
2
3
4
5
6
7
8
9
10
11
12
13
扰动函数是一种用于增强哈希函数的技术。它通常被用来对原始哈希值进行混淆和扰动，从而减小哈希冲突的发生率。
	
	具体来说，扰动函数会将原始哈希值与另一个数值进行混合，并再次运用哈希函数产生最终的哈希值。这个额外的数值可以是任意的固定值或随机数，目的是使得不同的哈希值在进行混淆之后，仍然能够保持一定的分散性，从而减小哈希冲突的概率。

扰动函数可以被应用在许多地方，例如：

1.哈希表：在哈希表中，扰动函数可以用来增加键的随机性，减少哈希冲突的发生率，从而提高哈希表的性能。Java 中的 HashMap 就使用了扰动函数对键的哈希码进行混淆。

2.加密算法：在一些加密算法中，也会使用扰动函数来增加密码熵，并提高加密强度。例如，MD5 算法就采用了一系列扰动函数对数据进行混淆。

3.图像处理：在图像处理中，扰动函数可以用来对像素值随机化，增加图像的噪声，从而实现一些特殊效果，如毛玻璃效果、雨滴效果等。

总之，扰动函数是一种通用的技术，可以在许多场景下使用。通过引入随机数和混淆操作，扰动函数可以增强数据的随机性和复杂性，从而提高系统的安全性和性能。

# 6.HashMap 负载因子？

1
2
3
4
5
6
7
负载因子，可以理解成一辆车可承重重量超过某个阈值时，把货放到新的车上。

	那么在HashMap中，负载因子决定了数据量多少了以后进行扩容。这里要提到上面做的HashMap例子，我们准备了7个元素，但是最后还有3个位置空余，2个位置存放了2个元素。 所以可能即使你数据比数组容量大时也是不一定能正正好好的把数组占满的，而是在某些小标位置出现了大量的碰撞，只能在同一个位置用链表存放，那么这样就失去了Map数组的性能。

	所以，要选择一个合理的大小下进行扩容，默认值0.75就是说当阈值容量占了3/4时赶紧扩容，减少Hash碰撞。

	同时0.75是一个默认构造值，在创建HashMap也可以调整，比如你希望用更多的空间换取时间，可以把负载因子调的更小一些，减少碰撞。

# 7.HashMap 是开放寻址还是拉链寻址？

1
2
3
4
5
6
7
8
9
HashMap 是一种拉链式哈希表，也就是说，它使用了链表来解决哈希冲突。

	具体来说，当多个不同的键映射到同一个桶时，HashMap 会将它们存储在同一个桶中，并通过链表或红黑树等数据结构组织起来。这样，在进行查找、插入、删除等操作时，就可以遍历对应桶中的链表，找到所需的元素。

	相对于开放寻址法，拉链法能够更好地处理哈希冲突，并且支持动态扩容。因为在拉链法中，哈希表的每个桶都可以存储多个元素，而在开放寻址法中，每个位置只能存储一个元素，这使得动态扩容变得更加困难和低效。

	但是，由于链表的空间和时间开销，当哈希冲突较为频繁时，拉链法可能会导致性能下降。为了解决这个问题，Java8 引入了基于红黑树的优化机制，即当链表长度超过一定阈值时，将链表转换为红黑树，以提高查询效率。

总之，HashMap 是一种基于拉链法实现的哈希表，能够高效处理哈希冲突，并且支持动态扩容和基于红黑树的优化。

# 8.HashMap 链表什么时候树化以及迁移数据算法是什么？

1
2
3
4
5
6
7
8
9
在JDK1.8中，HashMap是以数组+链表+红黑树构成的。

	具体来说，当某个桶中的链表长度超过了阈值时，HashMap 会将这个链表转换成一棵红黑树，以便支持更快的查找、插入和删除等操作。这个过程中，需要进行以下步骤：

	1.创建一棵空的红黑树，并将原始链表中的所有元素插入到这棵树中。
	2.删除原始链表中的所有元素，并设置哈希表的结构类型为 TREEBIN。
	3.在进行插入、删除等操作时，先判断当前桶的数据结构类型，如果是链表，则采用链表的方法进行操作；否则，采用红黑树的方法进行操作。

	总之，在 JDK8 及以后版本中，HashMap 在树化和迁移数据方面做了一些优化，使得它能够更好地支持大规模并发和高效内存使用。

# 9.HashMap 中的 key 若为 Object 类型， 则需实现哪些方法？

HashMap 在 JDK1.7 和 JDK1.8 中有哪些区别？_数组_07

1
2
3
4
5
6
7
如果 HashMap 中的 key 是 Object 类型，则该对象需要正确地实现 equals() 和 hashCode() 方法。这两个方法用于确定两个对象是否相等，并计算对象的哈希码。

具体来说，equals() 方法用于比较两个对象是否相等。在 HashMap 中，当两个 key 的哈希值相同时，会调用它们的 equals() 方法进行比较，以确定它们是否真正相等。因此，正确实现 equals() 方法可以防止哈希冲突和键值对重复的问题。
       
hashCode() 方法用于计算对象的哈希码，它将一个对象映射到一个整数值，用于确定该对象在哈希表中的位置。在 HashMap 中，当插入或查找键值对时，会首先计算 key 的哈希码，并根据哈希码查找对应的桶。因此，正确实现 hashCode() 方法可以提高哈希表的性能和效率。

需要注意的是，如果在 HashMap 中使用自定义的对象作为 key，默认情况下，它们的 equals() 方法和 hashCode() 方法是通过继承 Object 类而来的，这可能导致 key 的比较和哈希码计算不准确。因此，我们通常需要自己重写 equals() 和 hashCode() 方法，以满足我们的具体需求。同时，还需要遵循一些规则，例如：如果两个对象相等，那么它们的哈希码必须相等；反之亦然。

# 10.HashMap 中的扰动函数是如何计算的？

1
2
3
4
5
6
/**
 * 使用扰动函数就是为了增加随机性，让数据元素更加均衡的散列，减少碰撞
 * 把哈希值右移16位，也就正好是自己长度的一半，之后与原哈希值做异或运算
 * 这样就混合了原哈希值中的高位和低位，增大了随机性
 */
int hashIndex = (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));

# 11. 为什么 hashMap 中要使用 （1 << 30） 来作为最大限制

1
2
3
4
5
在 HashMap 中，使用 1 << 30 来作为容量的最大限制是因为 Java 中的数组长度不能超过 Integer.MAX_VALUE（即 2^31-1）。而 HashMap 内部的实现需要使用一个数组来保存数据，因此其容量也必须受到这个限制。

为了保证 HashMap 的最大容量不超过 Integer.MAX_VALUE，同时又要尽可能地提高 HashMap 的容量，Java 开发团队选择了 1 << 30 作为 HashMap 的最大容量。这个值是一个 2 的幂次方，可以充分利用位运算的优势，同时又不会超过数组长度的最大限制。

需要注意的是，HashMap 实际上并不会直接使用 1 << 30 作为容量的最大限制。在初始化 HashMap 时，如果传入的初始容量大于等于 1 << 30，则会将容量设置为 Integer.MAX_VALUE；如果传入的初始容量小于 1 << 30，则会将容量调整为大于等于传入值且最接近 2 的幂次方的数。这样可以确保 HashMap 容量的合理性，同时避免出现数组长度超过 Integer.MAX_VALUE 的情况。

# 12.HashMap 如何寻找 2 的幂次方最小值？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//JDK1.8中：把二进制的各个位置都填上1，当二进制的各个位置都是1以后，就是一个标准的2的幂次方减1了，最后把结果加1再返回即可。
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;
}
//JDK1.8之后：（二分法）通过多次右移和减小位宽的方式来逐步缩小搜索范围，最终得到最高位 0 的个数
static final int tableSizeFor(int cap) {
     int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

# 12. 为什么重写 equals 一定要重写 hashcode

1
2
3
4
5
6
7
8
9
10
11
在 Java 中，每个类都继承了 Object 类，Object 类提供了两个有关哈希值的方法，一个是 equals() 方法，另一个是 hashCode() 方法。其中，equals() 方法用于判断两个对象是否相等，而 hashCode() 方法则返回该对象的哈希码。

如果在一个类中重写了 equals() 方法，但没有重写 hashCode() 方法，则可能会导致出现以下情况：

	在使用 HashMap、HashSet 等哈希数据结构时，由于不同的对象可以返回相同的哈希值，因此可能会将这些对象误认为是同一个对象，从而引发程序错误。
	在使用自定义对象作为键来进行 Map 操作时，由于不同的键可以返回相同的哈希值，因此可能无法正确地定位到对应的键值对，从而导致数据丢失或查找失败。
因此，如果要重写 equals() 方法，则必须同时重写 hashCode() 方法，以确保它们的行为一致并满足一些约定：

	如果两个对象使用 equals() 方法比较返回相等，则它们的 hashCode() 值必须相等。
	如果两个对象的 hashCode() 值相等，则它们不一定相等（即可能存在哈希冲突），因此需要再次使用 equals() 方法进行比较。
通过遵循这些约定，可以保证在使用哈希数据结构或自定义对象作为键值对时不会出现问题。

# 13. 为什么在 Java 的 HashMap 实现中，数组的大小（即容量）必须始终保持为 2 的幂次方？

1
2
3
4
5
6
7
8
HashMap的长度必须保证是2的幂次方，是为了避免出现HashMap为空或者HashMap中存储的元素个数不足2的幂次方的情况。

如果HashMap的长度不是2的幂次方，可能会导致以下问题：

	如果HashMap的长度为1，那么它的哈希冲突解决方式只能是链地址法（即将冲突的键值对插入到链表中），这种方式不能处理哈希冲突。
	如果HashMap的长度为0，那么它的哈希冲突解决方式只能是开放地址法（即将冲突的键值对直接放在HashMap中），这种方式不能处理哈希冲突。

因此，为了保证HashMap的正确性和性能，我们需要确保它的长度是2的幂次方，或者为一个固定的最大值。如果需要动态地调整HashMap的长度，可以使用链表法或者开放地址法。

# 14. 为什么 HashMap.loadFactor 的选值是 3/4，而不是 2/4?

1
2
3
首先，当loadFactor的值比较小的时候，虽然能够减少空间的浪费，但是会导致哈希表更加频繁地进行扩容操作，这会影响到HashMap的性能。
其次，当loadFactor的值比较大的时候，虽然能够减少扩容操作的次数，但是会导致哈希链表长度过长，查找效率会变得较低。
因此，为了平衡空间利用率和时间效率，选择一个适当的loadFactor值非常重要。经过实验和分析，发现loadFactor取0.75时，可以在保证哈希表查找效率的同时，稍微减少空间的浪费。另外，这个值也是比较常见的一个取值，很多编程语言中也采用了类似的值。

# 15.HashMap 什么时候会触发扩容机制？如何扩容？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HashMap在存储键值对时，会将键通过哈希函数映射到桶里面，每个桶是一个链表或红黑树。当HashMap中的元素数量增加到超过了负载因子（默认为0.75），就会触发扩容机制。

具体地说，在添加元素时，如果当前的元素数量达到了阈值（即容量乘以负载因子），就会启动扩容机制。这个阈值通过如下公式计算：

threshold = capacity * loadFactor

其中capacity是当前HashMap的容量，loadFactor是负载因子，默认值为0.75。当HashMap中元素个数达到了threshold值时，就会触发扩容机制。

扩容操作包括以下几个步骤：

	1.创建一个新的Entry数组，长度为原数组的两倍。
	2.将原来数组中所有的元素重新分配到新的数组中，这一步需要重新计算每个元素的hash值，并且根据新的数组长度求出它们在新数组中的位置。
	3.在重新分配元素的过程中，如果某个位置上有多个元素，则会形成一个链表或红黑树，这取决于链表长度是否大于等于8，并且桶容量大于64。如果链表长度大于等于8并且桶容量大于64的话，则会将其转换为红黑树，否则仍然使用链表。这一步是为了提高查询效率，因为红黑树的查询时间复杂度是O(log n)，而链表的查询时间复杂度是O(n)。
	4.更新HashMap的容量和阈值。
	
扩容操作会比较耗时，因为需要重新计算hash值、重新分配元素等，所以应该尽可能避免频繁触发扩容。可以通过调整负载因子的大小来控制HashMap的性能和空间占用

# 关于我

Brath 是一个热爱技术的 Java 程序猿，公众号「InterviewCoder」定期分享有趣有料的精品原创文章！

InterviewCoder

非常感谢各位人才能看到这里，原创不易，文章如果有帮助可以关注、点赞、分享或评论，这都是对我的莫大支持！

喜欢这篇文章？打赏一下作者吧

评论

最新文章

归档

关注我
关注我

链接

×