HashMap 源码解读

Hash 算法

简单介绍一下 Hash 算法以及解决 Hash 冲突的方案。

优秀 Hash 算法的特点：

从 Hash 值不可以反向推导出原始的数据
输入数据的微小变化会得到完全不同的 Hash 值，相同的数据会得到相同的值
哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
Hash 算法的冲突概率要小

Hash 冲突解决方案

链地址法

链表地址法是使用一个链表数组，来存储相应数据，当 Hash 遇到冲突的时候依次添加到链表的后面进行处理；这也是 HashMap 在 1.8 之后做的优化之一。

Hash-链地址法

开放地址法

线性探测法，就是比较常用的一种开放地址哈希表的一种实现方式。

线性探测法的核心思想是当冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。简单来说就是：一旦发生冲突，就去寻找下一个空的散列表地址，只要散列表足够大，空的散列地址总能找到。

HashMap 数据结构

HashMap-数据结构

数组：通过 Hash 后得到的值可以直接找到对应的数组下标，时间复杂度为 O(1)，就算是遍历素组，复杂度也是 O(n)
链表：1.7 版本采用首插法，在 resize 时，会重新计算每个元素的 Hash 值，从新放到不同的位置，首插可能会出现链表变环出现死循环；1.8 版本后采用尾插法，避免了该问题的出现。
红黑树：1.8 版本后添加，使查询性能由链表的 O(n)，提升到 O(logn)，效率更高

关于 1.7 到 1.8 的升级，后面说明。

HashMap Java 源码

先确定几个预定义常量

默认初始容量

/**
 * 默认初始化容量，必须是 2 的整数幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认 16

扩容阈值

/**
 * 如果当前容量到达指定阈值 (capacity * loadFactor)
 */
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;

HashMap 中的变量

// 该表在首次使用时初始化，并根据需要调整大小。 分配时，长度始终是2的幂
// table 是一个以 Node 为单位的数组
// 数组中的每个元素为桶，桶中的元素称作 bin，在 putVal() 方法中有一个 binCount 就是用来计算 bin 的数量的
transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

// map 中的元素个数
transient int size;

// 这个变量设计涉及到 Java 集合中的 “快速失败” 机制，会另起博客描述
transient int modCount;

// 扩容阈值 = capacity * loadFactor
int threshold;

// 装载因子，用来衡量 HashMap 满的程度，影响扩容时机，默认值为0.75
// 计算实时装载因子的方法：size / capacity
final float loadFactor;

存储数据的最小单位 Node

Node 是整个 HashMap 的最小单位，实际的值都存储在这个 Node 中；

static class Node<K,V> implements Map.Entry<K,V> {
    // key 的 Hash 值计算结果
    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;
    }

    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;
    }
}

构造方法

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    // 不用多说，容量小于 0 只能抛异常
    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;
    // tableSizeFor 用于初始化容量，这个方法很重要
    this.threshold = tableSizeFor(initialCapacity);
}

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;
}

这里的算法主要目的是计算出离给定数值向上最近的 2 的整数幂的值，简单点来说就是：给 1 就返回 2；给 5 返回 8；给 15 返回 16；给 16 也返回16。

可能会有疑问，给了16 按道理来说不应该是返回 32 吗？这就是为什么一开始会有一个 int n = cap - 1 的操作。

从使用者的视角来看，我需要创建的是一个容量为 16 的 HashMap，那就应该只创建一个容量为 16 的 HashMap，而不是一个 32 的 HashMap，虽然在使用上感受不到，但是在 JVM 中，每块内存都是寸土寸金，能不浪费就不浪费，减 1 操作就是为了得到一个与设置值更加接近的 2 的整数幂的值作为 HashMap 实际的容量，但如果传入的值为 -1，那初始容量就会为 1，会在后面的 resize 中立即扩容；

putVal() 方法

在除了构造方法歪，HashMap 仍然还有几个比较重要的方法，先来介绍一个 putVal() 方法，然后在引入其他的方法。先上源码：

// 实际调用的方法
public V put(K key, V value) {
    // 这里说明一下，hash 方法中将 null 值进行了特殊处理，null 的 hash 值为 0
    return putVal(hash(key), key, value, false, true);
}

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

/**
 * 为了方便阅读源码，我把源码格式调整了一下，里面的变量名也进行了修改，提高一定的可读性
 * (初步认为之所以源码的格式和变量名不符合开发规范，主要是为了减少一定的空间占用，以免源码包过大)
 */
final V putVal(int hash, 
               K key, 
               V value, 
               boolean onlyIfAbsent, 
               boolean evict) {
    
    Node<K,V>[] tab; 
    Node<K,V> node; 
    int newLen, index;
    
    // 从刚才的构造方法中可以看出，调用构造方法是不会真正实例化的
    // 真正实例化是第一次调用 putVal 的时候，进行到这一步的时候会实例化，给 Node[] 实际分配内存
    if ((tab = table) == null || (newLen = tab.length) == 0) {
        newLen = (tab = resize()).length;
    }
    
    // 根据 key 的 hash 值找到对应的位置插入第一 node
    if ((node = tab[index = (newLen - 1) & hash]) == null) {
        tab[index] = newNode(hash, key, value, null);
    }
    // 如果当前位置有一个 node 了，那就在这个 node 后面接着插入（链表尾插）
    else {
        Node<K,V> nodeBuffer; 
        K k;
        // 这个 if 是用于判断当前 key 是否已经存在，如果存在就不进行下面的添加操作，直接跳到下面进行更新操作
        if (node.hash == hash && ((k = node.key) == key || (key != null && key.equals(k)))) {
            nodeBuffer = node;
        } else if (node instanceof TreeNode) {
            // 若判断为数节点，则根据红黑树的原理进行添加操作
            nodeBuffer = ((TreeNode<K,V>)node).putTreeVal(this, tab, hash, key, value);
        } else {
            // 从这里开始计算 bin 的数量，也就是某个链表或者红黑树节点的数量
            for (int binCount = 0; ; ++binCount) {
                // 先实现链表尾插
                if ((nodeBuffer = node.next) == null) {
                    node.next = newNode(hash, key, value, null);
                    // 树化第一步，判断链表长度是否为 >= 8
                    if (binCount >= TREEIFY_THRESHOLD - 1) {
                        treeifyBin(tab, hash);
                    }
                    break;
                }
                // 和上面一样，如果找到一个已经存在的 key，直接执行更新操作
                if (nodeBuffer.hash == hash && ((k = nodeBuffer.key) == key || (key != null && key.equals(k)))) {
                    break;
                }
                node = nodeBuffer;
            }
        }
        
        // 更新已有的值
        if (nodeBuffer != null) {
            V oldValue = nodeBuffer.value;
            if (!onlyIfAbsent || oldValue == null) {
                nodeBuffer.value = value;
            }
            afterNodeAccess(nodeBuffer);
            return oldValue;
        }
    }
    // 用于实现 “快速失败” 机制
    ++modCount;
    // 超过阈值扩容
    if (++size > threshold) {
        resize();
    }
    // 这是个空方法，可以由继承的类自行实现，比如 LinkedHashMap(key 有序)
    afterNodeInsertion(evict);
    return null;
}

resize() 方法

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) {
        // 如果 capacity 已经扩容到最大 (2^31-1)，则不进行扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
            // capacity > 16  且  capacity * 2 < MAXIMUM_CAPACITY, 则进行扩容 2 倍
            newThr = oldThr << 1;
        }
    } else if (oldThr > 0) {
        // 如果 capacity < 0  且  threshold > 0, 则 capacity = threshold
        newCap = oldThr;
    } else {
        // 如果 capacity < 0  且  threshold < 0, 初始化 table (都使用默认值)
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 计算新的元素数量阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 将原来 table 中的数据迁移到新的 table 中
    @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;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) {
                    // 重新计算 hash 值，放到新的桶中
                    newTab[e.hash & (newCap - 1)] = e;
                } else if (e instanceof TreeNode) {
                    // 如果是红黑树，使用红黑树复制方式
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                } else {
                    /**
                     * 如果是线性链表, 使用链表复制方式
                     * 这里会将原来的链表拆分为两个链表，分别放在 lo 和 hi 两个不同的桶中
                     * 拆分完成后，hi 在新的数组中的位置 = lo 的位置 + oldCap
                     * 注：lo 表示 高位为 0，hi 表示高位为 1，关键计算方法：(e.hash & oldCap) == 0，下文有解释
                     */ 
                    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;
}

链表拆分算法

主要算法就是上面源码中出现的：(e.hash & oldCap) == 0，大白话就不说了，直接上图：

（PS：还是多一句嘴，2 的整数幂都是只有一个 1，比如 8 => 01000，图中的最上一行是 hash 结果，01000 作为 oldCap，最下一行是运算结果)

HashMap-链表拆分算法

由上图可知，至于是分到 lo 链表还是 hi 链表，就看最高位是 0 还是 1。

treeifyBin() 方法

进入这个方法的前提是在该桶中的链表长度 >= 8，但不代表进入就一定会树化，源码如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        // 这里说明了，就算你链表长度 >= 8，但是桶的长度没到 64，那就不树化，只扩容
        resize();
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 到了这里才会开始树化
        // 这里也说明了树化的可能性是非常小的
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null) {
                hd = p;
            } else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null) {
            hd.treeify(tab);
        }
    }
}