开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> HashMap学习（一）（基于JDK 1.8) -> 正文阅读

[数据结构与算法]HashMap学习（一）（基于JDK 1.8)

1. 絮絮叨叨

关于HashMap的源码解读，网上一查一大堆
讲的虽然大同小异，作为菜鸟，总怕哪个知识点没注意到，就错过了一个亿 😂
同时，自己还需要对这些知识进行筛选、鉴别、整合
想要有底气的说：这个地方写的不对，就要多研究源码才行
从JDK 1.8开始，HashMap的底层结构从桶数组 + 链表，变成 桶数组 + 链表 + 红黑树，以解决链表过长导致查找效率退化成 $O (n)$ 的问题

1.1 处理hash冲突的方法

HashMap基于哈希表实现，entry数量增加、hash计算不均匀等，出现hash冲突是无可避免的
HashMap采用拉链法解决hash冲突，即相同hash值的entry放在同一个桶中，并以链表的形式连接
哈希表中，桶其实就是数组中的一个位置；哈希表的实质是数组，又称桶数组

经典的面试问题： hash冲突时，entry是插入链表的头部还是尾部？

JDK 1.8以前，使用头插法：直接将原链表作为新entry的next

// JDK 1.6
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // e赋值给新nentry的next
    if (size++ >= threshold)
        resize(2 * table.length);
}

JDK 1.8中，使用尾插法：putVal()方法中，当p是链表末尾节点时，将新的entry作为其next

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}

感谢博客：HashMap到底是插入链表头部还是尾部

除了拉链法，还有以下三种处理hash冲突的方法

再哈希：发生hash冲突时，使用更多的hash函数计算地址，直到无冲突为止
开放定址法：发生hash冲突时，使用 $\% m$ 计算新的地址，直到无冲突为止
（1）线性探测：di = 1, 2, 3, 4, … , m - 1
（2）平方探测：di = $1^2$ , $1^2$ , $2^2$ , $2^2$ , … , $k^2$ , $k^2$
（3）随机探测：di是一组伪随机数
建立公共溢出区：哈希表分为基本表和溢出表，凡是和基本表发生冲突的，都记录到溢出表中（网上讲解几乎都是偏概念性的，具体如何实现需要深入学习）

1.2 HashMap的特性

之前，了解一个类几乎都是网上搜索这个类的详解，然后看看是否满足需求
学习HashMap时，让我惊喜地发现，想要了解一个类，多看类注释是一个非常好的方法

HashMap的类注释中，包含了以下信息：

HashMap实现了Map接口，允许key或value为null（至多一个key为null，可以多个value为null）
HashMap不保证entry的顺序（如插入顺序或key的自然顺序），相反，entry的顺序还可能在一段时间内发生改变（扩容时，需要rehash）

rehash实际是哈希表扩容（resize）后，重新计算哈希以更新位置的操作，rehash可以等价于扩容
HashMap是非线程安全的：
（1）多线程下使用，要么选择线程安全的兼容类，如ConcurrentHashMap
（2）要么通过 Collections.synchronizedMap()将其转为线程安全的类，且最好在创建时就进行转化，避免出现意外的不同步访问
（3）与HashTable的区别：HashTable是线程安全的，但不允许key或value为null
HashMap使用fail-fast迭代器：一旦创建了迭代器，除非使用迭代器的remove方法，其他任何改变HashMap结构的方法都将使得迭代器抛出ConcurrentModificationException异常
initial capacity、load factor、threshold对HashMap的影响
（1）capacity，容量，哈希表中桶的数量；initial capacity，初始容量，创建哈希表时的容量（默认DEFAULT_INITIAL_CAPACITY为16）
（2）loadFactor：装载因子，哈希表能够使用的比例，即哈希表的full程度（默认DEFAULT_LOAD_FACTOR为0.75）
（3）threshold，当HashMap中的entry数超过threshold时，哈希表将被扩容至当前桶数量的2倍
（4）threshold = capacity * loadFactor，注意： 在哈希表尚未分配内存时，threshold中存储的是initial capacity，具体见下文
（5）尽量设置HashMap的初始容量为一个较大值，避免数据量较大时频繁resize（扩容）；阿里的《Java开发手册》中规定，initialCapacity = (需要存储的元素个数 / 负载因子) + 1，以避免会出现resize
（6）迭代操作的时间与桶数组的大小（capacity）和entry的数量都有关系，不能将capacity设置的太高（哈希表占用的存储空间更大）或将loadFactor设置的太低（容易触发rehash）
（7）loadFactor设置为0.75在时间和空间上有一个很好的折中：loadFactor越高，降低了空间开销，但增加了查找成本。

loadFactor越高，越不容易触发扩容操作，哈希表的长度越小；但是出现hash冲突的可能性变大，查找操作更耗时
不同key的hashCode应该尽量不同：这样可以减少哈希冲突，从而减少链表长度；如果链表长度过大，应该考虑使用比较顺序来组织具有相同hashCode的key（链表转红黑树）

参考链接：

2. HashMap概述

2.1 类图

HashMap类的声明如下：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

类图，如下图所示

从类图解读HashMap

直观地看：HashMap继承了AbstractMap抽象类，实现了Map、Cloneable、Serializable接口
AbstractMap抽象类：实现了Map接口，对Map接口进行了骨架级实现，极大减少了实现Map接口所需的工作量
Map接口：是map体系的基础接口，定义了各种与map操作有关的方法，是对Dictionary完全抽象类的替代
Cloneable接口：说明HashMap支持clone操作
Serializable接口：说明HashMap支持序列化与反序列化

疑问： 为什么继承了AbstractMap类，还需要实现Map接口？

从类图中，我们可以看出AbstractMap类本身就实现了Map接口。
HashMap不仅继承了AbstractMap类，还实现了Map接口，这样的写法显得多此一举
原因一： JDK源码这样写是有原因的，例如，可以通过发射中的getInterfaces()方法直接获取到Map接口
原因二： 这就是当时作者Josh Bloch的一个失误
- 最开始，他认为这样写在某些地方可能是有价值的，直到他意识到错了
- JDK的维护者不认为这个小小的错误值得修改，就一直保留了下来
- 实际上，去除Map接口，整个HashMap仍然能正常运行
参考链接：
- Why does LinkedHashSet extend HashSet and implement Set （正是从这个提问的回答中，大家才知道这是作者的一个失误）
- HashMap既然继承了AbstractMap为什么还要实现Map（上述Q&A的英文翻译）
- 为什么HashMap继承了AbstractMap还要实现Map接口（提出了两种原因）
- 错误写法的佐证：HashMap中为什么既继承AbstractMap又实现Map接口呢？

2.2 成员变量

HashMap中存在很多static final的成员变量（类常量），这些类常量与HashMap的扩容、树化（转红黑树）等有关

// 哈希表的容量/长度（桶大小），必须为2的幂，默认值16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 哈希表的max容量，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 装载因子，默认值0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 单个桶中，链表转红黑树的阈值：大于8，链表转红黑树
static final int TREEIFY_THRESHOLD = 8;
// 单个桶中，红黑树转回链表的阈值：小于等于6
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表转红黑树的阈值，大于64
static final int MIN_TREEIFY_CAPACITY = 64;

实例变量

// 桶数组，大小总是为2的幂
// 并非创建时就分配内存，而是第一次使用时分配
transient Node<K,V>[] table;
// 缓存的entrySet
transient Set<Map.Entry<K,V>> entrySet;
// 哈希表中entry（键值对）的数量
transient int size;
// HashMap结构被修改的次数，如put、remove，用于实现fail-fast迭代
transient int modCount;
// 扩容的阈值 =  capacity * loadFactor，大于阈值就扩容；可能会存储initial capacity
int threshold;
// 装载因子，哈希表的full程度
final float loadFactor;

2.3 构造函数

HashMap的构造函数如下：

public HashMap(int initialCapacity, float loadFactor) {
    // 入参校验
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 会将输入的initialCapacity转为大于该值的、最小的2的幂（本文称为最近2的幂）
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 构建一个指定initial capacity的HashMap，loadFactor将使用默认值0.75
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 不指定任何参数的HashMap，initial capacity和loadFactor都将使用默认值
public HashMap() {
    // 第一次使用时，桶数组大小为16
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 从已有的map构建一个HashMap，loadFactor使用默认值
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

疑问一： tableSizeFor()方法是如何计算一个数最近2的幂呢？

tableSizeFor()方法的代码如下：

static final int tableSizeFor(int cap) {
    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;
}

代码中，不停进行带符号右移、异或的计算，是为了计算cap的掩码
掩码计算出来以后+1，就是cap最近2的幂
具体的数学原理不做深究，要想验证想法可以自己找个数进行计算，也可以查看博客：HashMap 源码详细分析(JDK1.8)

疑问二： 第一个构造函数，为何initial capacity变为2的幂后，赋值给了threshold？

根据之前的学习，threshold表示的是HashMap扩容的阈值，并非哈希表的容量
将initialCapacity转为大于该值的、最小的2的幂后，却赋值给了threshold这个变量，这咋看觉得是代码没写对 😂

查看扩容方法resize()，发现通过该构造函数创建的HashMap第一次扩容时

oldCap = 0，oldThr为threshold，假设为32
此时，会满足条件判断的情况2，将oldThr赋值给newCap

也就是说newCap的值将变成threshold的初始值，32

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) { // 情况1
        // ...
    }
    else if (oldThr > 0) // 情况2
   		// table未初始化，但threshold大于0，说明initial capacity存储在threshold中
        newCap = oldThr;
    else { // 情况3
        // 对应构造函数public HashMap() ，threshold为0，newCap和newThr使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // ...
}

为什么搞得这么麻烦呢？后来想想，也是有原因的
- HashMap中，initialCapacity没有对应的实例变量，只有一个类变量DEFAULT_INITIAL_CAPACITY来记录其默认值
- 作者巧妙地借助threshold，实现了initialCapacity的存储、各种初始化情况的判断

2.4 确定桶下标

想要查找、增加或删除一个entry，都需要先确定这个entry的桶下标
entry在哈希表中的位置，取决于key的哈希值，计算桶下标应该先key的计算哈希值
HashMap中，哈希值的计算方法如下：
（1）key为null，则直接返回0，即null的哈希值默认为0；
（2）key不为null，先获取的key的hashCode，再异或上该hashCode无符号右移16位的结果
```
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

桶下标的计算：

// n为桶数组的容量
(n - 1) & hash

疑问一： 计算桶下标，为什么不直接使用hash % n？

hash % n与(n - 1) & hash二者的结果是一样的，位运算和数学运算之间，肯定选择具有先天优势位运算

例如，n = 16， hash = 18，直接进行%计算，桶下标为2；位运算的结果也是2：

hash        :   0001 0010
n - 1       :   0000 1111
(n - 1) & hash: 0000 0010

疑问二： 为什么不直接使用key的hashCode？

hashCode为32位，由于n的值一般很小（不超过65536）
如果直接将hashCode & (n - 1)，这时hashCode只有低16位的数据参与了计算
计算出来的哈希值存在散列不均匀的情况
因此将hashCode无符号右移16位，然后异或上原始的hashCode，可以让高16位也参与到哈希值的计算中
从而哈希值的散列更加均匀，发生哈希碰撞的概率也就更低

2.5 重要数据结构

之前学习TreeMap时，TreeMap的entry（红黑树的节点）起码也叫Entry

对本人来说，学习起来还是挺容易关联的

static final class Entry<K, V> implements Map.Entry<K, V> { // 代码省略}

HashMap中entry对应Node或继承了Node的TreeNode，一下子让本人变得不适应
不过想想，作者这样起名也是有道理的，这是一个链表节点或树节点，叫Node无可厚非

Node的定义如下：

作为一个构建链表的节点，它的value应该是：key、value（映射），然后还有一个next引用
除此之外，避免使用该节点的哈希值时，每次都重新计算哈希值，还增加了一个hash字段用于存储哈希值

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;

   Node(int hash, K key, V value, Node<K,V> next) {
       this.hash = hash;
       this.key = key;
       this.value = value;
       this.next = next;
   }
}

TreeNode定义如下：

TreeNode继承了LinkedHashMap.Entry，而LinkedHashMap.Entry 又继承了HashMap.Node
可以说，TreeNode最终还是继承了HashMap自身的Node
TreeNode中，除了红黑树常见的parent、left、right、red（color），还有一个prev引用

prev和next一起，用于在树化后，依然保留原链表的节点顺序

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 实现双向链表的关键
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}