来自华为开发者社区！深度解析HashMap底层实现架构

　　Map接口大家应该都听说过吧？它是在Java中对键值对进行存储的一种常用方式，同样其中的HashMap我相信大家应该也不会陌生，一说到HashMap，我想稍微知道点的小伙伴应该都说是：这是存储键值对的，存储方式是数组加链表的形式。但是其中真正是如何进行存储以及它的底层架构是如何实现的，这些你有了解吗？
　　在Java开发的面试之中，HashMap底层实现的提问和考察已经是司空见惯的了。今天就来和大家分析一下Map接口的详细使用以及HashMap的底层是如何实现的。
　　1、Map接口和List接口是什么关系？
　　对于这个问题，如果非要说这两个接口之间存在怎样的关系的话，那无非就只有一个，就都是集合。存放数据的。在其他上面，Map接口和List接口的联系其实并不大，为什么这么说？
　　先来看List接口，关于List接口我在之前也和大家提到过，它是继承于Collection接口的，是Collection接口的子接口，只是用于对数据的单列存储。继承关系如下图：
　　而Map接口是一个顶层接口，下面包含了很多不同的实现类，它是用于对键值对（key:value）进行存储的，继承关系如下图：
　　2、Map有哪些常用的实现类？
　　上面关于Map的继承结构我们已经了解了，我们也看了其中很多不同的实现类，这些类很多也是我们比较熟悉的，比如HashMap、TreeMap以及HashTable。在面试的时候，面试官往往就还会问，Map接口下有哪些常用的实现类以及它们的作用，那么接下来我们就来对这几个接口进行简单的介绍和分析一下。
　　HashMap:上面也说了，HashMap的底层实现是数组+链表+红黑树的形式的，同时它的数组的默认初始容量是16、扩容因子为0.75，每次采用2倍的扩容。也就是说，每当我们数组中的存储容量达到75%的时候，就需要对数组容量进行2倍的扩容。
　　HashTable:HashTable接口是线程安全，但是很早之前有使用，现在几乎属于一个遗留类了，在开发中不建议使用。
　　ConcurrentHashMap:这是现阶段使用使用比较多的一种线程安全的Map实现类。在1.7以前使用的是分段锁机制实现的线程安全的。但是在1.8以后使用synchronized关键字实现的线程安全。
　　其中关于HashMap的考察和提问在面试中是最频繁的，这也是在日常开发中最应该深入理解和掌握的。所以接下来就主要和大家详细分析一下HashMap的实现原理以及面试中的常考问题。
　　3、请阐述HashMap的put过程？
　　我们知道HaahMap使用put的方式进行数据的存储，其中有两个参数，分别是key和value，那么关于这个键值对是如何进行储存的呢？我们接下来进行分析一下。
　　注意：这里所说的相同并不一定是key的数值相同，而是存在某种相同的特征，具体是哪种特征让我们继续往下看！
　　HashMap将将要存储的值按照key计算其对应的数组下标，如果对应的数组下标的位置上是没有元素的，那么就将存储的元素存放上去，但是如果该位置上已经存在元素了，那么这就需要用到我们上面所说的链表存储了，将数据按照链表的存储顺序依次向下存储就可以了。这就是put的简单过程，存储结果如下：
　　但是我们有时候存储的数据会很多，那么如果一直使用链表的形式进行数据的存储的话就或造成我们的链表的长度非常大，这样无论在进行删除还是在进行插入操作都是十分麻烦的，因此对于这种情况应该怎么办呢？
　　这里就涉及到了一个链表中数据存储时，进行＂树化＂和＂链化＂的一个过程，那么什么是＂树化＂和＂链化＂呢？
　　当我们在对键值对进行存储的时候，如果我们在同一个数组下标下存储的数据过多的话，就会造成我们的链表长度过长，导致进行删除和插入操作比较麻烦，所以在java中规定，当链表长度大于8时，我们会对链表进行＂树化＂操作，将其转换成一颗红黑树（一种二叉树，左边节点的值小于根节点，右边节点的值大于根节点），这样我们在对元素进行查找时，就类似于进行二分查找了，这样的查找效率就会大大增加。
　　但是当我们进行删除操作，将其中的某些节点删除了之后，链表的长度不再大于8了，这个时候怎么办？难道就要赶紧将红黑树转化为链表的形式吗？其实并不是，只有当链表的长度小于6的时候，我们才会将红黑树重新转化为链表，这个过程就叫做＂链化＂。
　　4、链表中是按照怎样的顺序存放数据的？
　　我们现在已经知道了HashMap中的元素是如何存放的，但是有时候面试官可能还会问我们，在HashMap中，向链表中存储元素是在头结点存储的还是在尾节点存储的？
　　这个我们需要知道，对于HashMap中链表元素的存储。
　　在JDK1.7以及前是在头结点插入的，在JDK1.8之后是在尾节点插入的。
　　本文分享自华为云社区《【图文并茂】深度解析HashMap高频面试及底层实现结构！【奔跑吧！JAVA】》，原文作者：灰小猿 。