HashMap

特点
  • 通过对key进行哈希计算得到数组下标，存value.
  • HashMap 键值对，K可为null，只能有一个，V可为null。
  • key为null直接返回数组0位置。

  • 无参构造没有容量，共四个构造方法

    结构

  • 7底层数组+链表节点Entry[]，8数组+链表/红黑树(一种自平衡的二叉树)节点Node[]作为哈希桶。

  • 头插尾插

    扩容

  • 扩容resizes()，第一次16(1<<4)，后续(new = old << 1)2倍。负载因子0.75。

  • 扩容消耗较大。

  • 每次push都会见擦汗是否超过预定的threshold，超过就扩容，整个表里的所有元素都需要按照新的hash算法被算一边，代价较大。

    put

  • table为空初始化。

  • key得到hash，计算数组下标。获得节点判空。
  • 空直接插入。判是否需要扩容（容量阈值），结束。
  • 非空key是否存在，存在直接覆盖。
  • 不存在判断是链表还是树节点，树插入。
  • 链表尾插插入，长度大于8树化，先扩容至64。树化。

  • 7头差法，8尾插。

    树化

  • 普通节点数组Node[]，红黑树数组TreeNode[]，冲突超过8树化，树化前先扩容至64，64是最小树化长度。treeifyBin（）

    线程安全

  • 线程不安全，扩容有可能死锁新家节点的transfor()方法的while，8已解决，

  • 7在并发下会发生死锁，transfer()方法（将新哈希表的数据转移回去）
    • 对索引数组中的元素遍历
    • 对链表上节点遍历，用next取得要转移那个元素的下一个，将e转移到新的hash表的头部，因可能有元素，所以将e.next指向新hash表的第一个元素（如果第一次就null）这时候新hash的第一个元素是e，但hash指向的缺失e没转移时候的第一个，所以将hash表的第一个元素指向e。
    • 循环2
    • 循环1
  • 转移是逆序的，！死锁正式1—>2；2—>1造成的。

  • 8的不安全在putVal，定位下标的时候(与hash位与运算)，若并发可能产生数组覆盖问题。

    重写equals,要重写hash

  • 添加先判断hash，若不重写，默认Object的hash()添加引用对象，hash是根据堆位置生成值，永远不相等。

扩展：红黑树旋转

bili诸葛

Q0：HashMap是如何定位下标的？A：先获取Key，然后对Key进行hash，获取一个hash值，然后用hash值对HashMap的容量进行取余（实际上不是真的取余，而是使用按位与操作，原因参考Q6），最后得到下标。Q1：HashMap由什么组成？A：数组+单链表，jdk1.8以后又加了红黑树，当链表节点个数超过8个（m默认值）以后，开始使用红黑树，使用红黑树一个综合取优的选择，相对于其他数据结构，红黑树的查询和插入效率都比较高。而当红黑树的节点个数小于6个（默认值）以后，又开始使用链表。这两个阈值为什么不相同呢？主要是为了防止出现节点个数频繁在一个相同的数值来回切换，举个极端例子，现在单链表的节点个数是9，开始变成红黑树，然后红黑树节点个数又变成8，就又得变成单链表，然后节点个数又变成9，就又得变成红黑树，这样的情况消耗严重浪费，因此干脆错开两个阈值的大小，使得变成红黑树后“不那么容易”就需要变回单链表，同样，使得变成单链表后，“不那么容易”就需要变回红黑树。Q2：Java的HashMap为什么不用取余的方式存储数据？A：实际上HashMap的indexFor方法用的是跟HashMap的容量-1做按位与操作，而不是%求余。（这里有个硬性要求，容量必须是2的指数倍，原因参考Q6）Q3：HashMap往链表里插入节点的方式？A：jdk1.7以前是头插法，jdk1.8以后是尾插法，因为引入红黑树之后，就需要判断单链表的节点个数（超过8个后要转换成红黑树），所以干脆使用尾插法，正好遍历单链表，读取节点个数。也正是因为尾插法，使得HashMap在插入节点时，可以判断是否有重复节点。Q4：HashMap默认容量和负载因子的大小是多少？A：jdk1.7以前默认容量是16，负载因子是0.75。Q5：HashMap初始化时，如果指定容量大小为10，那么实际大小是多少？A：16，因为HashMap的初始化函数中规定容量大小要是2的指数倍，即2，4，8，16，所以当指定容量为10时，实际容量为16。
Q6：容量大小为什么要取2的指数倍？A：两个原因：1，提升计算效率：因为2的指数倍的二进制都是只有一个1，而2的指数倍-1的二进制就都是左全0右全1。那么跟（2^n - 1）做按位与运算的话，得到的值就一定在【0,（2^n - 1）】区间内，这样的数就刚合适可以用来作为哈希表的容量大小，因为往哈希表里插入数据，就是要对其容量大小取余，从而得到下标。所以用2^n做为容量大小的话，就可以用按位与操作替代取余操作，提升计算效率。2.便于动态扩容后的重新计算哈希位置时能均匀分布元素：因为动态扩容仍然是按照2的指数倍，所以按位与操作的值的变化就是二进制高位+1，比如16扩容到32，二进制变化就是从0000 1111（即15）到0001 1111（即31），那么这种变化就会使得需要扩容的元素的哈希值重新按位与操作之后所得的下标值要么不变，要么+16（即挪动扩容后容量的一半的位置），这样就能使得原本在同一个链表上的元素均匀（相隔扩容后的容量的一半）分布到新的哈希表中。（注意：原因2（也可以理解成优点2），在jdk1.8之后才被发现并使用）Q7：HashMap满足扩容条件的大小（即扩容阈值）怎么计算？A：扩容阈值=min(容量负载因子,MAXIMUM_CAPACITY+1)，MAXIMUM_CAPACITY非常大，所以一般都是取（容量负载因子）Q8：HashMap是否支持元素为null？A：支持。
Q9：HashMap的 hash(Obeject k)方法中为什么在调用 k.hashCode()方法获得hash值后，为什么不直接对这个hash进行取余，而是还要将hash值进行右移和异或运算？A：如果HashMap容量比较小而hash值比较大的时候，哈希冲突就容易变多。基于HashMap的indexFor底层设计，假设容量为16，那么就要对二进制0000 1111（即15）进行按位与操作，那么hash值的二进制的高28位无论是多少，都没意义，因为都会被0&，变成0。所以哈希冲突容易变多。那么hash(Obeject k)方法中在调用 k.hashCode()方法获得hash值后，进行的一步运算：h^=(h>>>20)^(h>>>12);有什么用呢？首先，h>>>20和h>>>12是将h的二进制中高位右移变成低位。其次异或运算是利用了特性：同0异1原则，尽可能的使得h>>>20和h>>>12在将来做取余（按位与操作方式）时都参与到运算中去。综上，简单来说，通过h^=(h>>>20)^(h>>>12);运算，可以使k.hashCode()方法获得的hash值的二进制中高位尽可能多地参与按位与操作，从而减少哈希冲突。Q10：哈希值相同，对象一定相同吗？对象相同，哈希值一定相同吗？A：不一定。一定。Q11：HashMap的扩容与插入元素的顺序关系？A：jdk1.7以前是先扩容再插入，jdk1.8以后是先插入再扩容。Q12：HashMap扩容的原因？A：提升HashMap的get、put等方法的效率，因为如果不扩容，链表就会越来越长，导致插入和查询效率都会变低。Q13：jdk1.8引入红黑树后，如果单链表节点个数超过8个，是否一定会树化？A：不一定，它会先去判断是否需要扩容（即判断当前节点个数是否大于扩容的阈值），如果满足扩容条件，直接扩容，不会树化，因为扩容不仅能增加容量，还能缩短单链表的节点数，一举两得。