关于java:面试28k职位老乡面试官从HashCode到HashMap给我讲了一下午回家赶忙整理出16万字的面试材料

作者：小傅哥
博客：https://bugstack.cn

一、前言

不是面试难，而是 30 岁要有 30 岁的能力，35 岁要有 35 岁的经验！

☺️可能有点题目夸大，但本文通篇干货，要不亲自实际各项知识点，很难有这样的深度的总结。有时候咱们会埋怨找工作难，但同样企业招聘也难，面试官向我透漏，为了招聘 3 个高开，以及筛选了 200 份简历，面试了 70 场。

本文从 HashCode 讲到 HashMap，从一个小小的知识点扩大的实践实际验证，10 来万单词表的数据验证；数据分布 、 扰动函数 、 负载因子 、 数据迁徙 等各项外围数学知识，非常适合行将跨入高开的程序员学习。

本文波及到的源码和图表，能够关注公众号：bugstack 虫洞栈，回复下载后，关上取得的链接，找到 ID：19，即可下载。

好！接下来就是咱们这次面试的外围知识点总结，通篇 1.6 万字，需急躁浏览。

二、HashCode 为什么应用 31 作为乘数

1. 固定乘积 31 在这用到了

// 获取 hashCode "abc".hashCode();
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {char val[] = value;
        for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

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

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

2. 来自 stackoverflow 的答复

在 stackoverflow 对于为什么抉择 31 作为固定乘积值，有一篇探讨文章，Why does Java’s hashCode() in String use 31 as a multiplier? 这是一个工夫比拟久的问题了，摘取两个答复点赞最多的；

413 个赞???? 的答复

最多的这个答复是来自《Effective Java》的内容；

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

这段内容次要论述的观点包含；

1. 31 是一个奇质数。
2. 另外在二进制中，2 个 5 次方是 32，那么也就是 31 * i == (i << 5) - i。这次要是说乘积运算能够应用位移晋升性能，同时目前的 JVM 虚拟机也会主动反对此类的优化。

80 个赞???? 的答复

As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.

• 这个答复就很有实战意义了，通知你用超过 5 千个单词计算 hashCode，这个 hashCode 的运算应用 31、33、37、39 和 41 作为乘积，失去的碰撞后果，31 被应用就很失常了。
• 他这句话就就能够作为咱们实际的指向了。

3. Hash 值碰撞概率统计

接下来要做的事件并不难，只是依据 stackoverflow 的答复，统计出不同的乘积数对 10 万个单词的 hash 计算结果。10 个单词表已提供，能够通过关注公众号：bugstack 虫洞栈进行下载

3.1 读取单词字典表

1    a    "n.(A)As 或 A's  安(ampere(a) art. 一;n. 字母 A /[军] Analog.Digital, 模仿 / 数字 /(=account of) 帐上 "
2    aaal    American Academy of Arts and Letters 美国艺术和文学学会
3    aachen     亚琛[德意志联邦共和国西部城市]
4    aacs    Airways and Air Communications Service (美国)航路与航空通信联络处
5    aah    "[军]Armored Artillery Howitzer, 装甲榴弹炮;[军]Advanced Attack Helicopter, 先进攻打直升机"
6    aal    "ATM Adaptation Layer,ATM 适应层"
7    aapamoor    "n.[生]丘泽, 高下位镶嵌沼泽"

• 单词表的文件格式如上，能够自行解析
• 读取文件的代码比较简单，这里不展现了，能够通过 资源下载 进行获取

3.2 Hash 计算函数

public static Integer hashCode(String str, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {hash = multiplier * hash + str.charAt(i);
    }
    return hash;
}

• 这个过程比较简单，与原 hash 函数比照只是替换了可变参数，用于咱们统计不同乘积数的计算结果。

3.3 Hash 碰撞概率计算

想计算碰撞很简略，也就是计算那些呈现雷同哈希值的数量，计算出碰撞总量即可。这里的实现形式有很多，能够应用 set、map 也能够应用 java8 的stream流统计distinct。

private static RateInfo hashCollisionRate(Integer multiplier, List<Integer> hashCodeList) {int maxHash = hashCodeList.stream().max(Integer::compareTo).get();
    int minHash = hashCodeList.stream().min(Integer::compareTo).get();
    int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());
    double collisionRate = (collisionCount * 1.0) / hashCodeList.size();
    return new RateInfo(maxHash, minHash, multiplier, collisionCount, collisionRate);
}

• 这里记录了最大 hash 和最小 hash 值，以及最终返回碰撞数量的统计后果。

3.4 单元测试

@Before
public void before() {"abc".hashCode();
    // 读取文件，103976 个英语单词库.txt
    words = FileUtil.readWordList("E:/itstack/git/github.com/interview/interview-01/103976 个英语单词库.txt");
}

@Test
public void test_collisionRate() {List<RateInfo> rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
    for (RateInfo rate : rateInfoList) {System.out.println(String.format("乘数 = %4d, 最小 Hash = %11d, 最大 Hash = %10d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
    }
}

• 以上先设定读取英文单词表中的 10 个单词，之后做 hash 计算。
• 在 hash 计算中把单词表传递进去，同时还有乘积数；2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199，最终返回一个 list 后果并输入。
• 这里次要验证同一批单词，对于不同乘积数会有怎么样的 hash 碰撞后果。

测试后果

单词数量：103976
乘数 =    2, 最小 Hash =          97, 最大 Hash = 1842581979, 碰撞数量 = 60382, 碰撞概率 = 58.0730%
乘数 =    3, 最小 Hash = -2147308825, 最大 Hash = 2146995420, 碰撞数量 = 24300, 碰撞概率 = 23.3708%
乘数 =    5, 最小 Hash = -2147091606, 最大 Hash = 2147227581, 碰撞数量 =  7994, 碰撞概率 = 7.6883%
乘数 =    7, 最小 Hash = -2147431389, 最大 Hash = 2147226363, 碰撞数量 =  3826, 碰撞概率 = 3.6797%
乘数 =   17, 最小 Hash = -2147238638, 最大 Hash = 2147101452, 碰撞数量 =   576, 碰撞概率 = 0.5540%
乘数 =   31, 最小 Hash = -2147461248, 最大 Hash = 2147444544, 碰撞数量 =     2, 碰撞概率 = 0.0019%
乘数 =   32, 最小 Hash = -2007883634, 最大 Hash = 2074238226, 碰撞数量 = 34947, 碰撞概率 = 33.6106%
乘数 =   33, 最小 Hash = -2147469046, 最大 Hash = 2147378587, 碰撞数量 =     1, 碰撞概率 = 0.0010%
乘数 =   39, 最小 Hash = -2147463635, 最大 Hash = 2147443239, 碰撞数量 =     0, 碰撞概率 = 0.0000%
乘数 =   41, 最小 Hash = -2147423916, 最大 Hash = 2147441721, 碰撞数量 =     1, 碰撞概率 = 0.0010%
乘数 =  199, 最小 Hash = -2147459902, 最大 Hash = 2147480320, 碰撞数量 =     0, 碰撞概率 = 0.0000%

Process finished with exit code 0

以上就是不同的乘数下的 hash 碰撞后果图标展现，从这里能够看出如下信息；

1. 乘数是 2 时，hash 的取值范畴比拟小，根本是沉积到一个范畴内了，前面内容会看到这块的展现。
2. 乘数是 3、5、7、17 等，都有较大的碰撞概率
3. 乘数是 31 的时候，碰撞的概率曾经很小了，根本稳固。
4. 顺着往下看，你会发现 199 的碰撞概率更小，这就相当于一排奇数的茅坑量多，天然会缩小碰撞。但这个范畴值曾经远超过 int 的取值范畴了，如果用此数作为乘数，又返回 int 值，就会失落数据信息。

4. Hash 值散列散布

除了以上看到哈希值在不同乘数的一个碰撞概率后，对于散列表也就是 hash，还有一个十分重要的点，那就是要尽可能的让数据散列散布。只有这样能力缩小 hash 碰撞次数，也就是前面章节要讲到的 hashMap 源码。

那么怎么看散列散布呢？如果咱们能把 10 万个 hash 值铺到图表上，造成的一张图，就能够看出整个散列散布。然而这样的图会比拟大，当咱们放大看后，就成一个了大黑点。所以这里咱们采取分段统计，把 2 ^ 32 方分 64 个格子进行寄存，每个格子都会有对应的数量的 hash 值，最终把这些数据展现在图表上。

4.1 哈希值分段寄存

public static Map<Integer, Integer> hashArea(List<Integer> hashCodeList) {Map<Integer, Integer> statistics = new LinkedHashMap<>();
    int start = 0;
    for (long i = 0x80000000; i <= 0x7fffffff; i += 67108864) {
        long min = i;
        long max = min + 67108864;
        // 筛选出每个格子里的哈希值数量，java8 流统计；https://bugstack.cn/itstack-demo-any/2019/12/10/%E6%9C%89%E7%82%B9%E5%B9%B2%E8%B4%A7-Jdk1.8%E6%96%B0%E7%89%B9%E6%80%A7%E5%AE%9E%E6%88%98%E7%AF%87(41%E4%B8%AA%E6%A1%88%E4%BE%8B).html
        int num = (int) hashCodeList.parallelStream().filter(x -> x >= min && x < max).count();
        statistics.put(start++, num);
    }
    return statistics;

• 这个过程次要统计 int 取值范畴内，每个哈希值寄存到不同格子里的数量。
• 这里也是应用了 java8 的新个性语法，统计起来还是比拟不便的。

4.2 单元测试

@Test
public void test_hashArea() {System.out.println(HashCode.hashArea(words, 2).values());
    System.out.println(HashCode.hashArea(words, 7).values());
    System.out.println(HashCode.hashArea(words, 31).values());
    System.out.println(HashCode.hashArea(words, 32).values());
    System.out.println(HashCode.hashArea(words, 199).values());
}

• 这里列出咱们要统计的乘数值，每一个乘数下都会有对应的哈希值数量汇总，也就是 64 个格子里的数量。
• 最终把这些统计值放入到 excel 中进行图表化展现。

统计图表

• 以上是一个沉积百分比统计图，能够看到下方是不同乘数下的，每个格子里的数据统计。
• 除了 199 不能用以外，31 的散列后果相对来说比拟平均。

4.2.1 乘数 2 散列

• 乘数是 2 的时候，散列的后果根本都沉积在两头，没有很好的散列。

4.2.2 乘数 31 散列

• 乘数是 31 的时候，散列的成果就非常明显了，根本在每个范畴都有数据寄存。

4.2.3 乘数 199 散列

• 乘数是 199 是不能用的散列后果，然而它的数据是更加扩散的，从图上能看到有两个小山包。但因为数据区间问题会有数据失落问题，所以不能抉择。

三、HashMap 数据结构与算法

1. 写一个最简略的 HashMap

学习 HashMap 前，最好的形式是先理解这是一种怎么样的数据结构来存放数据。而 HashMap 通过多个版本的迭代后，乍一看代码还是很简单的。就像你原来只穿个裤衩，当初还有秋裤和风衣。所以咱们先来看看最基本的 HashMap 是什么样，也就是只穿裤衩是什么成果，之后再去剖析它的源码。

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

计划：如果说咱们须要通过 ID 从数组中获取元素，那么就须要把每个字符串都计算出一个在数组中的地位 ID。字符串获取 ID 你能想到什么形式？ 一个字符串最间接的获取跟数字相干的信息就是 HashCode，可 HashCode 的取值范畴太大了[-2147483648, 2147483647]，不可能间接应用。那么就须要应用 HashCode 与数组长度做与运算，失去一个能够在数组中呈现的地位。如果说有两个元素失去同样的 ID，那么这个数组 ID 下就寄存两个字符串。

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

1.1 代码实现

// 初始化一组字符串
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 的倍数。这样的数组长度才会呈现一个 0111 除高位以外都是 1 的特色，也是为了散列。
3. 接下来就是循环存放数据，计算出每个字符串在数组中的地位。key.hashCode() & (tab.length - 1)。
4. 在字符串寄存到数组的过程，如果遇到雷同的元素，进行连贯操作 模仿链表的过程。
5. 最初输入寄存后果。

测试后果

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 散列示意图

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

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

1.3 这个简略的 HashMap 有哪些问题

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

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

以上这些问题能够演绎为；扰动函数 、 初始化容量 、 负载因子 、 扩容办法 以及 链表和红黑树 转换的应用等。接下来咱们会一一问题进行剖析。

2. 扰动函数

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

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 位，也就正好是本人长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了 随机性。计算形式如下图；

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

2.2 试验验证扰动函数

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

但看不到试验数据的话，这究竟是一段实践，具体这段哈希值真的被减少了随机性没有，并不知道。所以这里咱们要做一个试验，这个试验是这样做；

1. 选取 10 万个单词词库
2. 定义 128 位长度的数组格子
3. 别离计算在扰动和不扰动下，10 万单词的下标调配到 128 个格子的数量
4. 统计各个格子数量，生成稳定曲线。如果扰动函数下的稳定曲线绝对更安稳，那么证实扰动函数有成果。

2.2.1 扰动代码测试

扰动函数比照办法

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 非扰动函数下，下标值计算

单元测试

// 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 中生成图表。

2.2.2 扰动函数散列图表

以上的两张图，别离是没有应用扰动函数和应用扰动函数的，下标调配。试验数据；

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

未应用扰动函数

应用扰动函数

• 从这两种的比照图能够看进去，在应用了扰动函数后，数据调配的更加平均了。
• 数据调配平均，也就是散列的成果更好，缩小了 hash 的碰撞，让数据寄存和获取的效率更佳。

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

接下来咱们探讨下一个问题，从咱们模拟 HashMap 的例子中以及 HashMap 默认的初始化大小里，都能够晓得，散列数组须要一个 2 的倍数的长度，因为只有 2 的倍数在减 1 的时候，才会呈现 01111 这样的值。

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

3.1 寻找 2 的倍数最小值

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

public HashMap(int initialCapacity, float loadFactor) {
    ...
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

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

计算阀值大小的办法；

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 这样一个初始化计算阀值的过程，用图展现进去，不便了解；

3.2 负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子是做什么的？

负载因子，能够了解成一辆车可承重分量超过某个阀值时，把货放到新的车上。

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

所以，要抉择一个正当的大小下进行扩容，默认值 0.75 就是说当阀值容量占了 3 /4s 时连忙扩容，缩小 Hash 碰撞。

同时 0.75 是一个默认结构值，在创立 HashMap 也能够调整，比方你心愿用更多的空间换取工夫，能够把负载因子调的更小一些，缩小碰撞。

4. 扩容元素拆分

为什么扩容，因为数组长度有余了。那扩容最间接的问题，就是须要把元素拆分到新的数组中。拆分元素的过程中，原 jdk1.7 中会须要从新计算哈希值，然而到 jdk1.8 中曾经进行优化，不在须要从新计算，晋升了拆分的性能，设计的还是十分奇妙的。

4.1 测试数据

@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));
    }
}

测试后果

字符串：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 数据迁徙

• 这张图就是原 16 位长度数组元素，像 32 位数组长度中转移的过程。
• 其中黄色区域元素 zuio 因计算结果 hash & oldCap 不为 1，则被迁徙到下标地位 24。
• 同时还是用从新计算哈希值的形式验证了，的确调配到 24 的地位，因为这是在二进制计算中补 1 的过程，所以能够通过下面简化的形式确定哈希值的地位。

四、HashMap 源码解析

1. 插入

1.1 疑难点 & 考题

通过上一章节的学习：《HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习》

大家对于一个散列表数据结构的 HashMap 往里面插入数据时，根本曾经有了一个印象。简略来说就是通过你的 Key 值获得哈希再计算下标，之后把相应的数据寄存到外面。

但再这个过程中会遇到一些问题，比方；

1. 如果呈现哈希值计算的下标碰撞了怎么办？
2. 如果碰撞了是扩容数组还是把值存成链表构造，让一个节点有多个值寄存呢？
3. 如果寄存的数据的链表过长，就失去了散列表的性能了，怎么办呢？
4. 如果想解决链表过长，什么时候应用树结构呢，应用哪种树呢？

这些疑难点都会在前面的内容中逐渐解说，也能够本人思考一下，如果是你来设计，你会怎么做。

1.2 插入流程和源码剖析

HashMap 插入数据流程图

visio 原版流程图，能够通过关注公众号：bugstack 虫洞栈，进行下载

以上就是 HashMap 中一个数据插入的整体流程，包含了；计算下标、何时扩容、何时链表转红黑树等，具体如下；

1. 首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2. 判断 tab 是否位空或者长度为 0，如果是则进行扩容操作。

   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;

3. 依据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则须要笼罩。tab[i = (n - 1) & hash])
4. 判断 tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
5. 如果链表中插入节点的时候，链表长度大于等于 8，则须要把链表转换为红黑树。treeifyBin(tab, hash);
6. 最初所有元素解决实现后，判断是否超过阈值；threshold，超过则扩容。
7. treeifyBin, 是一个链表转树的办法，但不是所有的链表长度为 8 后都会转成树，还须要判断寄存 key 值的数组桶长度是否小于 64 MIN_TREEIFY_CAPACITY。如果小于则须要扩容，扩容后链表上的数据会被拆扩散列的相应的桶节点上，也就把链表长度缩短了。

JDK1.8 HashMap 的 put 办法源码如下:

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 初始化桶数组 table，table 被提早到插入新数据时再进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不蕴含键值对节点援用，则将新键值对节点的援用存入桶中即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            
        // 如果桶中的援用类型为 TreeNode，则调用红黑树的插入方法
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 对链表进行遍历，并统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 链表中不蕴含要插入的键值对节点时，则将该节点接在链表的最初
                if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                    // 如果链表长度大于或等于树化阈值，则进行树化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 条件为 true，示意以后链表蕴含要插入的键值对，终止遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 判断要插入的键值对是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 示意是否仅在 oldValue 为 null 的状况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 键值对数量超过阈值时，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.3 扩容机制

HashMap 是基于数组 + 链表和红黑树实现的，但用于寄存 key 值得的数组桶的长度是固定的，由初始化决定。

那么，随着数据的插入数量减少以及负载因子的作用下，就须要扩容来寄存更多的数据。而扩容中有一个十分重要的点，就是 jdk1.8 中的优化操作，能够不须要再从新计算每一个元素的哈希值，这在上一章节中曾经讲到，能够浏览系列专题文章，机制如下图；

里咱们次要看下扩容的代码(正文局部)；

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // Cap 是 capacity 的缩写，容量。如果容量不为空，则阐明曾经初始化。if (oldCap > 0) {
        // 如果容量达到最大 1 << 30 则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 按旧容量和阀值的 2 倍计算新容量和阀值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
    
        // initial capacity was placed in threshold 翻译过去的意思，如下；// 初始化时，将 threshold 的值赋值给 newCap，// HashMap 应用 threshold 变量临时保留 initialCapacity 参数的值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 这一部分也是，源代码中也有相应的英文正文
        // 调用无参构造方法时，数组桶数组容量为默认容量 1 << 4; aka 16
        // 阀值；是默认容量与负载因子的乘积，0.75
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 为 0，则应用阀值公式计算容量
    if (newThr == 0) {float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    @SuppressWarnings({"rawtypes","unchecked"})
        // 初始化数组桶，用于寄存 key
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果旧数组桶，oldCap 有值，则遍历将键值映射到新数组桶中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 这里 split，是红黑树拆分操作。在从新映射时操作的。((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 这里是链表，如果以后是依照链表寄存的，则将链表节点按原程序进行分组{这里有专门的文章介绍，如何不须要从新计算哈希值进行拆分《HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习》}
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 将分组后的链表映射到桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

以上的代码略微有些长，然而整体的逻辑还是蛮清晰的，次要包含；

1. 扩容时计算出新的 newCap、newThr，这是两个单词的缩写，一个是 Capacity，另一个是阀 Threshold
2. newCap 用于翻新的数组桶 new Node[newCap];
3. 随着扩容后，原来那些因为哈希碰撞，寄存成链表和红黑树的元素，都须要进行拆分寄存到新的地位中。

1.4 链表树化

HashMap 这种散列表的数据结构，最大的性能在于能够 O(1)工夫复杂度定位到元素，但因为哈希碰撞不得已在一个下标里寄存多组数据，那么 jdk1.8 之前的设计只是采纳链表的形式进行寄存，如果须要从链表中定位到数据工夫复杂度就是 O(n)，链表越长性能越差。因为在 jdk1.8 中把过长的链表也就是 8 个，优化为自均衡的红黑树结构，以此让定位元素的工夫复杂度优化近似于 O(logn)，这样来晋升元素查找的效率。但也不是齐全摈弃链表，因为在元素绝对不多的状况下，链表的插入速度更快，所以综合思考下设定阈值为 8 才进行红黑树转换操作。

链表转红黑树，如下图；

以上就是一组链表转换为红黑树的状况，元素包含；40、51、62、73、84、95、150、161 这些是通过理论验证可调配到 Idx：12 的节点

通过这张图，根本能够有一个 链表 换行到 红黑树 的印象，接下来浏览下对应的源码。

链表树化源码

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 这块就是咱们下面提到的，不肯定树化还可能只是扩容。次要桶数组容量是否小于 64 MIN_TREEIFY_CAPACITY 
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {// 又是单词缩写；hd = head (头部)，tl = tile (结尾)
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将一般节点转换为树节点，但此时还不是红黑树，也就是说还不肯定均衡
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 转红黑树操作，这里须要循环比拟，染色、旋转。对于红黑树，在下一章节具体解说
            hd.treeify(tab);
    }
}

这一部分链表树化的操作并不简单，简单点在于下一层的红黑树转换上，这部分知识点会在后续章节中专门介绍；

以上源码次要包含的知识点如下；

1. 链表树化的条件有两点；链表长度大于等于 8、桶容量大于 64，否则只是扩容，不会树化。
2. 链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗均衡树。同时在树转换过程中会记录链表的程序，tl.next = p，这次要不便后续树转链表和拆分更不便。
3. 链表转换成树实现后，在进行红黑树的转换。先简略介绍下，红黑树的转换须要染色和旋转，以及比对大小。在比拟元素的大小中，有一个比拟有意思的办法，tieBreakOrder加时赛，这次要是因为 HashMap 没有像 TreeMap 那样自身就有 Comparator 的实现。

1.5 红黑树转链

在链表转红黑树中咱们重点介绍了一句，在转换树的过程中，记录了原有链表的程序。

那么，这就简略了，红黑树转链表时候，间接把 TreeNode 转换为 Node 即可，源码如下；

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // 遍历 TreeNode
    for (Node<K,V> q = this; q != null; q = q.next) {
        // TreeNode 替换 Node
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

// 替换办法
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {return new Node<>(p.hash, p.key, p.value, next);
}

因为记录了链表关系，所以替换过程很容易。所以好的数据结构能够让操作变得更加容易。

2. 查找

上图就是 HashMap 查找的一个流程图，还是比较简单的，同时也是高效的。

接下来咱们在联合代码，来剖析这段流程，如下；

public V get(Object key) {
    Node<K,V> e;
    // 同样须要通过扰动函数计算哈希值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判断桶数组的是否为空和长度值
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 计算下标，哈希值与数组长度 -1
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {// TreeNode 节点间接调用红黑树的查找办法，工夫复杂度 O(logn)
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 如果是链表就顺次遍历查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

以上查找的代码还是比较简单的，次要包含以下知识点；

1. 扰动函数的应用，获取新的哈希值，这在上一章节曾经讲过
2. 下标的计算，同样也介绍过 tab[(n - 1) & hash])
3. 确定了桶数组下标地位，接下来就是对红黑树和链表进行查找和遍历操作了

3. 删除

 public V remove(Object key) {
     Node<K,V> e;
     return (e = removeNode(hash(key), key, null, false, true)) == null ?
         null : e.value;
 }
 
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 定位桶数组中的下标地位，index = (n - 1) & hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 树节点，调用红黑树的查找办法，定位节点。if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 遍历链表，找到待删除节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 删除节点，以及红黑树须要修复，因为删除后会毁坏平衡性。链表的删除更加简略。if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
} 

• 删除的操作也比较简单，这外面都没有太多的简单的逻辑。
• 另外红黑树的操作因为被包装了，只看应用上也是很容易。

4. 遍历

4.1 问题点

HashMap 中的遍历也是十分罕用的 API 办法，包含；

KeySet

 for (String key : map.keySet()) {System.out.print(key + " ");
 }

EntrySet

 for (HashMap.Entry entry : map.entrySet()) {System.out.print(entry + " ");
 }

从办法上以及日常应用都晓得，KeySet 是遍历是无序的，但每次应用不同形式遍历包含keys.iterator()，它们遍历的后果是固定的。

那么从实现的角度来看，这些种遍历都是从散列表中的链表和红黑树获取汇合值，那么他们有一个什么固定的法则吗？

4.2 用代码测试

测试的场景和前提；

1. 这里咱们要设定一个既有红黑树又有链表构造的数据场景
2. 为了能够有这样的数据结构，咱们最好把 HashMap 的初始长度设定为 64，防止在链表超过 8 位后扩容，而是间接让其转换为红黑树。

3. 找到 18 个元素，别离放在不同节点(这些数据通过程序计算得来)；

   1. 桶数组 02 节点：24、46、68
   2. 桶数组 07 节点：29
   3. 桶数组 12 节点：150、172、194、271、293、370、392、491、590

代码测试

@Test
public void test_Iterator() {Map<String, String> map = new HashMap<String, String>(64);
    map.put("24", "Idx：2");
    map.put("46", "Idx：2");
    map.put("68", "Idx：2");
    map.put("29", "Idx：7");
    map.put("150", "Idx：12");
    map.put("172", "Idx：12");
    map.put("194", "Idx：12");
    map.put("271", "Idx：12");
    System.out.println("排序 01：");
    for (String key : map.keySet()) {System.out.print(key + " ");
    }
    
    map.put("293", "Idx：12");
    map.put("370", "Idx：12");
    map.put("392", "Idx：12");
    map.put("491", "Idx：12");
    map.put("590", "Idx：12");
    System.out.println("\n\n 排序 02：");
    for (String key : map.keySet()) {System.out.print(key + " ");
    }    
    
    map.remove("293");
    map.remove("370");
    map.remove("392");
    map.remove("491");
    map.remove("590");
    System.out.println("\n\n 排序 03：");
    for (String key : map.keySet()) {System.out.print(key + " ");
    }
    
}

这段代码别离测试了三种场景，如下；

1. 增加元素，在 HashMap 还是只链表构造时，输入测试后果 01
2. 增加元素，在 HashMap 转换为红黑树时候，输入测试后果 02
3. 删除元素，在 HashMap 转换为链表构造时，输入测试后果 03

4.3 测试后果剖析

排序 01：24 46 68 29 150 172 194 271 

排序 02：24 46 68 29 271 150 172 194 293 370 392 491 590 

排序 03：24 46 68 29 172 271 150 194 
Process finished with exit code 0

从 map.keySet()测试后果能够看到，如下信息；

1. 01 状况下，排序定位哈希值下标和链表信息

1. 02 状况下，因为链表转换为红黑树，树根会挪动到数组头部。moveRootToFront()办法

1. 03 状况下，因为删除了局部元素，红黑树进化成链表。

五、红黑树前身，2- 3 树剖析

日常的学习和一部分搭档的面试中，居然会听???? 到的是；从 HashMap 中文红黑树、从数据库索引为 B +Tree，但问 2 - 3 树的状况就不是很多了。

1. 为什么应用树结构

从最基本的起因来看，应用树结构就是为了晋升整体的效率；插入、删除、查找(索引)，尤其是索引操作。因为相比于链表，一个均衡树的索引工夫复杂度是 O(logn)，而数组的索引工夫复杂度是 O(n)。

从以下的图上能够比照，两者的索引耗时状况；

• 从上图能够看到，应用树结构无效的升高工夫复杂度，晋升数据索引效率。
• 另外这个规范的树结构，是二叉搜寻树(Binary Search Tree)。除此之外树形构造还有；AVL 树、红黑树、2- 3 树等

2. 二叉搜寻树进化链表

在树的数据结构中，最先有点是二叉查找树，也就是英文缩写 BST 树。在应用数据插入的过程中，现实状况下它是一个均衡的二叉树，但实际上可能会呈现二叉树都一边倒，让二叉树像列表一样的数据结构。从而树形构造的工夫复杂度也从 O(logn) 降级到O(n)，如下图；

• 二叉搜寻树的数据插入过程是，插入节点与以后树节点做比对，小于在左，大于在右。
• 随着数据的插入程序不同，就会呈现齐全不同的数据结构。可能是一棵均衡二叉树，也极有可能进化成链表的树。
• 当树结构进化成链表当前，整个树索引的性能也跟着进化成链表。

综上呢，如果咱们心愿在插入数据后又放弃树的特点，O(logn)的索引性能，那么就须要在插入时进行节点的调整

3. 2- 3 树解决均衡问题

2- 3 树是什么构造，它怎么解决均衡问题的。带着问题咱们持续????。

2- 3 树是一种十分奇妙的构造，在放弃树结构的根底上，它容许在一个节点中能够有两个元素，等元素数量等于 3 个时候再进行调整。通过这种形式呢，来保障整个二叉搜寻树的平衡性。

这样说可能还没有感觉，来看下图；

• 左侧是二叉搜寻树，右侧是 2 - 3 均衡树，别离插入节点 4、5，察看树形构造变动。
• 二叉搜寻树开始呈现偏移，节点一遍倒。
• 2- 3 树通过一个节点中寄存 2 到 3 个元素，来调整树形构造，保持平衡。所谓的保持平衡就是从根节点，到每一个最底部的本人点，链路长度统一。

2- 3 树曾经能够解决均衡问题 那么，数据是怎么寄存和调整的呢，接下来咱们开始实际应用。

六、红黑树前身，2- 3 树应用

1. 树结构定义和特点性质

2- 3 树，读法；二三树，个性如下；

综上咱们能够总结出，2- 3 树的一些性质；

1. 2- 3 树所有子叶节点都在同一层
2. 1 个节点能够有 1 到 2 个数据，如果有三个须要调整树结构
3. 1 个节点 1 个数据时，则有两个子节点
4. 1 个节点 2 个数据时，则有三个子节点，且两头子节点是介于两个节点间的值

2. 数据插入

接下来咱们就模仿在二叉搜寻树中进化成链表的数据，插入到 2 - 3 树的变动过程，数据包含；1、2、3、4、5、6、7，插入过程图如下；

以上，就是整个数据在插入过程中，2- 3 树的演化过程，接下来咱们具体解说每一步的变动；

• α，向节点 1 插入数据 2，此时为了保持平衡，不会新产生分支，只会在一个节点中寄存两个节点。
• β，持续插入数据 3，此时这个节点有三数据，1、2、3，是一个长期区域。
• γ，把三个数据的节点，两头节点拉起来，调整成树形构造。
• δ，持续插入数据 4，为了放弃树均衡，会插在节点 3 的右侧。
• ε，持续插入数据 5，插入后 3、4、5 共用 1 个节点，当一个节点上有三个数据时候，则须要进行调整。
• ζ，两头节点 4 向上⏫调整，调整后，1 节点在左、3 节点在两头、5 节点在右。
• η，持续插入数据 6，在放弃树均衡的状况下，与节点 5 专用。
• θ，持续插入数据 7，插入后，节点 7 会与以后的节点 5 6 共用。此时是一个长期寄存，须要调整。初步调整后，抽出 6 节点，向上寄存，变为 2 4 6 共用一个节点，这是一个长期状态，还须要持续调整。
• ι，因为根节点有三个数据 2、4、6，则持续须要把两头节点上移，1、3 和5、7 则别离成二叉落到 节点 2 、节点 6 上。

???????? 希腊字母：α(阿尔法)、β(贝塔)、γ(伽马)、δ(德尔塔)、ε(伊普西隆)、ζ(截塔)、η(艾塔)、θ(西塔)、ι(约塔)

3. 数据删除

有了下面数据插入的学习，在看数据删除其实就是一个逆向的过程，在删除的次要包含这样两种状况；

1. 删除了 3 - 节点，也就是蕴含两个数据元素的节点，间接删除即可，不会毁坏树均衡。
2. 删除了 2 - 节点，此时会毁坏树均衡，须要将树高缩短或者元素合并，复原树均衡。

承接下面???? 的例子，咱们把数据再从 7、6、5、4、3、2、1 程序删除，察看 2 - 3 树的构造变动，如下；

• α，删除节点 7，因为节点 7 只有一个数据元素，删除节点 5、6 合并，但此时毁坏了 2 - 3 树的平衡性，须要缩短树高进行调整。
• β，因为删除节点后，整个树结构不均衡，所以须要缩短树高，调整元素。节点 2、4 合并，节点 1、3 别离插入左侧和两头。
• γ，删除节点 6，这个节点是 3 - 节点 ( 能够分出 3 个叉的意思)，删除后不会毁坏树均衡，放弃不变。
• δ，删除节点 5，此时会毁坏树均衡，须要把跟节点 4 下放，与 3 合并。
• ε，删除节点 4，这个节点仍旧是 3 - 节点，所以不须要扭转树结构。
• ζ，删除节点 3，此时只有 1、2 节点，须要合并。
• η，删除节点 2，此时节点仍旧是 3 - 节点，所以不须要扭转树结构。

再看一个略微简单点 2 - 3 树删除：

下面???? 这张图，就一个略微简单点的 2 - 3 均衡树，树的删除过程次要包含；

1. 删除 4，其实须要将节点 3、5 合并，指向节点 2，放弃树均衡。
2. 删除 7，节点 8、9 合并。
3. 删除 14，节点 15 上移，复原成 3 - 叉树。

???? 如果有时候不好了解删除，能够试想下，这个要删除的节点，在插入的时候是一个什么成果。

4. 数据索引

相比于插入和删除，索引的过程还是比较简单的，不须要调整数据后果。根本准则就是；

1. 小于以后节点值，左侧寻找
2. 大于以后节点值，右侧寻找
3. 始终到找到索引值，进行。

???? 第一层寻找：

???? 第二层寻找：

???? 第三次寻找：

七、红黑树解析

红黑树，是一种高效的自均衡二叉查找树

Rudolf Bayer 于 1978 年创造红黑树，在过后被称为 对称二叉 B 树 (symmetric binary B-trees)。起初，在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 批改为现在的 红黑树。

红黑树具备良好的效率，它可在近似O(logN) 工夫复杂度下实现插入、删除、查找等操作，因而红黑树在业界也被广泛应用，比方 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。

死记硬背，很难学会

红黑树的构造和设计都十分优良，也同样在实现上有着简单的解决逻辑，包含插入或者删除节点时；色彩变动、旋转操作等操作。但如果只把这些知识点硬背下来，什么时候染色、什么时候旋转，是没有多大意义的，用不了多久也就遗记了。所以这部分的学习，理解其基本更重要。

1、2- 3 树与红黑树的等价性

在上一章节《解说 2 - 3 均衡树「红黑树的前身」》，应用了大量图例解说了 2 - 3 树，并在题目处写出它是红黑树的前身。浏览后更容易了解红黑树相干常识。

红黑树规定

1. 根节点是彩色
2. 节点是红黑或者彩色
3. 所有子叶节点都是彩色(叶子是 NIL 节点，默认没有画进去)
4. 每个红色节点必须有两个彩色子节点(也同样阐明一条链路上不能有链路的红色节点)
5. 黑高，从任一节点到齐每个叶子节点，通过的门路都蕴含雷同数目的彩色节点

那么，这些规定是怎么总结定义进去的呢？接下里咱们一步步剖析解说。

1. 为什么既有 2 - 3 树要有红黑树

首先 2- 3 树( 读法：二三树 ) 就是一个节点有 1 个或者 2 个元素，而实际上 2 - 3 树转红黑树是由概念模型 2-3- 4 树 转换而来的。- 4 叉 就是一个节点里有 3 个元素，这在 2 - 3 树中会被调整，然而在概念模型中是会被保留的。

尽管 2-3- 4 树 也是具备 2- 3 树 同样的均衡树的个性，然而如果间接把这样的模型用代码实现就会很麻烦，且效率不高，这里的简单点包含；

1. 2- 叉、3- 叉、4- 叉，三种构造的节点类型，相互转换复杂度较高
2. 3- 叉、4- 叉，节点在数据比拟上须要进行屡次，不像 2 - 叉节点，间接布尔类型比拟即可 非左即右
3. 代码实现上对每种差别，都须要有额定的代码，规定不够标准化

所以 ，心愿找到一种均衡关系，既放弃 2 - 3 树均衡和 O(logn) 的个性，又能在代码实现上更加不便，那么就诞生了红黑树。

2. 简略 2 - 3 树转红黑树

2- 3 树 转红黑树，也能够说红黑树是 2- 3 树 和2-3- 4 树 的另外一种表现形式，也就是更利于编码实现的模式。

简略转换示例；

从上图能够看出，2-3- 4 树与红黑树的转换关系，包含；

1. 2- 叉节点，转换比较简单，只是把原有节点转换为彩色节点
2. 3- 叉节点，包含了 2 个元素，先用红色线把两个节点相连，之后拆分进去，最初调整高度 彩色节点在上
3. 4- 叉节点，包含了 3 个元素，别离用红黑线连贯，之后拆分进去拉升高度。这个拉升过程和 2 - 3 树调整统一，只是增加了色彩

综上，就是 2 -3- 4 树的节点转换，总结进去的规定，如下；

1. 将 2 -3- 4 树，用二叉树的模式示意
2. 3- 叉、4- 叉节点，应用红色、彩色连线进行连贯
3. 另外，3- 叉节点有两种状况，导致转换成二叉树，就有左倾和右倾

3. 简单 2 - 3 树转红黑树

在 简略 2 - 3 树转换红黑树 的过程中，理解到一个根本的转换规则右旋定义，接下来咱们在一个略微简单一点的 2- 3 树 与红黑树的对应关系，如下图；

上图是一个略微简单点的 2 - 3 树，转换为红黑树的过程，是不这样一张图让你对红黑树更有感觉了，同时它也满足一下条件；

1. 从任意节点到叶子节点，所通过的彩色节点数目雷同
2. 彩色节点放弃着整体的平衡性，也就是让整个红黑树靠近于 O(logn)工夫复杂度
3. 其余红黑树的特点也都满足，能够对照红黑树的个性进行比对

2、红黑树操作

2.1 均衡操作

通过在上一章节 2 - 3 树的学习，在插入节点时并不会插到空地位，而是与现有节点交融以及调整，放弃整个树的均衡。

而红黑树是 2 -3- 4 树的一种概念模型转换而来，在插入节点时通过红色链接相连，也就是插入红色节点。插入实现后进行调整，以放弃树靠近均衡。

那么，为了让红黑树达到均衡状态，次要包含染色、↔左右旋转、这些做法其实都是从 2 - 3 树演变过去的。接下来咱们就别离解说几种规定的演化过程，以此更好理解红黑树的均衡操作。

2.1.1 左旋转

左旋定义： 把一个向右歪斜的红节点链接(2- 3 树，3- 叉双元素节点)，转化为左链接。

背景：程序插入元素，1、2、3，2- 3 树保持平衡，红黑树临时处于右歪斜。

接下来咱们别离比照两种树结构的均衡操作；

1. 2- 3 树，所有插入的节点都会放弃在一个节点上，之后通过调整节点地位，保持平衡。
2. 红黑树，则须要通过节点的左侧旋转，将元素 2 拉起来，元素 1 和元素 3，别离成为左右子节点。

红黑树的左旋，只会解决与之对应的 2 - 3 树节点进行操作，不会整体扭转。

2.1.2 右旋转

右旋定义： 把一个向左歪斜的红节点连贯(2- 3 树，3- 叉双元素节点)，转换为右连贯。

背景：程序插入元素，3、1、1，2- 3 树保持平衡，红黑树临时处于左歪斜。

接下来咱们别离比照两种树结构的均衡操作；

1. 2- 3 树，所有插入的节点都会放弃在一个节点上，之后通过调整节点地位，保持平衡。
2. 红黑树，则须要通过节点的右侧旋转，将元素 2 拉起来，元素 1 和元素 3，别离成为左右子节点。

你会发现，左旋与右旋是互相对应的，但在 2 - 3 树中是放弃不变的

2.1.3 左右旋综合使用

左旋、右旋，咱们曾经有了一个根本的概念，那么接下来咱们再看一个能够综合左右旋以及对应 2 - 3 树的演变案例，如下；

以上的例子别离演示了一个元素插入的三种状况，如下；

1. 1、3，插入 0，左侧底部插入，与 2 - 3 树相比，须要右旋保持平衡
2. 1、3，插入 2，两头地位插入，首先进行左旋调整元素地位，之后进行右旋进行树均衡
3. 1、3，插入 5，右侧地位插入，此时正好放弃树均衡，不须要调整

2.1.4 染色

在 2 - 3 树中，插入一个节点，为了放弃树均衡是不插入到空地位上的，当插入节点后元素数量有 3 个后则须要调整两头元素向上，来放弃树均衡。与之对应的红黑树则须要调整色彩，来保障红黑树的均衡规定，具体参考如下；

2.2 旋转 + 染色使用案例

接下来咱们把下面解说到的 旋转 、 染色，使用到一个理论案例中，如下图；

• 首先从左侧开始，是一个依照程序插入生产进去的红黑树，插入程序；`7、2、8、1、4、3、5

`

• α，向目前红黑树插入元素 6，插入后右下角有三个红色节点；3、5、6。
• β，因为右下角满足染色条件，变换后；彩色节点(3、5)、红色节点(4、6)。
• γ，之后看被红色连线链接的节点7、4、2，最小节点在两头，左旋均衡树结构。
• δ，左旋实现后，红色链接线的 7、4、2 为做倾程序节点，因而须要做右旋操作。
• ε，左旋、右旋，调整实现后，又满足了染色操作。到此复原红黑树均衡。

留神，所有连贯红色节点的，都是是红色线。以此与 2 - 3 树做对应。

2.3. 删除操作

依据 2 -3- 4 树模型的红黑树，在删除的时候根本是依照 2 - 3 形式进行删除，只不过在这个过程中须要染色和旋转操作，以放弃树均衡。删除过程次要能够分为如图四种状况，如下；

2.3.1 删除子叶红色节点

红色子叶节点的删除并不会毁坏树均衡，也不影响树高，所以间接删除即可，如下；

2.3.2 删除左侧节点

2.3.2.1 被删节点兄弟为彩色 & 含右子节点

2.3.2.2 被删节点兄弟为彩色 & 含左子节点

2.3.2.3 被删节点兄弟为彩色 & 含双子节点(红)

2.3.2.4 被删节点兄弟为彩色 & 不含子节点

2.3.2.5 被删节点兄弟为彩色 & 含双黑节点(黑)

2.3.3 删除右侧节点

2.3.3.1 被删节点兄弟为彩色 & 含左子节点

2.3.3.2 被删节点兄弟为彩色 & 含右子节点

2.3.3.3 被删节点兄弟为彩色 & 含双子节点(红)

2.3.2.4 被删节点兄弟为彩色 & 不含子节点

2.3.2.5 被删节点兄弟为彩色 & 含双黑节点(黑)

八、总结

• HashMap 的数据结构设计的十分优良，同时也非常复杂，波及的知识点泛滥。作为高级开发的程序员尽管平时开发不须要实现这样的性能，然而这里的设计思维十分值得学习。
• 这里的知识点根本包含了；Hash 值的设计，HashMap 中，1、散列表实现 、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分 得算法的制订以及 2 -3- 4 树到红黑树的转换，都十分值得深刻学习。
• 面试只是一份新工作的开发，就像比武招亲一样，你总要拿出本人最优良的实力，如果以后能力还有余，那么就能够持续深刻学习。

九、系列文章

• 简历写成这样，谁要你呀!
• 工作 5 年的学习路线资源汇总
• 讲道理，只有你是一个爱折腾的程序员，毕业找工作真的不须要再花钱培训！
• 高级开发必须要懂设计模式，并能重构代码