我是风筝，公众号「古时的风筝」，一个兼具深度与广度的程序员鼓励师，一个本打算写诗却写起了代码的田园码农！
文章会收录在 JavaNewBee 中，更有 Java 后端知识图谱，从小白到大牛要走的路都在里面。
这是上篇文章 有趣的条漫版 HashMap，25岁大爷都能看懂 的文字版。有不少同学说条漫版的比较有意思，简单易懂，但是毕竟图片画不了那么详细，只能从大面而上理解。
真正的了解细节，还得看这一篇。其实是这篇先写完，然后画了不少图片，所以就写了一篇图片版的。本篇 7000 多字，建议三连呦。
在 Java 中，最常用的数据类型是 8 中基本类型以及他们的包装类型以及字符串类型，其次应该就是 ArrayList和HashMap了吧。HashMap存的是键值对类型的数据，其存储和获取的速度快、性能高，是非常好用的一个数据结构，每一个 Java 开发者都肯定用过它。
而且 HashMap的设计巧妙，其结构和原理也经常被拿去当做面试题。其中有很多巧妙的算法和设计，比如 Hash 算法、拉链法、红黑树设计等，值得每一个开发者借鉴学习。
想了老半天，怎么才能简单易懂的把 HashMap说明白呢，那就从我理解它的思路和过程去说吧。要理解一个事物最好的方式就是先了解整体结构，再去追究细节。所以，我们先从结构谈起。
先从结构说起拿我自身的一个体会来说吧，风筝我作为一个专业路痴，对于迷路这件事儿绝不含糊，虽然在北京混迹多年，但是只在中关村能分清南北，其他地方，哪怕是我每天住的小区、每天工作的公司也分不太清方向，回家只能认一条路，要是打车换条路回家，也得迷糊一阵，这么说吧，在小区前面能回家，小区后面找不到家。去个新地方，得盯着地图看半天。这时，我就在想啊，要是我能在城市上空俯瞰下面的街道，那我就再也不怕找不到回家的路了。这不就是三体里的降维打击吗，站在高维的立场，理解低维的事物，那就简单多了。
理解数据结构也是一个道理，大多数时候，我们都是停留在会用的层面上，理解一些原理也只是支离破碎的，困在数据机构的迷宫里跌跌撞撞，迫切的需要一张地图或者一架直升机。
先来看一下整个 Map家族的集成关系图，一看东西还不少，但其他的可能都没怎么用过，只有 HashMap最熟悉。
以下描述可能不够专业，只为简单的描述 HashMap的结构，请结合下图进行理解。
HashMap主体上就是一个数组结构，每一个索引位置英文叫做一个 bin，我们这里先管它叫做桶，比如你定义一个长度为 8 的 HashMap，那就可以说这是一个由 8 个桶组成的数组。当我们像数组中插入数据的时候，大多数时候存的都是一个一个 Node 类型的元素，Node 是 HashMap中定义的静态内部类。
当插入数据（也就是调用 put 方法）的时候，并不是按顺序一个一个向后存储的，HashMap中定义了一套专门的索引选择算法，叫做散列计算，但散列计算存在一种情况，叫哈希碰撞，也就是两个不一样的 key 散列计算出来的 hash 值是一致的，这种情况怎么办呢，采用拉链法进行扩展，比如图中蓝色的链表部分，这样一来，具有相同 hash 值的不同 key 即可以落到相同的桶中，又保证不会覆盖之前的内容。
但随着插入的元素越来越多，发生碰撞的概率就越大，某个桶中的链表就会越来越长，直到达到一个阈值，HashMap就受不了了，为了提升性能，会将超过阈值的链表转换形态，转换成红黑树的结构，这个阈值是 8 。也就是单个桶内的链表节点数大于 8 ，就会将链表变身为红黑树。
以上概括性的描述就是 HashMap的整体结构，也是我们进一步研究细节的蓝图。我们将从中抽取出几个关键点一一解释，从整体到细节，降维打击 HashMap。
接下来就是说明为什么会设计成这样的结构以及从单纯数组到桶内链表产生，接着把链表转换成红黑树的详细过程。
认清几个关键概念 存储容器因为HashMap内部是用一个数组来保存内容的，数组定义如下：
transient Node<K,V>[] table; Node 类型table 是一个 Node类型的数组，Node是其中定义的静态内部类，主要包括 hash、key、value 和 next 的属性。比如之后我们使用 put 方法像其中加键值对的时候，就会转换成 Node 类型。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } TreeNode