Java 集合框架之HashMap

1. Hash (散列)

通过散列算法把任意长度的输入变换成固定长度的散列值

特征：
同一散列函数计算出的散列值如果不同，那么输入值肯定也不同
同一散列函数计算出的散列值如果相同，输入值不一定相同

1.1 Hash碰撞

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞

1.2 Hash函数

• 开放定址法(Open Addressing)
• 再哈希法(Re-Hashing)
• 链地址法(Separate Chaining)
  • 链地址法将数组和链表组合，可以理解为链表的数组
  • 数组寻址容易，插入和删除困难；而链表寻址困难，插入和删除容易

2. HashMap

• HashMap 是一个利用 Hash 表原理来存储元素的集合，Hash 冲突时，采用链地址法
• JDK8 相比 JDK1.7 的改进
  • 取消 segment 分段设计
  • 增加红黑树的实现

Java8 HashMap 结构：数组 + 链表 + 红黑树

1. 数组（Array）：HashMap 的基础结构是一个数组，每个数组元素被称为一个“桶”或“槽”（bucket）。当向 HashMap 插入键值对时，首先会计算键的哈希码(hashCode)，然后通过一定的算法（如取模运算）将哈希码转换为数组的索引位置。
2. 链表（LinkedList）：对于哈希冲突的情况，即不同的键通过哈希函数映射到了同一个数组索引，HashMap 使用链表来存储这些冲突的键值对。也就是说，数组中的每个元素不仅是一个对象引用，也是一个链表头节点，链表中的每个节点（Node）包含键、值以及指向下一个节点的引用。
3. 红黑树（Red-Black Tree）：在 Java 8 中引入了一个改进，即当某个桶中的链表长度超过阈值（默认是 8）时，该链表会被自动转换成一颗红黑树。（阈值 > 8 并且数组长度大于64,才将链表转换为红黑树，小于 64 时直接扩容）
   红黑树是一种自平衡二叉查找树，它的插入、删除和查找操作的时间复杂度都可以保持在 O(logN)

2.1 主要成员变量

• 加载因子 final float loadFactor;
• 临界值 int threshold;
• 计数器 transient int modCount

2.2 计算初始化容量

static final int tableSizeFor(int cap) {
    // cap - 1 防止传入2的整次幂时返回值大一倍
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

作用：
通过计算，得到第一个比自身大的2的幂

分析：
对一个二进制数依次向右移位，然后与原值取或
复合赋值位运算 (|=按位或赋值)，比如 a |= b 等价 a = a | b
示例：

@Test
public void tableSize() {
    System.out.println("    size: " + Integer.toBinaryString(tableSizeFor(10)));
}
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    System.out.println(" cap - 1: " + Integer.toBinaryString(n));
    System.out.println(" n >>> 1: " + Integer.toBinaryString(n |= n >>> 1));
    System.out.println(" n >>> 2: " + Integer.toBinaryString(n |= n >>> 2));
    System.out.println(" n >>> 3: " + Integer.toBinaryString(n |= n >>> 4));
    System.out.println(" n >>> 8: " + Integer.toBinaryString(n |= n >>> 8));
    System.out.println("n >>> 16: " + Integer.toBinaryString(n |= n >>> 16));
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

打印结果：

 cap - 1: 1001
 n >>> 1: 1101
 n >>> 2: 1111
 n >>> 3: 1111
 n >>> 8: 1111
n >>> 16: 1111
    size: 10000

2.3 hash函数

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

2.4 扩容

默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // ...
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // ...
        }
    }
    return newTab;
}

3. Node 数组

• transient Node<K,V>[] table;

3.1 (单向)链表

static class Node<K,V> implements Map.Entry<K,V> {
    // 用来定位数组索引位置
    final int hash;
    final K key;
    V value;
    HashMap.Node<K, V> next;
}

3.2 红黑树

• 阈值 > 8 并且数组长度大于64,才将链表转换为红黑树

// 树化阈值
static final int TREEIFY_THRESHOLD = 8;
// 树降级为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 树化另一个参数
static final int MIN_TREEIFY_CAPACITY = 64;

4. 其他

• HashMap 类允许键和值为 null

1. 用 hashCode 结合数组长度计算出索引值
2. 当索引值一样时，比较 hash 值
   2.1 不一致：划出一个节点存储
   2.2 一致：哈希碰撞，再去比较内容是否相等
   2.2.1 相等：后面的 value 覆盖之前的 value
   2.2.3 不相等：继续向下和其他数据的 key 进行比较，如果都不相等，则划出一个节点存储