HashMap

数据结构

JDK8之前，数组+链表

JDK8之后，数组+链表+红黑树

1、基础数据结构是数组，每一对key->value的键值对组成Entity类，以双向链表的形式存放到数组中

2、元素在数组位置由key.hashCode()决定，如果两个key的hash值相等，即哈希碰撞，则这两个key对应的Entity将以链表的形式存放在数组中

3、HashMap.get()，计算key.hashCode找到key位置，遍历该位置上的链表找到对应的值

4、桶数组大小，2的正整数幂，通过构造位运算实现快速寻址，减少哈希碰撞，扩容后同一个桶中元素均匀散列到新桶中

元素大小=桶数组大小*负载因子0.75

JDK8中，如果同一个位置链表数量超过一个定值，整个链表有一定概率转为一颗红黑树

1、调用key的hashCode方法，计算出数组下标index

2、如果当前桶数组为null，则调用resize方法初始化

3、如果没有哈希碰撞，则直接放到对应的桶中

4、如果发生哈希碰撞，且节点已经存在，则替换value

5、如果发生哈希碰撞，且桶中存放树状结构，则挂载到树上

6、如果碰撞后为链表，则添加到链表尾，超过TREEIFY_THRESHOLD默认值8，将链表转为树结构（小于6转回）

7、数据put完成，元素超过负载，进行扩容

放在桶数组下标为0的桶中