HashMap 是日常开发中，用的最多的荟萃类之一，也是面试中经常被问到的 Java 类之一。同时，HashMap 在实现方式上面又有十分典型的规范。

不管是从哪一方面来看，学习 HashMap 都可以说是有利无害的。分析 HashMap 的源码的文章在网上面已经数不胜数了，本文另辟蹊径来分析 HashMap 的设计思想。

底层数据结构说到 HashMap 的数据库，我们需要从两个 JDK 版原来分析：JDK7 和 JDK8。JDK7 版本的 HashMap 的数据结构为：数组 + 链表。而 JDK8 版本的 HashMap 的数据结构为： 数组 + 链表 + 红黑树。可以看到 7 和 8 中 HashMap 的底层数据结构最主要的区别就是 Java8 多了红黑树。

为何是数组加链表？上文中说到了 不管是 7 或者8 ，底层数据结构都是 数组 + 链表，但这又是为什么呢？数组是一个链式数据结构。put的时候，通过哈希函数将数据举行 哈希运算 之后，就获得数组的下标，这样子就可以将数据生存在对应的槽中，这个槽在 HashMap 中被称为 Entry。在 get 时候，通过相同的哈希函数，将 key 举行哈希运算，可以获得对应的下标，就可以快速找到该 key 对应的 value。

这时候， get 的时间庞大度还是 O(1)。但，哈希运算就制止不了有哈希冲突，也就说，差别的值通过哈希运算之后可能获得同一个值。

在散列表的相关观点中，我们说了几种解决哈希冲突的方案，在 HashMap中，则是接纳了链表法。也就是说，发生了冲突之后，我们在Entry中形成一个单链表。可是这里有存在了一个问题，如果链表过长，检索起来的效率同样也会很低。

于是，在 Java8 中，通过链表转红黑树来解决这个问题。为何要加上红黑树为什么要链表转红黑树，我们需要从数据结构来剖析。如果从一个无序单链表中检索数据，我们只能重新到尾一个一个检索，一旦数据量很大的情况下，检索的效率就很低。

这时，我们想到了红黑树，从现在的情况来看，红黑树能很好地解决这个问题。我们先来看看红黑树的界说：红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或玄色。

在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的分外要求：节点是红色或玄色。根是玄色。

所有叶子都是玄色（叶子是NIL节点）。每个红色节点必须有两个玄色的子节点。（从每个叶子到根的所有路径上不能有两个一连的红色节点。）从任一节点到其每个叶子的所有简朴路径都包罗相同数目的玄色节点。

红黑树要是红黑树，首先得是二叉查找树：二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于或即是它的根节点的值；任意节点的左、右子树也划分为二叉查找树；简朴做一个总结，红黑树的左节点要比父节点小，右节点要比父节点大。如果要检索一个数字，可以将时间庞大度从 O(n) 降低到 O(logn)。

固然了，添加了红黑树的数据结构之后，代码实现要比 只用数组 + 链表要庞大了好几倍。看代码的时候简直是不能再痛苦了。

什么时候转成红黑树，有什么转成链表在源码中有这么一个字段，static final int TREEIFY_THRESHOLD = 8;，见字知义，这个字段的意思链表转红黑树的阈值，也就是 8。同样的，另有这么一个字段，static final int UNTREEIFY_THRESHOLD = 6;，它意思是红黑树转链表的阈值。

为什么是 8 呢？在源码的注释中也有解释，英文翻译过来就是下面的意思。链表查询的时间庞大度是 O (n)，红黑树的查询庞大度是 O (log n)。

在链表数据不多的时候，使用链表举行遍历也比力快，只有当链表数据比力多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，思量到转化时间和空间损耗，所以我们需要界说出转化的界限值。在思量设计 8 这个值的时候，我们参考了泊松漫衍概率函数，由泊松漫衍中得出结论，链表各个长度的掷中概率为：* 0: 0.60653066* 1: 0.30326533* 2: 0.07581633* 3: 0.01263606* 4: 0.00157952* 5: 0.00015795* 6: 0.00001316* 7: 0.00000094* 8: 0.00000006复制代码意思是，当链表的长度是 8 的时候，泛起的概率是 0.00000006，不到千万分之一，所以说正常情况下，链表的长度不行能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题，所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写代码，使用 HashMap 时，险些不会遇到链表转化成红黑树的情况，究竟观点只有千万分之一。为什么两个阈值纷歧样的，大家想想，如果一样的，在链表到达8 的时候，会转成红黑树，但红黑树转链表的阈值也是8，这时候就会泛起循环转换。链表转红黑树另有一个条件，就是当数组容量大于 64 时，链表才会转化成红黑树扩容的条件在说扩容之前，先来说说 HashMap 在 7 和 8 中初始化时的差别体现。

在 Java 7 中，HashMap 初始化的时候，会有个默认容量 （16）。但在 Java8 中，HashMap 初始化的时候，默认容量为0，只有在第一次 put 的时候，才会扩容到 16。（其实 ArrayList 在 Java8 也是这么体现的）。在 HashMap 源码中，有一个字段界说 static final float DEFAULT_LOAD_FACTOR = 0.75f;。

这个字段的意思是，当HashMap 的长度 = HashMap 当前容量 * 0.75的时候，就会发生扩容。关于为什么负载因子是 0.75，我们可以在源码注释找到一定的谜底。load factor大致意思就是说负载因子是0.75的时候，空间使用率比力高，而且制止了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比力低，提升了空间效率。

HashMap的扩容是酿成原先容量的 2 倍。Hash函数我们先来看看 Java 8 的 hash 函数。static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }复制代码这里的或许意思就是，先盘算出 key 的 hashCode h。

然后盘算盘算 h ^ (h >>> 16)。无符号右移16位。这么做的利益是使大多数场景下，算出来的 hash 值比力疏散。

一般来说，hash 值算出来之后，要盘算当前 key 在数组中的索引下标位置时，可以接纳取模的方式，就是索引下标位置 = hash 值 % 数组巨细，这样做的利益，就是可以保证盘算出来的索引下标值可以匀称的漫衍在数组的各个索引位置上，但取模操作对于处置惩罚器的盘算是比力慢的，数学上有个公式，当 b 是 2 的幂次方时，a % b = a &（b-1），所以此处索引位置的盘算公式我们可以更换为： (n-1) & hash。此问题可以延伸出三个小问题：1：为什么不用 key % 数组巨细，而是需要用 key 的 hash 值 % 数组巨细。答：如果 key 是数字，直接用 key % 数组巨细是完全没有问题的，但我们的 key 另有可能是字符串，是庞大工具，这时候用 字符串或庞大工具 % 数组巨细是不行的，所以需要先盘算出 key 的 hash 值。

2：盘算 hash 值时，为什么需要右移 16 位？答：hash 算法是 h ^ (h >>> 16)，为了使盘算出的 hash 值更疏散，所以选择先将 h 无符号右移 16 位，然后再于 h 异或时，就能到达 h 的高 16 位和低 16 位都能到场盘算，淘汰了碰撞的可能性。3：为什么把取模操作换成了 & 操作？答：key.hashCode() 算出来的 hash 值还不是数组的索引下标，为了随机的盘算出索引的下表位置，我们还会用 hash 值和数组巨细举行取模，这样子盘算出来的索引下标比力匀称漫衍。

取模操作处置惩罚器盘算比力慢，处置惩罚器对 & 操作就比力擅长，换成了 & 操作，是有数学上证明的支撑，为了提高了处置惩罚器处置惩罚的速度。hash 冲突时怎么办？hash 冲突指的是 key 值的 hashcode 盘算相同，但 key 值差别的情况。如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；如果桶中元素已经是链表，而且链表个数大于即是 8 时，此时有两种情况：如果此时数组巨细小于 64，数组再次扩容，链表不会转化成红黑树;如果数组巨细大于 64 时，链表就会转化成红黑树。

这里不仅仅判断链表个数大于即是 8，还判断了数组巨细，数组容量小于 64 没有立刻转化的原因，推测主要是因为红黑树占用的空间比链表大许多，转化也比力耗时，所以数组容量小的情况下冲突严重，我们可以先实验扩容，看看能否通过扩容来解决冲突的问题。

本文来源：欧宝app官网登陆-www.xyzysmx.com