HashMap

目录

HashMap

底层原理

jdk1.8之前是数组加链表的形式，在这之后是数组链表红黑树的形式

put方法的执行流程

扩容机制

细节

头插法 -> 尾插法

线程安全

• 底层原理

  • jdk1.8之前是数组加链表的形式，在这之后是数组链表红黑树的形式

    • 每个数组元素是链表或红黑树的头节点

    • 在同一个数组下标中，出现key不同，就会以链表形式挂在数组下标之下

    • 当数组长度大于等于64，且链表长度超过默认值8，链表就转为红黑树。如果树的节点小于6就会退化为链表

  • put方法的执行流程

    • 首先会计算元素的哈希值，然后调用put方法中的核心方法putval，核心方法的执行流程是，先去检查数组是否初始化或者长度为0，如果满足其一就会执行扩容机制进行初始化操作；然后，计算元素数组下标位置，如果对应的数组下标没有节点，就直接创建新节点插入。如果有节点，需要检查key值是否相同，如果key值相同那就将旧的value值替换成新的value值；如果key值不同，就需要执行对应结构的插入方法，有可能是链表或者红黑树结构。最后，如果数组长度超过阈值需要进行扩容机制，最后返回null；

• 扩容机制

  • 首先判断是哪种扩容，首次扩容，常规扩容，链表长度大于等于8，但是数组长度小于64，优先触发扩容；计算新容量和新阈值；新建数组；迁移原数组元素到新数组；更新阈值；

  • 迁移原数组元素到新数组

    • 只有两种可能，新下标=原下标，新下标=原下表+原容量

      • 原因：新容量=原容量的二倍，原下表的计算:index = hash & (oldCap - 1)，新下标计算：newIndex = hash & (newCap - 1) = hash & (2oldCap - 1)，2oldCap - 1 = (oldCap - 1) | oldCap由于原容量是2的k次方所以形式一定是低位连续的0高位是1，原容量-1的形式一定是低位连续的一

      • 主要还是跟hash的第k位是1还是0有关系，这里的第k位是从0开始数的（0、1、2.....）新容量-1的二进制是连续的1，新容量-1的二进制形式是由原容量的二进制或上原容量-1的二进制，最高位的1是来自原容量的二进制，所以当hash&原容量=1，此时的新下标就是原下标+原容量，当hash&原容量=0，此时的新下标就是原下标

• 细节

  • hashmap有最大容量，2的30次方

  • (n-1)&hash等价于hash%n，位运算效率高于取模

  • 为什么容量是2的幂次方，保证(n-1)&hash的结果均匀分布，否则可能导致某些桶永远无法被访问

  • 扩容阈值=数组容量x负载因子，负载因子默认0.75，这个值对于时间和空间的利用率比较高，如果太大，哈希冲突会比较高，查询插入的速度就会变慢；如果太小，就会造成空间浪费

  • 时间复杂度由 O n -> O logn

  • 头插法 -> 尾插法

    • 在迁移链表的时候，头插法是先从原链表的头节点插入新下标，然后其他节点依次插入到新下标的头节点，最后相当于把原链表的节点顺序在新链表中倒过来了

    • 头插法可能出现死循环，头插法是倒着插，多线程环境下会把指针插反，形成闭环

    • 尾插法next指针只会被修改一次，可能会造成节点遗漏但是不会造成死循环

• 线程安全

  • 非线程安全，多个操作都是非原子性的，没有加锁机制或者cas操作等等，主要是对于单线程高性能提供，如果需要并发安全，可以使用 ConcurrentHashMap