1.HashMap底层采用的存储结构

1.在JDK1.7及之前采用的存储结构是数组+链表

我们知道链表的优点是适合增删，但是存储的数据很多时查找的效率会很低，因此针对查找效率低的问题，对HashMap的存储结构进行了改进。

2.到了JDK1.8之后采用的是数组+链表+红黑树

保留了JDK1.7增删效率高的优点，由于增加了红黑树查找效率也提高了。
（1）首先解释一下什么是红黑树:红黑树是一个自平衡二叉树，查找效率很高。红黑树有以下几个特点：
1)每个节点只有两种颜色：红色或黑色
2）根节点必为黑色
3）每个叶子节点都是黑色的空节点
4）从根节点到叶子节点，不能出现两个红色的节点
5）从任一节点出发，到它下边的子结点的路径包含黑色节点数相同。

2.HashMap实现的原理

HashMap基于hashing的原理，通过提供put()和get()方法来存储和获取对象。

1.put()方法。

当把键值对的值传递给put()方法时，会调用hashCode()方法来计算hashcode，然后找到bucket位置来存储。

2.get()方法。

当要获取对象时，通过键对象的equals方法找到正确的键值对，然后返回值。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在下一个节点中。

3.HashMap源码分析

1.默认的初始化容量为16（2的n次幂），最大容量为2^30
2.默认的加载因子0.75，乘以数组容量得到的值用来表示元素个数达到多少时需要扩容

*0.75的原因：
（1）若小于0.75，如0.5，则数组长度达到一半大小就扩容，空间使用率降低；
（2）若大于0.75，如0.8，则会增大hash冲突的概率，影响查询的效率。
3.当链表的长度超过8时，转化为红黑树。
4.当红黑树上的元素个数减少到6个时就退化为链表；
5.链表转化为红黑树，除了有阈值的限制，还有一个限制：数组容量至少达到64，才会树化，这是为了避免数组扩容和树化阈值之间的冲突。
6.HashMap的源码如下（来源于知乎）：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

    // 序列号

    private static final long serialVersionUID = 362498820763181265L;    

    // 默认的初始容量是16

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   

    // 最大容量：2^30，超过仍按2^30来算

    static final int MAXIMUM_CAPACITY = 1 << 30; 

    // 默认的填充因子（负载因子/加载因子）

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 当桶(bucket)上的结点数大于这个值时会转成红黑树

    static final int TREEIFY_THRESHOLD = 8; 

    // 当桶(bucket)上的结点数小于这个值时树转链表

    static final int UNTREEIFY_THRESHOLD = 6;

    // 桶中结构转化为红黑树对应的table的最小大小

    static final int MIN_TREEIFY_CAPACITY = 64;

    // 存储元素的数组，总是2的幂次倍

    transient Node<k,v>[] table; // 下面会分析结构源码

    // 存放具体元素的集

    transient Set<map.entry<k,v>> entrySet;

    // 存放元素的个数，注意这个不等于数组的长度。

    transient int size;

    // 每次扩容和更改map结构的计数器

    transient int modCount;   

    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容

    int threshold;

    // 加载因子

    final float loadFactor;

}
原文章：https://blog.csdn.net/weixin_48929324/article/details/112100700

秒客网

HashMap底层实现原理及面试常见问题

HashMap底层源码分析