HashMap

因为为了翻转课堂专门看了 HashMap 的源码，为了担心以后忘记，写一篇笔记记录下来，如果下面没有特指都是指 JDK 1.8 的源码，JDK 1.7 与 1.8 差别比较大

介绍

HashMap 的底层是数组 + 链表 + 红黑树，用一张图就能表示的比较清楚
HashMap 的结构图

这张图有一个问题，不止要链表长度达到 8，还要数组长度达到 64

常量

// 版本 id，感觉一般没用
private static final long serialVersionUID = 362498820763181265L;

//  默认初始化容量，为 16
// 之所以用 1 << 4 应该是为了表示容量必须是 2 的幂次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量为 2^30
// 最小为 2
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;

// 最小树化容量
// 这是树化的第二个条件
// 至少要链表长度达到 8，且桶(容量)大小至少达到 64 才会树化
static final int MIN_TREEIFY_CAPACITY = 64;

内部类

// JDK1.8 中的结点叫 Node，JDK1.7 中的结点叫 Entry
static class Node<K,V> implements Map.Entry<K,V> {
    // hash: key 算出来的 hash 值
    // key: key 
    // value: key 对应的 value
    // next: 链表的下一个结点
    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;
    }
}

重要函数

Hash 函数是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。因此这边是通过 key，算出一个 hash 值，然后将 key 映射到数组的索引上.

// Node 的中的属性 hash，是通过下面的算法算出来的
// 首先是获得 key 的 hashCode 值(即 h)，
// 再将 h 与 h 无符号右移 16位进行异或
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key 的 hashCode 函数是怎么样的？

// 返回值是 32 位的 int
public int hashCode() {
    int h = hash;
    if(h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++){
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

这个代码实际上是这样的公式
$s[0] * 31^{n-1}+s[1] * 31^{n-2}+\cdots + s[n-1]$
其中 $s$ 表示字符串.

那么这边有个引申问题，这个乘数 31 是哪里来的呢？下面是选不同的乘数时的hash冲突，因为这个图是直接用别人博客的，所以我不知道这张图的hash冲突是怎么算的，只知道是用了十万个不重复的单词
我们会发现，乘数为31，33，39，41，199的hash冲突已经很低很低了，下面是10万个单词算出 hash 值，然后模 64 得到的 hash 冲突结果 (hash 冲突指不同的内容，但是经过hash 函数处理后得到相同的hash值成为 hash 冲突) 乘数为 2
乘数为 31
乘数为 199

我们会发现 31 的散列效果很好，199也不错，但是为什么最后选了 31 呢？
除了散列效果很好以外，在 JVM 中还会把 31*i 优化成 i«5-i，博客中还写了199会导致数据丢失(但是不知道为什么orz)

OK，我们这边已经解决了 hashCode 怎么来的了

为什么要将 h 无符号右移 16 位再进行异或呢？

首先我们要知道，Node 在数组中的位置是通过 hash & (length -1) 算出来的，这边实际上是做了一个扰动，无符号右移 16 位，然后进行异或。
下面是没有扰动过的效果
我们会发现散列效果其实不怎么好，而经过扰动的散列效果如下
欸！这个散列效果就一级棒，这是为什么？
其实是如果只用 key.hashCode() & (length - 1) 就只会选取 32 位的最后几位，而进行扰动之后，就会让前 32 位可以参与进来. 比如这边模的是 127，如果不进行扰动，只会有最后 8 位对索引值有影响。而扰动之后第17位到第24位也会参与进来

为什么要用异或，而不用“与”或者“或”呢？

&	0	1
0	0	0
1	0	0

$\mid$	0	1
0	0	1
1	1	1

^	0	1
0	0	1
1	1	0

我们看到，如果是“异或”，那么只要改变一个值就会改变值，而“与”和“或”都没有这样的效果，感觉可以理解成“异或”映射到0和1的概率相同。

我们前面说了获得Node在数组中的位置是通过 hash 值模数组长度得到的，那么应该是用 hash % length，那为什么代码中是 hash & (length - 1) 呢？

首先给出结论，因为数值上二者会有相同的结果，其次“与”运算效率远远高于取模。
我们知道 length 一定是 $2^n$(这是 HashMap 设计时就想好的)，因此 length 转化为二进制一定是 000…00100…00 这样的形式，32 位中只有一个1，length - 1 转化为二进制就是 000…000111(假设 length=8 的话)，这样的话 hash & (length-1) 范围就一定是 0到length - 1，试一试就知道！

其次是构造函数，HashMap 中有四种构造函数

// 1. 无参构造
public HashMap()

// 2. 设定初始容量
public HashMap(int initialCapacity)

// 3. 给定初始容量和负载因子
public HashMap(int initialCapacity, float loadFactor)

// 4. 通过 Map 初始化 HashMap
public HashMap(Map<? extends K, ? extends V> m)

无参构造

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

无参构造非常简单，只是把负载因子设置为默认的了，没做别的事情

设置初始容量

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;
    // 如果负载因子小于等于 0 或者
    // Float.isNaN(loadFactor) 是对的(这边比较难，还不是很懂)
    // 那么就报错
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    // 如果判断都没问题的话就直接初始化值了
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

我们之前说过，容量一定要是 2 的幂次，那我要是给的初始容量是12呢？那就不是 2 的幂次了，我们会发现这边有一个 tableSizeFor 函数，其实这个函数的作用就是把返回不小于给定数字的2的幂次。
比如：给他6，不是2的幂次，那就会返回大于6的最小2的幂次8，如果给他8就会返回8，那么这个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 >= MAXMUM_CAPACITY) ? MAXMUN_CAPACITY : n+1;
}

先给一张图，这个是输入 17 的情况
这个图最后+1才是32，我们会发现这样可以达到我们想要的效果，但是是为什么呢？
首先我们知道，只要这个整数大于0，那么一定可以找到二进制中从左到右的第一个1，经过代码的或运算，我们一定可以将这个1 后面所有位都变成1，最后加上1就变成了2的幂次，那么最开始为什么要减1呢？可不可以不减1呢？
这是不可以的，减1就是为了输入的初始值就恰好是2的幂次的情况，如果输入8，不减1的话最后输出的会是16.

区别

JDK1.7 中，用的是头插法，结构是数组+链表
JDK1.8 中，用的是尾插法，结构是数组+链表+红黑树
HashMap 是线程不安全的
JDK1.7 中可能会在扩容的时候产生循环链表，导致死循环，并且也有可能数据丢失
JDK1.8 中可能会在扩容的时候产生数据覆盖
JDK1.7 中 table 是 Entry 数组
JDK1.8 中 table 是 Node 数组

扩容过程

1.8 中是懒加载，构造函数的时候并不会创建 table 数组，而是在第一次 put 的时候才创建，如果是链表达到8，且数组长度不到 64 的话，会进行扩容，每次扩容是之前的两倍，其次，如果数组元素达到 “数组容量*负载因子” 的话也会进行扩容，同样是扩容到原来的两倍.

在扩容的时候会进行rehash，首先 Node 的新位置索引index一定和原来一样或者是原来的索引加上原来的长度。这是为什么呢？
我们来回忆一下算 index 的方法，hash & (length - 1)，假设length = 8，那么位置就是hash值得后三位，那么当扩容之后，位置还是 hash & (newLength - 1)，这时候 newLength = 16，那么“与”运算的结果就是hash值得后四位，那么这个时候新多出来的一位只有可能是0或者1(毕竟是2进制)，那么假设是0，新的索引就和原来一样，如果是1，那么新的索引就是 oldLength + 老的索引，因此这边判断索引的位置实际上就是判断从右到左第4位是 0 还是 1，代码中非常优秀，直接将 hash & oldLength，因为oldLength 只有从右到左第4位是1，其他都是0，如果“与”运算的结果为0，说明hash值从右到左的第四位为0，否则为 1，这样就可以判断 Node 的新位置在哪里了

1.7 线程安全

由于扩容的时候需要创建一个新的数组，要把老数组中的元素复制到新数组中，这个过程可能会出现问题，有这样一个函数

void transfer(Entry[] newTable, boolean rehash) {  
    int newCapacity = newTable.length;  
    for (Entry<K,V> e : table) {  

        while(null != e) {  
            Entry<K,V> next = e.next;           
            if (rehash) {  
                e.hash = null == e.key ? 0 : hash(e.key);  
            }  
            int i = indexFor(e.hash, newCapacity);   
            e.next = newTable[i];  
            newTable[i] = e;  
            e = next;  
        } 
    }  
}

原来是这样的扩容后应该是现在有A，B两个线程，假设 A 线程刚执行完 e.next = newTable[i]; 时间片耗尽，线程挂起
这时候的状态是

next = 7
7.next = 5
5.next =null
e = 3
e.next = null

这时候转到B线程也在扩容，并且成功扩容完成
状态为：

next = 7
e = 3
5.next = null
7.next = 3
3.next = null

线程 B 挂起，继续进行线程 A
执行 newTable[i] = e;

e = next => 7 
next = e.next => 7.next = 3 
e.next = newTable[i];
即 7.next= 3
e = next = 3

再执行一次

next = e.next => 3.next = null
e.next = newTable[i];
即 3.next= 7

我们会发现3的next是7，7的next是3，形成了循环链表

循环链表会导致死循环

第二种
除了可能导致死循环，还有可能导致数据丢失
一开始
现在有A，B两个线程，假设 A 线程刚执行完 e.next = newTable[i]; 时间片耗尽，线程挂起

状态：

e = 7
7.next = null
next = 5
5.next = 3
3.next = null

转换到线程 B，扩容成功此时状态：

回到A线程，
newtable[3]=7,next = 5, 
e=5, next = 5.next =null
e.next  =newTable[1], e.next = 5
e=next =null

继续线程A：这时候5自己指向自己，并且丢失了数据3

1.8 线程安全

final V putVal(int hash, K key, V value, boolean onlyIfAvsent,
    boolean evict) {
    ......
    if ((p=tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    ......
}

假设线程A 判断完 tab[i] 为 null 之后时间片用完，开始线程 B，线程 B 在tab[i] 处判断为 null ，于是直接将值放在tab[i] 上，时间片结束后继续线程A，由于上次已经判断完了，于是直接把值赋给 tab[i]，这样就会导致线程B的数据被覆盖

参考

这篇笔记中大部分图都是从网络上别人的博客中搬运来的，但是找不到具体来源了，所以没有附上链接