HashMap源码阅读笔记

本文在此博客的内容上进行了部分修改，旨在加深笔者对HashMap的理解，暂不讨论红黑树相关逻辑

概述

  HashMap作为经常使用到的类，大多时候都是只知道大概原理，比如底层是由数组+链表+红黑树实现，使用HashMap存储自定义类时需要重写其hashCode和equals方法等等……但对其具体如何实现却知之甚少，本文将作为类似笔记的形式记录笔者的源码阅读方式。（在JDK 1.7及其之前由数组加链表组成，正常情况想我们谈论的均为JDK 1.8及其之后的HashMap。需要注意的是HashMap非线程安全，在多线程下可能会引发多线程问题）

构造方法分析

  HashMap 的构造方法不多，只有四个。HashMap 构造方法做的事情比较简单，一般都是初始化一些重要变量，比如 loadFactor 和 threshold。而底层的数据结构则是延迟到插入键值对时再进行初始化。HashMap 相关构造方法如下：

//构造方法1，也是使用最多的一种
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//构造方法2，可以设置初始容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造方法3，可以设置初始容量和负载因子
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;
    this.threshold = tableSizeFor(initialCapacity);
}
//构造方法4，通过一个已有的map映射到新的map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
Java

  第二个方法调用了第三个方法，一般来说前两个方法用的是比较多的，至于负载因子（loadFactor）一般使用默认的0.75就行。构造方法主要是进行一些参数的设置，下面说说初始化的这些参数。

初始容量，负载因子，阈值

  我们在一般情况下，都会使用无参构造方法创建 HashMap。但当我们对时间和空间复杂度有要求的时候，使用默认值有时可能达不到我们的要求，这个时候我们就需要手动调参。在 HashMap 构造方法中，可供我们调整的参数有两个，一个是初始容量 initialCapacity，另一个负载因子 loadFactor。通过这两个设定这两个参数，可以进一步影响阈值大小。但初始阈值 threshold 仅由 initialCapacity 经过移位操作计算得出。他们的作用分别如下：

名称用途
initialCapacityHashMap 初始容量
loadFactor负载因子
threshold当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容

先介绍几个常量值：

//The default initial capacity - MUST be a power of two.
//默认容量为16，容量必须为2的幂次方：16，32，64……
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/*The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. 
MUST be a power of two <= 1<<30.
*/
//最大容量为2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;

//The load factor used when none specified in constructor.
//默认负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//The next size value at which to resize (capacity * load factor).
// 阈值并没有初始值，因为阈值 = 容量 * 负载因子
int threshold;

//树化阈值，即桶元素达到8时并且桶数达到MIN_TREEIFY_CAPACITY（64）时开始树化，把链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

//红黑树拆分阈值，即扩容后如果数的节点小于6，则把红黑树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;

/*
当哈希表中的容量达到这个值时，表中的桶才能进行树形化，否则桶内元素太多时会优先扩容，而不是树形化
这是因为当容量较小时桶内元素数更容易超过树化阈值，此时应该优先选择扩容而不是树化，这样可以避免频繁树化。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
Java

  在上面的代码中使用了位运算：<<，位运算是直接操作二进制位，<<代表向左移动，这里只需要知道左移一位：a << 1等价于a * 2就行了（右移一位等价于除以2）。代码中并没有定义初始容量initialCapacity这个变量，因为initialCapacity只使用一次，并且可以被threshold暂时代替（下面会有讲到），因此并没有必要浪费空间存储该值。
  默认情况下HashMap容量为16，负载因子0.75，这里并没有默认阈值，原因是阈值可由容量乘上负载因子计算而来（注释中有说明），即threshold = capacity * loadFactor。但当你仔细看构造方法3时，会发现阈值并不是由上面公式计算而来，而是通过一个方法算出来的。我们来看看初始化 threshold 的方法长什么样的的，源码如下：

/**
    * Returns a power of two size for the given target capacity.
    */
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;
}
Java

  上面的代码不太好理解，使用了无符号右移>>>和或|运算。具体位运算如何使用请百度，本文不再赘述。该段代码的作用是找到大于或等于 cap 的最小2的幂。可以通过以下运算看出端倪：

int cap = (int) Math.pow(2, 29) + 1;//2的29次幂+1
System.out.println(Integer.toBinaryString(cap));//输出cap的二进制数
int n = cap - 1;
System.out.println(Integer.toBinaryString(n));
n |= n >>> 1;
System.out.println(Integer.toBinaryString(n));
n |= n >>> 2;
System.out.println(Integer.toBinaryString(n));
n |= n >>> 4;
System.out.println(Integer.toBinaryString(n));
n |= n >>> 8;
System.out.println(Integer.toBinaryString(n));
n |= n >>> 16;
System.out.println(Integer.toBinaryString(n));
n = n + 1;
System.out.println(Integer.toBinaryString(n));
Java

输出结果：

100000000000000000000000000001
100000000000000000000000000000
110000000000000000000000000000
111100000000000000000000000000
111111110000000000000000000000
111111111111111100000000000000
111111111111111111111111111111
1000000000000000000000000000000

这里放一张图解：
最小二次幂

  说完了初始阈值的计算过程，再来说说负载因子（loadFactor）。对于 HashMap 来说，负载因子是一个很重要的参数，该参数反应了 HashMap 桶数组的使用情况（假设键值对节点均匀分布在桶数组中）。通过调节负载因子，可使 HashMap 时间和空间复杂度上有不同的表现。当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。至于负载因子怎么调节，这个看使用场景了。一般情况下，我们用默认值就可以了。

查找

  首先要知道内部的Node这个类，链表、二叉树一般都是使用类似这种的类，没什么好说的。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;//节点的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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    //下面这些没什么好说的
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

//这个table就是底层的数组，每个节点可以可以通过其成员变量next形成链表
transient Node<K,V>[] table;
Java

查找操作就是利用HashMap的原理：

  1. 找到元素所在桶
  2. 如果桶内是红黑树则调用红黑树的查找方法
  3. 如果桶内是链表则直接遍历
//get()方法，通过key获取value
public V get(Object key) {
    //声明一个节点，调用内部方法获取该key的节点，并返回其value
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//上面的方法并没有调用key本身的hashCode()方法，而是使用了自己的静态方法：
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//int类型为32位，无符号右移16位代表取到了高16位的值
}
//这么做的目的是使hashcode的高位也参与运算，增加随机性

//主要步骤在这个方法里
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位键值对所在桶的位置，即如果这个键在表里，它会在哪个桶
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {//tab[(n - 1) & hash]这是个重点
        //总会检查桶的第一个节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;//代表第一个节点就是要找的
        //到这里说明不是第一个节点
        if ((e = first.next) != null) {//第一个节点之后还有节点的话
            //如果这个桶放的是红黑树了，调用红黑树的查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //到这里说明不是红黑树，而是链表，直接遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //到这里说明没找到
    return null;
}
Java

上面，定位桶所在的位置关键在这一步：

// index = (n - 1) & hash
first = tab[(n - 1) & hash]
Java

  这里，在n为2的幂次方的时候，(n - 1) & hash等价于hash % n但是效率更高。举个例子hash = 185，n = 16，计算过程如下：
(n - 1) & hash

  正好可以获取到hash对n的模。这里正好解释了为什么容量必须是2的幂次方。网上好多人说容量不是2的幂次方之后，是因为(n - 1) & hash这么运算所得的值会冲突，并且会导致有些桶不能放元素了。但笔者不这么认为，因为假如容量不是2的幂次方之后，肯定不能使用(n - 1) & hash这种运算方式了，只能使用模运算%，这样就会导致效率低好多。所以空间必须是2的幂次方之后才能(n - 1) & hash这么运算，最终得到效率上的提升。
  但是上面的hash并非key的hashCode方法，而是HashMap的静态方法：

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

  这样做有两个好处，首先看一下上面求余的计算图，图中的 hash 是由键的 hashCode 产生。计算余数时，由于 n 比较小，hash 只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的 hash 高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：

  在 Java 中，hashCode 方法产生的 hash 是 int 类型，32 位宽。前16位为高位，后16位为低位，所以要右移16位。
  上面所说的是重新计算 hash 的一个好处，除此之外，重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。这也就是为什么 HashMap 不直接使用键对象原始 hash 的原因了。

遍历

  和查找查找一样，遍历操作也是大家使用频率比较高的一个操作。对于 遍历 HashMap，我们一般都会用下面两种方式：

//增强for循环体遍历keySet
for(Object key : map.keySet()) {
    // do something
}

//遍历entrySet
for(HashMap.Entry entry : map.entrySet()) {
    // do something
}
Java

  增强型for循环的底层原理就是迭代器，因此上面的代码相当于：

Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
    Object key = ite.next();
    // do something
}
Java

  大家在遍历 HashMap 的过程中会发现，多次对 HashMap 进行遍历时，遍历结果顺序都是一致的。但这个顺序和插入的顺序一般都是不一致的。为什么呢，这里首先分析一下keySet的遍历：

//keySet方法，返回的是一个内部KeySet类
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

//内部的KeySet类
final class KeySet extends AbstractSet<K> {
    //大小
    public final int size()                 { return size; }
    //清空
    public final void clear()               { HashMap.this.clear(); }
    //注意这一步，返回的是下面的KeyIterator类的对象
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    //包含
    public final boolean contains(Object o) { return containsKey(o); }
    //删除
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    //多线程迭代
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    //集合可以调用forEach方法，参数为Consumer函数式接口
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K, V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}
//内部类KeyIterator，继承抽象内部类HashIterator
final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

//抽象内部类，下面有KeyIterator、ValueIterator、EntryIterator三个实现子类
abstract class HashIterator {
    //在当前已读到的元素的下一个元素
    Node<K,V> next;        // next entry to return
    //当前已读到的元素
    Node<K,V> current;     // current entry
    // 期望操作数，用于多线程情况下，如果多个线程同时对 HashMap 进行读写，那么这个期望操作数 expectedModCount 和 HashMap 的 modCount 就会不一致，这时候抛个异常出来，称为“快速失败”
    int expectedModCount;  // for fast-fail
    // 当前正在迭代的桶位置索引
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        //找到第一个不为空的桶的索引
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    //是否还有下一个节点
    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        // 这里就是快速失败实现的地方，可以看出，多线程情况下，执行到 if (modCount != expectedModCount) 这行代码时，有可能这时候  modCount 还是等于 expectedModCount，当过了这一行代码，modCount 有可能不等于 expectedModCoun，所以对于这个时候会有一个时差，或许会读到有问题的数据
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        //找到下一个不为空的桶
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
    // 和外部 remove(Object key) 差不多，但是不会对 table 的元素进行重排，所以这个方法适合一边迭代一边删除元素
    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        //快速失败
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        removeNode(p.hash, p.key, null, false, false);
        //操作完更新操作数
        expectedModCount = modCount;
    }
}
Java

  如上面的源码，遍历所有的键时，首先要获取键集合KeySet对象，然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类，核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂，在初始化时，HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。举个例子，假设我们遍历下图的结构：

  HashIterator 在初始化时，会先遍历桶数组，找到包含链表节点引用的桶，对应图中就是3号桶。随后由 nextNode 方法遍历该桶所指向的链表。遍历完3号桶后，nextNode 方法继续寻找下一个不为空的桶，对应图中的7号桶。之后流程和上面类似，直至遍历完最后一个桶。以上就是 HashIterator 的核心逻辑的流程，对应下图：

通过这段代码可以验证一下：

//创建一个HashMap并添加几个Integer，注意Integer重写了hashCode方法，Integer的HashCode等于其本身
HashMap<Integer, String> map = new HashMap<>(16);
map.put(7, "");
map.put(11, "");
map.put(43, "");
map.put(59, "");
map.put(19, "");
map.put(3, "");
map.put(35, "");

//创建一个list保存这些数以对比
List<Integer> nums = new ArrayList<>();
Collections.addAll(nums, 7, 11, 43, 59, 19, 3, 35);
//创建另外一个list保存这些数的hashcode对16取余
List<Integer> numsHash = new ArrayList<>();
for (Integer n : nums) {
    numsHash.add(n.hashCode() % 16);
}
System.out.println("Key:");
System.out.println(nums);
System.out.println("Key的哈希值对容量（16）取余:");
System.out.println(numsHash);
System.out.println("在Map中的遍历结果：");
System.out.println(map.keySet());
Java

输出结果：

Key:
[7, 11, 43, 59, 19, 3, 35]
Key的哈希值对容量（16）取余:
[7, 11, 11, 11, 3, 3, 3]
在Map中的遍历结果：
[19, 3, 35, 7, 11, 43, 59]

完全一致

插入

  插入的大致流程其实是比较简单的：首先肯定是先定位要插入的键值对属于哪个桶，定位到桶后，再判断桶是否为空。如果为空，则将键值对存入即可。如果不为空，则需将键值对接在链表最后一个位置，或者更新键值对。
但是真正的插入流程非常复杂，因为掺杂了桶的扩容以及链表的树化等等。下面上源码：

//put方法，把新值放入并返回旧值
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//内部进行实现的方法，需要注意的是boolean onlyIfAbsent, boolean evict这两个参数目前并没有什么用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //这里才是初始化桶，HashMap在创建时并没有直接初始化，而是延迟到放入元素时才进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//这里tab = resize()进行了扩容
    //如果键所在的桶是空的就直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //使用e保存键和插入的键相同的节点
        Node<K,V> e; K k;
        //如果第一个节点的键和要放入的键相同，把e指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果桶里是红黑树，则调用红黑树的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //遍历链表，并统计长度
            for (int binCount = 0; ; ++binCount) {
                //链表中不包含要插入的节点时，则将该节点接在链表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //链表长度是否达到树化阈值，达到则树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);//树化
                    break;
                }
                //条件为 true，表示当前链表包含要插入的键值对，终止遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//这一步是遍历的关键，p指针后移
            }
        }
        //判断要插入的键值对是否存在 HashMap 中，非空代表存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;//获取旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;//更新值
            afterNodeAccess(e);//空方法
            return oldValue;//返回旧值
        }
    }
    ++modCount;
    // 键值对数量超过阈值时，则进行扩容
    if (++size > threshold)
        resize();//扩容
    afterNodeInsertion(evict);//空方法
    return null;
}
Java

大致流程如下：

  1. 当桶数组 table 为空时，通过扩容的方式初始化 table
  2. 查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
  3. 如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
  4. 判断键值对数量是否大于阈值，大于的话则进行扩容操作

还是比较容易理解的。

扩容

  在 Java 中，数组的长度是固定的，这意味着数组只能存储固定量的数据。但在开发的过程中，很多时候我们无法知道该建多大的数组合适。建小了不够用，建大了用不完，造成浪费。如果我们能实现一种变长的数组，并按需分配空间就好了。好在，我们不用自己实现变长数组，Java 集合框架已经实现了变长的数据结构。比如 ArrayList 和 HashMap。对于这类基于数组的变长数据结构，扩容是一个非常重要的操作。下面就来聊聊 HashMap 的扩容机制。
  在详细分析之前，先来说一下扩容相关的背景知识：
  在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。
  HashMap 的扩容机制与其他变长集合的套路不太一样，HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。以上就是 HashMap 的扩容大致过程，接下来我们来看看具体的实现：

// 扩容方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不为空，表明已经初始化过了
    if (oldCap > 0) {
        // 当 table 容量超过容量最大值，则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } 
        // 按旧容量和阈值的2倍计算新容量和阈值的大小
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        /*
         * 初始化时，将 threshold 的值赋值给 newCap，
         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        /*
         * 调用无参构造方法时，桶数组容量为默认容量，
         * 阈值为默认容量与默认负载因子乘积
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 为 0 时，按阈值计算公式进行计算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 创建新的桶数组，桶数组的初始化也是在这里完成的
    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;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 重新映射时，需要对红黑树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表，并将链表节点按原顺序进行分组
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将分组后的链表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
Java

上面的源码总共做了3件事，分别是：

  1. 计算新桶数组的容量 newCap 和新阈值 newThr
  2. 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
  3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

  上面列的三点中，创建新的桶数组就一行代码，不用说了。接下来，来说说第一点和第三点，先说说 newCap 和 newThr 计算过程。该计算过程对应 resize 源码的第一和第二个条件分支，如下：

// 第一个条件分支
if ( oldCap > 0) {
    // 嵌套条件分支
    if (oldCap >= MAXIMUM_CAPACITY) {...}
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
} 
else if (oldThr > 0) {...}
else {...}

// 第二个条件分支
if (newThr == 0) {...}
Java

  通过这两个条件分支对不同情况进行判断，进而算出不同的容量值和阈值。它们所覆盖的情况如下：

条件覆盖情况备注
oldCap > 0桶数组 table 已经被初始化
oldThr > 0threshold > 0，且桶数组未被初始化调用 HashMap(int) 和 HashMap(int, float) 构造方法时会产生这种情况，此种情况下 newCap = oldThr，newThr 在第二个条件分支中算出
oldCap == 0 && oldThr == 0桶数组未被初始化，且 threshold 为 0调用 HashMap() 构造方法会产生这种情况。

  这里把oldThr > 0情况单独拿出来说一下。在这种情况下，会将 oldThr 赋值给 newCap，等价于newCap = threshold = tableSizeFor(initialCapacity)。我们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap。这也就解答了前面提的一个疑问：initialCapacity 参数没有被保存下来，那么它怎么参与桶数组的初始化过程的呢？
嵌套分支：

条件覆盖情况备注
oldCap >= 230桶数组容量大于或等于最大桶容量 230这种情况下不再扩容
newCap < 2^30 && oldCap > 16新桶数组容量小于最大值，且旧桶数组容量大于 16该种情况下新阈值 newThr = oldThr << 1，移位可能会导致溢出

  这里简单说明一下移位导致的溢出情况，当 loadFactor小数位为 0，整数位可被2整除且大于等于8时，在某次计算中就可能会导致 newThr 溢出归零。见下图：

位移溢出

分支二：

条件覆盖情况备注
newThr == 0第一个条件分支未计算 newThr 或嵌套分支在计算过程中导致 newThr 溢出归零

  说完 newCap 和 newThr 的计算过程，接下来再来分析一下键值对节点重新映射的过程。

  在 JDK 1.8 中，重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。关于红黑树拆分的逻辑将会放在下一小节说明，先来看看链表是怎样进行分组映射的。

  我们都知道往底层数据结构中插入节点时，一般都是先通过模运算计算桶位置，接着把节点放入桶中即可。事实上，我们可以把重新映射看做插入操作。在 JDK 1.7 中，也确实是这样做的。但在 JDK 1.8 中，则对这个过程进行了一定的优化，逻辑上要稍微复杂一些。在详细分析前，我们先来回顾一下 hash 求余的过程：
hash

  上图中，桶数组大小 n = 16，hash1 与 hash2 不相等。但因为只有后4位参与求余，所以结果相等。当桶数组扩容后，n 由16变成了32，对上面的 hash 值重新进行映射：

  扩容后，参与模运算的位数由4位变为了5位。由于两个 hash 第5位的值是不一样，所以两个 hash 算出的结果也不一样。上面的计算过程并不难理解，继续往下分析。

  假设我们上图的桶数组进行扩容，扩容后容量 n = 16，重新映射过程如下:

  依次遍历链表，并计算节点 hash & oldCap 的值。如下图所示

  如果值为0，将 loHead 和 loTail 指向这个节点。如果后面还有节点 hash & oldCap 为0的话，则将节点链入 loHead 指向的链表中，并将 loTail 指向该节点。如果值为非0的话，则让 hiHead 和 hiTail 指向该节点。完成遍历后，可能会得到两条链表，此时就完成了链表分组：

  最后再将这两条链接存放到相应的桶中，完成扩容。如下图：

  从上图可以发现，重新映射后，两条链表中的节点顺序并未发生变化，还是保持了扩容前的顺序。以上就是 JDK 1.8 中 HashMap 扩容的代码讲解。另外再补充一下，JDK 1.8 版本下 HashMap 扩容效率要高于之前版本。如果大家看过 JDK 1.7 的源码会发现，JDK 1.7 为了防止因 hash 碰撞引发的拒绝服务攻击，在计算 hash 过程中引入随机种子。以增强 hash 的随机性，使得键值对均匀分布在桶数组中。在扩容过程中，相关方法会根据容量判断是否需要生成新的随机种子，并重新计算所有节点的 hash。而在 JDK 1.8 中，则通过引入红黑树替代了该种方式。从而避免了多次计算 hash 的操作，提高了扩容效率。

删除

  HashMap 的删除操作并不复杂，仅需三个步骤即可完成。第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。相关源码如下：

//删除方法
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
//主要实现
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {  
            // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 2. 遍历链表，找到待删除节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 3. 删除节点，并修复链表或红黑树
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
Java

  上面的代码并不复杂，不难理解，这里就不多说了。

table变量

  如果大家细心阅读 HashMap 的源码，会发现桶数组 table 被申明为 transient。transient 表示易变的意思，在 Java 中，被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中，考虑一个问题：桶数组 table 是 HashMap 底层重要的数据结构，不序列化的话，别人还怎么还原呢？

  这里简单说明一下吧，HashMap 并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap 中存储的内容是什么？不用说，大家也知道是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建 HashMap。有的朋友可能会想，序列化 table 不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化 talbe 存在着两个问题：

  1. table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
  2. 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。

  以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个 table 继续操作，就会出现问题。
  综上所述，大家应该能明白 HashMap 不序列化 table 的原因了

直接阅读源码还是有些难度的，结合这篇博客勉强把源码读完了，感觉源代码写的好厉害(*￣3￣)╭

参考HashMap源码分析

标签: Java, 源码

添加新评论