HashMap 原理解析
-
hashmap构造
hashmap 默认的初始数组容量大小为16,默认加载因子为0.75,默认阀值为16*0.75 = 12
-
如果指定了数组初始大小不为2的n次幂,最终会将数组容量指定为2的n次幂
为什么需要将数组容量设计为2的n次幂?方便后续通过key取数组index时取模运算,提高效率
-
resize()方法原理
扩容分两种情况:
hashmap 首次初始化
-
hashmap 的节点数目已经超过阀值
新增一个数组,数组大小在首次初始化时默认为16,在超过阀值扩容的情况下为原数组的两倍
遍历旧数组,如果节点没有链表,就将节点的hash 与 新数组的length -1 取模,得出新数组的index存放
-
如果出现链表
判断是否为红黑树,如果是,就调用红黑树的拆解方法(具体不清楚)
-
如果不是,迁移到新数组的index只有两种情况,要么跟旧数组的index一致,要么为旧数组的index+旧数组的length
JDK1.8 采用的是尾插,这样可以保证原有链表的顺序,避免在多线程下产生环形链表
为什么是这两种情况?跟hashmap的数组大小总为2的n次幂有关系,新的位置取决于hashcode 高一位的数组,1表示新位置,0表示原位置
-
put(key,value)方法流程
-
将key通过hash()方法得出hash值,为了得到的hash值分布更均匀,将hashcode右移16位,让高低位都参与运算
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) 公共hash值,与数组length-1 与运算,得出数组下标index
判断index下是否已经有值,如果没有值,直接new一个新节点,并插入
-
如果有值,就比较这个节点的key是否相等
比较节点的key是否相等,是通过
== || equals()来进行判断,== 对基本数据类型是比较的值,对引用型对象比较的是地址值如果相等,就覆盖此值
-
如果不相等,判断链表长度是否超过了8
超过了8,转为红黑树结构
没超过8,就遍历链表,看链表是否有节点的key值相等,如果有,就覆盖值,如果没有,就生成一个新节点插入到链表尾部
判断节点个数是否超过了加载因子,如果超过就扩容
-
面试
了解HashMap的原理吗?
1.HashMap 是一种数组 + 链表 数据结构,HashMap在存数据时,会根据key生成的hashcode 与 数组length -1 进行 与运算,得到数组的下标index,如果此index位置上还没有值,就直接插入,如果有值,会判断链表长度是否超过了8,超过了就转换为红黑树,没超过就将value转为一个note节点插入到链表的尾部
2.如果数组的节点size超出了阀值,会进入resize()扩容,扩容时会new一个新的数组,数组长度是原数组的两倍,然后根据key的hashcode与新数组length-1进行与运算,得到新的index,并将值赋值过去
