HashMap原理解析

HashMap 原理解析

• hashmap构造

  1. hashmap 默认的初始数组容量大小为16,默认加载因子为0.75,默认阀值为16*0.75 = 12

  2. 如果指定了数组初始大小不为2的n次幂,最终会将数组容量指定为2的n次幂

     为什么需要将数组容量设计为2的n次幂?方便后续通过key取数组index时取模运算,提高效率

• resize()方法原理

  扩容分两种情况:

  1. hashmap 首次初始化

  2. hashmap 的节点数目已经超过阀值

     • 新增一个数组,数组大小在首次初始化时默认为16,在超过阀值扩容的情况下为原数组的两倍

     • 遍历旧数组,如果节点没有链表,就将节点的hash 与 新数组的length -1 取模,得出新数组的index存放

     • 如果出现链表

       • 判断是否为红黑树,如果是,就调用红黑树的拆解方法(具体不清楚)

       • 如果不是,迁移到新数组的index只有两种情况,要么跟旧数组的index一致,要么为旧数组的index+旧数组的length

         JDK1.8 采用的是尾插,这样可以保证原有链表的顺序,避免在多线程下产生环形链表

         为什么是这两种情况? 跟hashmap的数组大小总为2的n次幂有关系,新的位置取决于hashcode 高一位的数组,1表示新位置,0表示原位置

• put(key,value)方法流程

  1. 将key通过hash()方法得出hash值,为了得到的hash值分布更均匀,将hashcode右移16位,让高低位都参与运算

     (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

  2. 公共hash值,与数组length-1 与运算,得出数组下标index

  3. 判断index下是否已经有值,如果没有值,直接new一个新节点,并插入

  4. 如果有值,就比较这个节点的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,并将值赋值过去