请说一下HashMap及其底层实现原理

说说HashMap的get取值流程

JDK 7 与JDK 8 中的HashMap有什么不同？

HashMap与Hashtable的区别有哪些？

......

在前5篇文章中，壹哥 给大家介绍了HashMap的基本特点、底层数据结构、HashMap中的重要属性，分析了HashMap的默认初始容量、负载因子，还有HashMap是如何保证其容量必须是2的N次方的，以及HashMap的put()方法执行流程。但在HashMap中，其底层内容非常的复杂，所以接下来在今天的文章中，壹哥 会继续给大家剖析HashMap的底层源码，敬请关注哦。

前5篇文章地址如下：

高薪程序员&面试题精讲系列39之说说HashMap的特点及其底层数据结构

高薪程序员&面试题精讲系列40之HashMap默认初始容量、最大容量、负载因子是多少？链表转红黑树阈值是多少？HashMap什么时候进行扩容？

高薪程序员&面试题精讲系列41之HashMap的容量为什么必须是2的N次方？说说HashMap添加数据的流程吧
高薪程序员&面试题精讲系列42之HashMap中如果出现冲突怎么解决？如何计算key的hash值、如何进行数组索引定位？

高薪程序员&面试题精讲系列43之HashMap扩容机制的底层实现原理，HashMap扩容后是如何进行rehash操作的？

二. get()取值原理

搞清楚了HashMap是如何存值之后，我们再来看看HashMap是如何来取值的。

1. get(key)方法源码

我们先来看看HashMap#get(key)方法的源码，如下：

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (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) {
                if (first instanceof TreeNode)
                    return ((TreeNode)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;
    }

get(key)方法与put(key,value)一对比，我们会发现，get()操作明显简单了很多。具体的取值流程，壹哥 给大家总结如下，请往下看。

2. get()取值流程(重点)

结合上面的代码，我们可以对取值流程总结如下图所示：

从上图可以得知，当我们调用 get()方法后，首先要确定索引的位置，也就是我们所说的位桶的位置，这和 put()方法中的定位是一样的，都是先使用 hash(key)这个函数来确定 hash 值，然后用 (n-1) & hash来获取最终的索引位置。

这里我们把get取值流程总结如下：

• 根据要取值的key，hash(key)计算出数组中对应的索引位置；
• 取出指定位置上的元素(这时key的hash值是一样的)；
• 如果key完全一样，则直接返回该值，查找结束；
• 如果key不一样，判断其后面挂载的是红黑树还是链表；
• 如果是红黑树，则按照树的方式查找；
• 如果是链表，则按照链表的方式查找;
• 如果任何一步都没有发现结果，则说明key在map中不存在，直接返回null。

3. 3种节点的处理情况

我们get取值时，在确定桶的位置后，有可能会出现3种情况:

• 单节点类型: 表示单个位桶内只有一个键值对，这是HashMap中存在最多的节点类型，只要不发生哈希碰撞都是这种类型，最理想的HashMap就是这样的。
• 链表类型: 如果发现key是在一个链表结构中，则需要遍历链表，直到找到 与该 key 相等的 Node节点。
• 红黑树类型: 如果发现key对应的节点在一颗红黑树中，则使用红黑树特有的快速查找法进行查找。

三. remove()移除方法

remove()与put()、get()方法类似，都是先得到 key 对应的 hash 值，然后利用 (n-1) & hash获取索引位置，之后根据不同的节点类型采取不同的处理措施。

• 单节点类型: 直接将当前位桶上的元素替换为node.next，也就是 null。
• 链表类型: 如果是链表类型，就将被删除节点的前一个节点的 next属性设置为 node.next。
• 红黑树类型: 如果是一棵红黑树，就调用红黑树的节点删除法。如果节点数在 2~6之间，就将树结构转化为链表。

四. 迭代器(Iterator）

迭代器是一种设计模式，在Java中它是一个对象，可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”的对象，因为创建它的代价很小。迭代器接口Iterable是Collection类的父接口，它只有一个方法: iterator()，该方法会返回一个代表当前集合对象的泛型迭代器，用于之后的遍历操作。所有的Collection集合对象都会实现这个Iterable接口，允许使用foreach进行遍历。

至此，壹哥 就带着各位，把HashMap中一些重要的属性和方法都分析完毕了，但还有一些问题需要我们掌握和明确，所以下面壹哥再把一些重要的问题给大家补充说明一下。

五. HashMap为什么是非线程安全的？

1. HashMap存在的线程安全问题

HashMap对多线程操作并没有做并发控制，如果想在多线程这样的高并发环境下使用集合，我们可以考虑使用ConcurrentHashMap。如果同一时刻有多个线程同时执行 put操作，且计算出来的索引(桶)位置是相同的，则会造成前一个 key 被后一个 key 覆盖的现象。

比如下图中，线程A 和 线程B 同时执行 put 操作，两个线程中有可能计算出的索引都是2。假如此时，线程A 和 线程B 都判断出索引为 2 的 位桶上 是空的，然后就开始插入值。线程A 先 put进去 key1 = 1 的键值对，紧接着 线程B 又 put进去 key2 = 2的键值对，那么最后索引为2的位桶中，值应该就是 key2=2，因为线程A 存进去的值被覆盖掉了！

另外在进行resize()扩容时，多线程操作还有可能会引起 死循环 的问题！当HashMap进行自动扩容时，如果有2个线程同时检测到元素个数超过了阈值，即threshold=数组大小 × 负载因子。那么此时这2个线程都会在put()方法中调用resize()扩容方法，而这两个不同的线程同时修改一个链表结构则会产生一个循环链表(JDK 7中，会出现resize时 前后元素顺序倒置 的情况)，接下来再想通过get()获取某一个元素，就会出现死循环。

2. 解决HashMap的线程安全问题

那么我们该如何解决HashMap的线程安全问题呢？其实通过以下代码就可以使HashMap成为线程安全的集合。

HashMap hashMap = new HashMap();

Map map = Collections.synchronizedMap(hashMap);

当然，更好的部分则是直接采用ConcurrentHashMap集合来替代。

六. JDK 7 与JDK 8 中的HashMap有什么不同(重点)

我们现在开发时，大多数都是基于JDK 8这个开发环境的，所以真正开发时面对的也是JDK 8中的HashMap。但是总有一些老古董，非得来问问我们JDK 8之前的HashMap怎么回事，都不用了的东西你说非得问这干嘛啊？但是没办法，谁让人家是面试官啦，所以这里 壹哥 还是给大家把不同版本的HashMap做个对比。

1. 插入位置不同

JDK 7 中HashMap用的是 头插法，而JDK 8及其之后使用的都是 尾插法。

那么为什么要这样做呢？

这是因为JDK 7中HashMap是 用单向链表进行的纵向延伸，采用头插法能够提高插入的效率，但是可能会出现一个逆序的环形链表，即死循环问题。而在JDK 8 之后因为加入了红黑树，则开始使用尾插法，能够避免出现逆序且死循环的链表。

2. 扩容后数据存储位置的计算方式不同

在JDK 7 中的HashMap采用 hash值和需要扩容的二进制数进行&运算，即hash & length-1这样的方法。这也是为什么在扩容的时候一定是2的n次幂的原因所在，因为只有在2的n次幂的时候，最后一位二进制数才一定是1，这样才能最大程度地减少hash碰撞。

而在JDK 8 中，HashMap是利用 扩容前的原始位置 + 原始容量，不再是JDK 7中的那种 异或 方法。JDK 8中的这种计算方式，相当于只需要判断Hash值中新增的参与运算的位是0还是1，就可以直接计算出扩容后的储存方式了。

3. 数据结构不同

JDK 7中的HashMap采用的是 数组+ 单向链表 的数据结构，而在JDK 8及之后，采用的是 数组+链表+红黑树 的数据结构。当链表的深度达到8的时候，就会自动扩容把链表转成红黑树，这样时间复杂度可以从O(N)变成O(logN)，提高了查询效率。

4. 性能不同

我们知道，在最坏的情况下，所有Entry的key可能会形成一个单向链表。JDK 8中为了优化这个问题，在链表数目大于8时会转化为红黑树，但resize时又必需拆解和重建红黑树。

如果链表长度<=6，会去掉树结构的指针，重建成一个链表；如果链表长度>=8，则会重建成一棵红黑树。

总的来看，JDK 7中的resize时间复杂度为O(n)，JDK 8中的复杂度为O(logn)。

七. HashMap与Hashtable的区别

然后我们再来总结回答一下另一个很常见的问题，如下：

HashMap与Hashtable的区别有哪些?

1. 相同点

• ①. 都是 基于哈希表 来实现的，并且里面存储的元素都是 key-value键值对结构。
• ②. 当产生哈希冲突时，内部都会通过 单链表 去解决冲突问题(当然JDK 8中HashMap中加入了红黑树)。
• ③. 内部容量不足时，都会 自动进行扩容。
• ④. 都实现了Map、Cloneable、Serializable接口，可以被克隆，支持序列化。

2. 不同点 2.1 继承的父类不同

HashMap继承的是AbstractMap，而Hashtable继承的是Dictionary。

2.2 线程安全性不同

HashMap是线程不安全的，在源码中也可以看到，HashMap中的方法并没有添加synchronized修饰符。在多线程的环境下使用时，需要自己增加同步处理，建议使用Collections包下的synchronizedMap来把map包装起来。而Hashtable的方法用了synchronized修饰符，所以它是线程安全的。

2.3 提供的API方法不同

Hashtable提供了contains()、containsValue()和containsKey()3个方法。

而HashMap中则去掉了contains()方法，改用containsKey()方法和containsValue()方法，因为contains()方法容易引起误解。

2.4 key-value是否支持null值

在Hashtable中，key-value是不允许为null的，但是在使用put()方法时将一个null-null的键值对添加进Hashtable时，编译也会通过，只是在运行的时候会抛出NullPointerException异常。

而在HashMap中，是允许null的key出现的，并且只允许出现一个，null的key会放在table[0]的位置。

2.5 遍历方式

HashMap和Hashtable都使用了Iterator迭代器进行遍历，不同的是，Hashtable还有Enumeration等遍历方式。

2.6 数组初始化和扩容机制不同

在默认情况下，Hashtable的初始容量为11，而HashMap为16。

Hashtable不要求底层数组的容量一定是2的整数幂，而是将容量变为原来的2倍加1；而HashMap则要求一定是2的整数次幂。

八. 关于二叉树与红黑树(拓展)

因为HashMap中涉及到了红黑树的概念，所以这里我对二叉树及红黑树做一个简单的介绍。

1. 排序二叉树

排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左、右子树也分别为排序二叉树。

排序二叉树虽然可以快速检索，但在最坏的情况下，如果插入的节点本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表。

2. 红黑树

红黑树其实是一种自平衡二叉查找树。它的左右子树高度可能大于1，严格意义上来讲，红黑树并不是完全平衡的二叉树。红黑树结构如下图所示：

红黑树在原有的排序二叉树的基础上，增加了如下几个要求:

• 性质1: 每个节点要么是红色，要么是黑色；
• 性质2: 根节点永远是黑色的；
• 性质3: 所有的叶节点都是空节点(即null)，并且是黑色的；
• 性质4: 每个红色节点的两个子节点都是黑色(从每个叶子到根的路径上不会有两个连续的红色节点)；
• 性质5: 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

上面的性质3中 指定红黑树的每个叶子节点都是空节点，而且叶子节点都是黑色的。但 Java 实现的红黑树是使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，只能看到每个叶子节点都是红色的。

九. 结语

至此，壹哥 就带各位把HashMap的特点、底层原理、源码、扩容机制、冲突解决等各种常见问题都复习完毕，可以说这是目前为止最难搞、也最复杂的一个知识点了。请各位一定要把HashMap熟练掌握，因为这一块在面试时真的是必考题！

壹哥 写了6篇文章，将近5w字专门介绍HashMap，不知道你现在对HashMap还有什么不明白的地方吗？请在评论区留言给壹哥吧。如果各位觉得壹哥的文章还不错，请给壹哥来个点赞评论收藏3连击吧。