这个问题，面试几乎次次问，但每次我也只知道个数组＋链表（/(ㄒoㄒ)/~~），偶尔有个面试官深入问我就慌了，还是得好好理解一下。

hashmap的整体结构示意如下： alt HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。

简单来说，HashMap由数组+链表组成的（拉链法），数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。HashMap是无序的。

在JDK1.8以后，HashMap的实现是数组＋链表／红黑树的方式，如下图： alt 这种方法可以大大优化了哈希冲突的问题，减少了搜索时间，当添加的数目达到阈值的时候可以将链表转换为红黑树的形式，而当红黑树的节点小于6的时候就会从红黑树转化为链表的形式，而在进行插入值的时候则采用的是尾插法的形式，这种方法解决了成环的情况发生。

如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；

如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。

所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组。

当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。

参考：https://juejin.cn/post/6844904018733432845

发现一个总结得很全的博客：https://zhuanlan.zhihu.com/p/380375038