date: 2023-02-14
版本差异
- JDK1.7以及之前 底层数据结构是数组加链表
- JDK1.8开始 底层数据结构是数组加链表加红黑树
JDK1.8之后的HashMap
默认数组长度：16 设计考虑：由于在寻址算法时，16-1为15，其二进制数各个位都为1，为了使得数据更加分散而设计。长度为8或者为32均可，此考虑是综合之前jdk的使用频次而默认值为16
put(key,value);实现原理：
- 首先会将该key和value封装成一个对象（entry对象）
- 根据该对象key的hashCode(方法)计算出一个int类型的哈希值
- 使用Hash扰动算法（高16位去异或低16位）得到一个扰动后的hash值
- 使用寻址算法（上述哈希值对数组长度进行取模，而在实现的时候是使用上述扰动后的哈希值去与上数组长度-1）计算出该元素落在数组中的那个索引位置上。
- 当计算出该元素落在哪个索引上，然后判断该处是否有节点，如果有，比较HashCode是否相同，如果相同，则将新value替换旧value。
- 如果有下一个节点，则重复上一个过程，直到next为空，将该节点插入链表尾部。
HashMap扩容
- 当map中的元素数量达到阈值的时候，数组长度会进行扩容为原来的两倍。原来的哈希表里面的所有元素会重新计算位置，要么保持原来的位置不变，要么是原来位置加12.
- 阈值： 计算公式：数组长度*负载因子 负载因子默认是0.75，之所以是0.75是根据统计学中的泊松分布概率所得。
JDK1.8引入红黑树
当哈希冲突7次，链表的长度达到8，且数组长度达到64，该链表形成红黑树，当他的根节点小于等于6则退化成链表。
注意：本文归作者所有，未经作者允许，不得转载
