第一点来说一下HashMap的底层结构为什么使用数组 链表 红黑树?

1. 数组的优点:数组有下标,查询比较快,时间复杂度o(1)
2. 链表的优点:解决hash冲突,当多个插入的值计算的下标,都在同一个下标下(哈希冲突)
3. 红黑树:提高查询速度,链表的时间复杂度是o(N)

第二点来说一下HashMap的put流程

调用put方法插入的时候,先会去计算key的hash值,如果是第一次插入,会先初始化数组,代码使用

(n-1)&hash值,获取数组下标

在插入的过程中,有2种情况:

(1)取出下标内容为null,表明当前节点没有插入过数据,直接插入该节点即可

(2)节点不为null,有可能key是相同的,这时候我们进行覆盖操作,后续会判断该节点是否是红黑树,如果是则进入红黑树逻辑,如果是链表情况,进行循环判断找到链表的最后一个节点,把插入的数据插入到链表最后节点,并判断当前节点key值是否相同,同时计算链表长度是否大于等于7,如果条件成立,判断数据长度是否大于64,都成立的话链表转成红黑树,不成立则进行扩容,之后数组元素个数+1,元素个数如果大于阈值,进行扩容.

代码分析:

public V put(K key, V value) {/*** 1.生成key的hash值* 2.调用putVal方法参数向下传递*/return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;/*** 判断table是不是第一次添加数据，如果是tabl