HashMap

HashMap

基本结构

理想状态下，HashMap 查找的时间复杂度为 O(1)；

JKD 8 之后，HashMap 使用数组 + 链表 + 红黑树的结构；在此之前，使用数组 + 链表；

• 数组：HashMap 是 key-value 的形式进行存储，key + value 以 Entry 对象的形式存入数组

下标：通过 key 获取对应的 hash，再根据 hash 值与数组最大索引进行按位与运算（都转为二进制，依次对比，都为 1 返回 1，否则返回 0），得到的值就是下标

• 链表：当数据量很大时，必然会出现下标冲突的问题（哈希碰撞），HashMap 是通过拉链法解决这个问题的

• 红黑树：链表查询速度太慢，当链表长度很长的时候，对应 HashMap 的取值操作会非常耗费时间，

  当链表长度大于 8 时，链表自动转为红黑树，红黑树是一个平衡二叉树，可以提高查询效率

排序二叉树：左子树结点的值都小于或等于根节点，右子树结点的值都大于或等于根节点，且左右两个子树都是一棵排序二叉树

平衡二叉树：本质是特殊的排序二叉树，满足：左右两个子树的高度差的绝对值不超过 1（平衡因子为 -1、0、1），且左右两个子树都是一棵平衡二叉树

红黑树：是一个平衡二叉树；满足：

• 结点是红色或黑色
• 根结点是黑色
• 每个叶子结点都是黑色的
• 每个红色结点的两个子结点都是黑色（从每个叶子结点到根节点的所有路径上不能有两个连续的红色结点）
• 从任意结点到其每个叶子结点的所有路径都包含相同数目的黑色结点

构造

HashMap 的无参构造只做一件事，设置 loadFactor（负载因子）= 0.75，并没有创建数组，HashMap 的数组是按需创建的，只有在创建 HashMap 并且添加数据的情况下才会创建数组；创建数组的默认长度是 16：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 右移4位

容量（capacity）：HashMap 中桶的数量，默认长度为 16

负载因子（loadFactor）：用来判断 HashMap 是否需要进行扩容，计算公式：loadFactor = 存入元素总和 / capacity，所以当存放的数据大于 12 时，就进行数组扩容；扩容方法：* 2，扩大一倍，桶的数量上限为 64

添加数据 putVal

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

首先通过 key 获取对应 hash

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key 为 null 时，hash 值赋为 0，即自动将该条数据存入数组第一位

(h = key.hashCode()) ^ (h >>> 16)

其中，>>> 无符号右移，h >>> 16 取出 h 的高 16位；则非空的 key，hash 值为其 hashCode 与自己的高 16 位进行按位异或运算；如：

0000 0100 1011 0011 1101 1111 1110 0001
>>> 16 //高16位取出来，放到低位，高位补0
0000 0000 0000 0000 0000 0100 1011 0011
异或运算：
0000 0100 1011 0011 1101 1011 0101 0010

（详解 028-2）取出自己的高 16 位，异或混合自己的低位，以此加大低位的随机性，降低冲突的可能性；这样可以在数组长度比较小的时候保证高低位都能参与运算，使散列更加均匀，减少碰撞几率；

拿到 key 的 hash 之后，再将 hash 与数组最大索引进行按位与运算，最终得到索引；如数组长度为 16 时：

h = hashCode()         1111 1111 1111 1111 1111 0000 1110 1010
h >>> 16               0000 0000 0000 0000 1111 1111 1111 1111
hash = h ^ h >>> 16    1111 1111 1111 1111 0000 1111 0001 0101
15                     0000 0000 0000 0000 0000 0000 0000 1111
15 & hash              0000 0000 0000 0000 0000 0000 0000 0101

链表和红黑树转换时机：数组长度等于 64，且链表长度大于 8 时：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

注意第一个判断，binCount 是从 0 开始计数的，判断条件为：

binCount >= TREEIFY_THRESHOLD - 1 => binCount+1(链表长度) >= TREEIFY_THRESHOLD

但此时链表新插入了一个节点：

p.next = newNode(hash, key, value, null);

所以链表树化的那一刻，它的真实长度应该是binCount+1+1 => 链表长度 > TREEIFY_THRESHOLD

添加数据完整步骤

1. 根据 key 计算 hash 值；
2. 在 put 时判断数组是否存在，如果不存在，用 resize() 创建默认长度为 16 的数组；
3. 确定存入的 Node 对象的索引，根据 hash 值与数组最大索引进行按位与运算得到下标；
4. 判断该位置是否有元素，如果没有，直接创建一个 Node 存入；
5. 如果有元素，判断 key 是否相同，如果相同，将原来的 Node 赋给一个变量并返回；
6. 如果不相同，需要在原 Node 基础上添加新 Node；首先要判断该位置是链表还是红黑树；
7. 如果是红黑树，将 Node 存入红黑树；
8. 如果是链表，就遍历链表，找到最后一位，将 Node 存入；
9. 将 Node 存入链表最后一位之后，需要判断此时链表的长度是否超过 8，如果链表长度超过 8，且此时数组容量等于 64，则将链表转为红黑树；如果数组容量小于 64，会进行数组扩容，而不是将链表转为红黑树；
10. 判断数组是或否需要进行扩容。