基于JDK1.8的HashMap源码解析一(变量和构造器)

本篇博客主要讲解了HashMap的变量和构造器

这是本人第一篇关于源码解析的技术博客，由于个人技术的局限性可能也会出现一些错误。所以请大家看到能够帮忙指出，感激不尽。

HashMap变量详解

HashMap主要有以下几个变量：

// 默认容器大小，1无符号右移4位，即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 容器最大值，超过这个值就将threshold设置为Integer.MAX_VALUE
static final int MAXIMUM_CAPACITY = 1 << 30;
// HashMap的默认负载因子，关系到HashMap扩容策略
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// HashMap的负载因子，可由构造器传入
final float loadFactor;
// HashMap扩容阈值，大小为(当前容器大小 * 负载因子)
int threshold;

// 链表转换成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 树化时容器的最小值
static final int MIN_TREEIFY_CAPACITY = 64;
// HashMap存放K-V的数组
transient Node<K,V>[] table;
// HashMap返回所有K-V的Set集合
transient Set<Map.Entry<K,V>> entrySet;
// HashMap的存储元素的大小
transient int size;
// HashMap内部修改次数，和迭代器快速失败有关，和源码一起讲
transient int modCount;

以上有些需要补充说明一下:

默认负载因子”DEFAULT_LOAD_FACTOR”为什么是0.75。
这个可以参考一个小姐姐的简书，HashMap的loadFactor为什么是0.75？笔者还是从评论区那里看到知识点才开始阅读Integer源码的。
为什么”MAXIMUM_CAPACITY = 1 << 30”。
我们知道，int在java占4字节32位，为什么不是”1 << 31”，那是因为在Java中，int的首位代表的是正负。如果右移31位那首位变成1，就是负数的最大值了。而且为了扩容时计算方便，HashMap采用的是与运算计算余数，所以规定扩容为2的幂次方，这个后续会讲。所以我们可以知道”1 << 30”已经是int类型中2的幂次方中最大的正整数。
“MIN_TREEIFY_CAPACITY = 64”是什么意思。
MIN_TREEIFY_CAPACITY代表树化时容器的最小值，也就是不管HashMap里的元素个数有没有达到threshold的值，如果链表长度超过8个，在进行树化的时候就会判断这个值，低于64触发resize()方法。举个例子，如果很不幸你前8个都在entry数组的第一个bucket中(HashMap里面的数组的下标位置称为桶，存放Node节点)，这个时候扩容阈值如果是默认的则为:(16*0.75=12)>8，远远没有达到扩容的要求，但是HashMap为了减少树化和解树化的开销，会进行resize操作。这个时候扩容成32了。
链表转红黑树为什么是8，红黑树转链表为什么是6。
前者可以在HashMap源码开头的”Implementation notes”中找到，主要是如果Key使用的是一个好的hashCode算法，容器中超过8的概率只0.00000006，低于一千万分之一。但是你不能阻止用户使用差的hash算法，所以出于性能考虑转化值为8。至于为什么红黑树转换链表是6，这个目前笔者还不知道，不过网上有个很流行的说法是:
红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

HashMap的构造器

HashMap的构造器涉及的方法如下:

public HashMap(int initialCapacity, float loadFactor) {
    // 判断容量是否为负数，是的话抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    // 判断容量是否大于容量最大值，是的话设置容量为最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 判断负载因子是否为非0~1之间的小数，不是的话抛出异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    // 设置负载因子
    this.loadFactor = loadFactor;
    // 设置扩容阈值
    this.threshold = tableSizeFor(initialCapacity);
}

// 计算HashMap容量值，不是2的幂次方通过此方法找到比其大且最邻近的幂值
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;
}
    
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 获取传入Map的容量
    int s = m.size();
    if (s > 0) {
        // 判断内部容量是否为空
        if (table == null) { // pre-size
            // 容量为空计算当前负载因子下该容器应当设置的数组大小。
            // 大于MAXIMUM_CAPACITY设置为MAXIMUM_CAPACITY，否则扩容阈值等于当前容量最近的2次幂。
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果传入的值大于扩容阈值，进行resize()。为什么要进行这步操作而不是直接put呢？
        // 传入Map大于threshold的范围时一定会触发resize()，如果不事先扩容等put过程扩容，需要移动的元素更多了，所以这一步可以节省性能开销。
        else if (s > threshold)
            resize();
        // 将传入的Map一个一个塞进我们当前的HashMap
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

上述代码基本都有注释，我们也看到了，HashMap并没有在构造器中给table进行初始化，其实是因为HashMap把初始化延时到了put操作之中。要说明的重头戏是计算容量的算法，这个的确相当的厉害，本人其实也讲不太清，大家可以看一下Java8 HashMap之tableSizeFor这篇博客，我觉得讲解的很清晰了。

但是这个构造器有个BUG，那就是”this.threshold = tableSizeFor(initialCapacity)”实际上应该为”this.threshold = tableSizeFor(initialCapacity) * loadFactor”，这个在ORACLE官方社区上Doug Lea大佬亲自承认的bug，并且在JDK1.9修复了。当然，这并不影响大佬在我心中的高大形象。还有一点就是putMapEntries()方法中”threshold = tableSizeFor(t)”让我存疑，不应该为”threshold = tableSizeFor(t) * loadFactor”，这个没有在社区上看到大佬说是bug，但我感觉是和上一个犯了同一个错吧。

经过我多次的debug和源码查看，此处并不是一个bug。当初我在社区看到的bug是在构造器中有参传入(12)和有参传入(12,0.75)他们的初始容量不一致。具体数值我不太清楚了，但是doug lea大佬说这的确是一个bug，我下意识的以为是我认为的bug了，不过在深入了解之后发现有参构造的threshold是为了在put操作给table初始化容量用的，下一章会讲到。我会努力再找到这个问题，看看具体bug到底是什么。

还有一个有意思的地方是”Float.isNaN(loadFactor)”这个方法。给大家看看方法和示例：

public static boolean isNaN(float v) {
    return (v != v);
}

public static void main(String[] args) {
    System.out.println(Float.isNaN(0.0f / 0.0f));
}

大家可以看看这个方法，想想输出会是什么呢？是报错还是输出true或者false呢？因为这个不在本文范畴内，所以给大家一个参考链接吧。大家先思考一下再带着疑问去有趣的NaN类型寻找答案吧。

本来打算今晚手撕红黑树，结果发现撕的脑壳疼，没有画图我自己都理不清。然而我还是个手残党不会画图，红黑树暂时不讲吧。今天的第一章暂时讲到这，明天我理一理应该按什么顺序讲好一点吧。

君子不立危墙之下