HashMap内部机制解析原理分析原理解析

数据结构

jdk1.8之前：数组+链表
jdk1.8及之后：数组+链表+红黑树

容量

创建一个map对象时一些参数属性被赋予默认值。

1. 参考容量（capacity）
   map对象中Node[]数组的初始长度（容量）默认16。可以new HashMap<>(capacity)指定长度。
   注意：hashMap内部有一个机制，创建map对象中Node[]数组的初始长度是2的n次方，例如当你设置长度23时，
   hashMap会把初始长度设置为32(23在 2的4次方(16)到2的5次方(32)之间)，取最大的数32。
2. 扩容阈值（threshold）
   在新增元素的过程中，如果达到扩容阀值就会扩大Node[]数组的长度，默认值=参考容量*负载因子。
3. 负载因子（loadFactor）
   默认值为0.75，可以修改但不建议。

负载因子 loadFactor

//默认是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

为什么是0.75？
官方解释：一般来说，默认的负载因子0.75在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销但增加了成本。

如果设置成1，容量使用默认初始值16，那表示一个hashMap需要在“满了”之后才会进行扩容。
最好的情况是这16个元素分别落到了不同的桶(Node[]的index)中，否则就必然发生哈希碰撞，随着元素原来越多 哈希碰撞的概率越大查找速度也会越低。

map.put(key)原理

1. 计算出key的hash值
2. 判断Node[]数组是否为空，为空按照初始长度开辟数组空间
3. 得到数组下标,求余：index = hash值 % 数组长度。为提高效率,减一运算：index = hash值 % (数组长度 - 1)
4. 把值赋值给对应的Node：hash值、key、value、next，位置上的第一个元素后面没有链表元素所以next是空的
5. 插入元素，全局变量size +1，如果大于扩容阀值就要扩容
   1. 不同key不同index：直接插入
   2. 相同的key：先比较hash值相等，在通过==和equals判断相等，直接覆盖原值
   3. key不同相同index：这就是哈希冲突，插入到这个位置的最后一个元素后面形成链表。把当前元素赋值给上个元素的next。
      不过插入前回显遍历当前位置上的所有元素，如果发现相同key时覆盖，没有相同key则追加。
   4. 当链表的元素数量达到8时，且数组总容量超过64，链表自动转成红黑树，来提升遍历效率。

扩容机制

扩容过程简单来说就是新建一个长度为原来的2倍的数组Node[]（因为要满足2的n次方），然后把旧数组和链表上的元素全部转移到新的Node[]。

map.get(key)原理

1. 获取key的hash值，得到在数组中的下标
2. 通过下标定位位置，如果位置上什么都没有则返回null
3. 遍历链表比较每个节点的key进行equals，如果equals方法返回true，get方法返回value，否则返回null。