HashMap源码解读

前言

HashMap是Java中最为常见的一个数据结构，它是一种基于哈希表(散列表)，实现Map接口的集合，在JDK1.7中其主要是由数组+链表构成，而到了JDK1.8的时候就由数组+链表+红黑树构成。其实HashMap中还是有许多地方值得我们注意的地方。比如说HashMap在JDK1.7和JDK1.8中有较大的不同，那么都有哪些不同？HashMap在什么条件下会进行扩容，如何扩容？HashMap的get/put过程是如何实现的？HashMap如何解决并发问题？HashMap的key如何设置？下面将对HashMap进行一次比较系统的整理与学习。

一、我对HashMap的疑问

HashMap的使用是很简单的，但是在没有看源码之前，我对HashMap还是有着一些疑问。

1.HashMap的实现原理？

• HashMap的原理是啥？
• 为什么HashMap会使用数组+链表的结构？
• hash冲突其他解决的方法？
• 既然HashMap是数组+链表，其中数组其实Entity数组，那么能用LinkedList或者ArrayList代替它吗？
• 如果能用LinkedList或者ArrayList代替的话，为什么不选择LinkedList/ArrayList而选择数组呢？

2.HashMap的扩容？

• HashMap在什么条件下扩容？
• 为什么扩容是2的n次幂？
• 为什么要先高十六位异或低十六位再取模运算？

3.HashMap的Get/Put过程是怎么样的？

• hashmap中get过程是怎么样的？
• hashmap中put过程是怎么样的？
• hash算法有哪些？
• String中hashcode的实现？

4.HashMap中在JDK1.8中添加红黑树

• 为什么在解决哈希冲突的时候，不直接用红黑树而是选择先用链表，再用红黑树？
• 红黑树用二叉查找树可以吗？
• 为什么链表转化为红黑树的阈值是8？
• 当链表转化为红黑树之后还会退化成链表吗？如果会退化，什么时候退化成链表？

5.HashMap如何解决并发的问题

• HashMap在并发编程环境下有什么问题？
• 在jdk1.8中还有这些问题吗？
• 并发问题一般应该如何解决？

6.HashMap的Key如何选择

• Key值可以为空吗？
• 一般用什么当做HashMap的Key？
• 可变类当HashMap的Key有什么问题吗？
• 如果要自己实现一个自定义的class作为HashMap的key应该如何实现？

那么就带着以上问题去阅读源码。

二、HashMap源码分析

注意：以下源码分析针对的是JDK1.8的HashMap源码，中间会有和JDK1.7的对比。

1.初始化变量和构造函数

//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//返回一个大于cap且最接近cap的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, 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);
}

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

• initialCapacity初始容量。
• loadFactor负载因子：装载因子，用来衡量HashMap满的程度，加载因子越大,填满的元素越多,空间利用率越高。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为size/capacity。
• threshold阈值：满足公式threshold=loadFactor*capacity。当HashMap的size大于threshold时会执行扩容（resize）操作。

HashMap的构造函数主要是初始化初始容量和负载因子，当调用的无参构造函数的时候，设置负载因子为默认的负载因子，也就是0.75，此时初始容量为默认的16。当调用的有参构造函数时候，可以自己设定负载因子，若不设定则默认为默认负载因子0.75，并设定初始容量，用初始容量计算出阈值，计算方法是tableSizeFor(initialCapacity);也就是返回一个大于initialCapacity且最接近initialCapacity的一个2的正数幂的数字作为初始阀值。这边不难发现，在构造函数中指定了initialCapacity，它也是只是用来计算阈值的。

举个例子

// 设置初始容量为4，最后map的容量是8。因为8是2的3次幂，且是最接近4的一个2的次幂值。
Map<Integer, Integer> map = new HashMap<>(4);

//其他例子
initialCapacity为10，最后的hashmap容量为16

如果我要存储100个数量在hashmap中，初始化容量initialCapacity应该设置为 (100/0.75)+1=134，此时hashmap中的实际容量有2的8次幂=256个。

总结：四个构造函数中，除了最后一个，其余三个构造函数最多只涉及到loadFactor和threshold，而不涉及到table的变量。这说明，在HashMap中，table的初始化或者使用不是在构造函数中进行的，而是在实际用到的时候。事实上，是在HashMap扩容的时候实现的，即resize函数，后文会提到。

2.底层数据存储结构

HashMap的散列表是一个table，它是采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，如下图所示。 只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树。

Node类：在JDK1.8之前，是静态内部类Entry，而到了JDK1.8，就成了静态内部类Node，这边不管是1.7的静态内部类Entity还是1.8的静态内部类Node，它们都实现了Map的内部接口Map.Entry<K,V>。

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

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

红黑树中的节点TreeNode类：

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

    /**
    * Returns root of tree containing this node.
    */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    /**关于红黑树的操作在后面进行说明*/
}

这边可以清楚地看到，TreeNode<K,V>类是继承于LinkedHashMap.Entry<K,V>类的，而LinkedHashMap.Entry<K,V>类是继承于HashMap.Node<K,V>类的，最终还是回到了上面的静态内部类Node，上面也提到了不管是1.8中的Node类还是1.7中的Entry类，都是实现了Map的内部接口Map.Entry<K,V>。做到了红黑树和链表中元素的一致性。

看到这边，其实就可以解决我的第一个疑问中的问题：

• HashMap的原理是啥？

在JDK1.8之前，HashMap实际上是数组+链表的实现方式，在JDK1.8之后又加入了红黑树，实现方式成为了数组+链表+红黑树。在JDK1.8之前，HashMap中的基本数据存储结构是静态内部类Entry，JDK1.8后是静态内部类Node，但是它们是差不多的，都是用来存储key-value对。以JDK1.8为例，Node实际上是一种单向的链表结构，具有next属性，可以指向下一个Node实体。

• 为什么HashMap会使用数组+链表的结构？

数组是用来确定桶的位置，比如说要放入一个key-value对，首先key的hash值对数组长度取模，放在数组的对应下标位置，链表是用来解决哈希冲突的一种方式，当出现hash值相同的时候，就在数组相应的位置形成链表。

• hash冲突是其他解决的方法？

  1.开放定址法：一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

  2.再哈希法：有多个不同的hash函数，当发生冲突时，使用第二个，第三个，直到没有冲突。造成计算的时间增大。

  3.链地址法：就是HashMap中的做法。

  4.建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，就存入到溢出表中。

• 既然HashMap是数组+链表，其中数组其实Entity数组，那么能用LinkedList或者ArrayList代替它吗？

可以用LinkedList或者ArrayList代替。

• 如果能用LinkedList代替的话，为什么不选择LinkedList而选择数组呢？

不选择LinkedList很明显，数组的使用效率远远高于LinkedList。对一个key值，我们用它的hash值对数组长度取模，得到了桶的位置，这时显然数组的查找速度要比链表快。

不选择ArrayList的原因是：采用基本数据结构，扩容机制可以自己定义，HashMap的扩容是2的次幂，保证了在做取模的时候效率最高，但是ArrayList的扩容机制是1.5倍扩容，显然不是很好。至于为什么ArrayList扩容是1.5倍，这里简单说明，ArrayList源码中的扩容部分有这么一段

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

直接定位到这句

int newCapacity = oldCapacity + (oldCapacity >> 1);

新容量通过移位操作变成了原来的大概1.5倍（其实好像大于1.5倍这么多，这边应该是个估计值），用移位操作是考虑到运算速度。

3.查找

HashMap的查找也就是通过key值找到value，具体来说可以分为两步：第一步根据key的哈希值找到相应的桶，第二步再根据equals()方法找到对应的value。其中肯定会涉及到对key值求hash值的方法，这边先解释这个函数。

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

以上是JDK1.8中的hash函数，并不是直接对key值的32位直接取模，而是先把高16位和低16位进行异或，再对新生成的数进行取模。至于为什么要这么干，和疑问二中的问题一起解释一下。

• HashMap在什么条件下扩容？

这个在之前就提到了，threshold=loadFactor*capacity。当HashMap中的元素个数大于threshold时会执行扩容（resize）操作。

• 为什么扩容是2的n次幂？

首先HashMap中判断把元素放在哪个位置的算法是取模，也就是用hash(key) % length，但是这种操作的效率没有移位运算的快，所以源码中采用hash(key) & (length-1)这种计算方法，这两种方法是等价的，hash(key) % length = hash(key) & (length-1)，但后者比前者的效率高的多。那为什么扩容是2的n次幂呢，比如说table的长度是16，也就是2的四次方，3&(16-1)也就是11&1111=0011=3，2&(16-1)=10&1111=0010=2，不同的位置不会发生碰撞，但是当table长度不符合2的n次幂时，比如为5，那么3&(5-1)=11&100=0，2&(5-1)=0，极易发生碰撞，不利于数据均匀分布在哈希表中。所以说保证table长度是2的n次幂时，在做length-1时就保证了所有位上都为1，与的时候就是和1111…..1111相与。也就是每一位都能&1。

• 为什么要先高十六位异或低十六位再取模运算？

HashMap采取这种操作是为了降低hash冲突。举个例子，当table的length为16时，哈希码为1954974008时

HashCode	111 0100 1000 0110 1000 1001 1000 0000
length=15	000 0000 0000 0000 0000 0000 0000 1111
&运算结果	000 0000 0000 0000 0000 0000 0000 0000

而先高十六位异或低十六位

HashCode	111 0100 1000 0110 1000 1001 1000 0000
>>> 16	000 0000 0000 0000 0111 0100 1000 0110
异或	111 0100 1000 0110 1111 1101 0000 0110
length=15	000 0000 0000 0000 0000 0000 0000 1111
与运算	000 0000 0000 0000 0000 0000 0000 0110

结果很明显，直接拿32位进行与运算，不管哈希码的高位如何变化，只要最后四位是0，最终的结果都是0。当高十六位与低十六位与运算之后再进行与运算，结果为6，使最终的结果会受到高十六位和低十六位的共同影响，避免当HashMap的长度过小时，产生的散列值只受到低16位的影响，减少了碰撞的概率。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 这边的(n-1)&hash = hash%n，也就是上文所解释的提高运算效率的取模方式。这边取到哈希表上对应key值的链表的第一个节点。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果链表上第一个节点就是要取的key值的话，就返回。
        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;
}

• 若为树，则在树中通过key.equals(k)查找，O(logn)；
• 若为链表，则在链表中通过key.equals(k)查找，O(n)。

4.插入

插入操作是HashMap中比较复杂的操作，因为其中涉及到当链表长度超过8的时候转换成红黑树，还会涉及到table的扩容，需要详细分析一下。关于什么是红黑树可以参考我的这篇博客[点击跳转]。

static final int TREEIFY_THRESHOLD = 8;

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 这边可以看到，table的初始化并不是在构造函数中进行的，而是在插入函数中进行的，这与之前说的相吻合。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果tab的这个位置没有元素，就直接插入。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果要插入的键值对的键是和hash(key)得到的这个桶的链表的头结点相同，将p保存在e之中。后面的代码会更新这个节点。相当于原来位置节点是a,1，更新之后变成了a,2。
        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);
                    // 如果链表长度超过8，则转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果链表中有一个节点的key值和要插入的新的key值相同，直接跳出循环，后面也会对其进行更新。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
               	// 指向下一个节点，让链表得以循环
                p = e;
            }
        }
        // 如果e不空，则意味着把相同key下的值更新了，返回
        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;
}

总结一下上一段插入操作的代码流程。首先如果table长度为0或者为空，则初始化table，分配初始容量。接下去如果table上的hash(key)的位置没有元素，则直接放入，不用考虑冲突。如果hash(key)有元素，则要进行插入操作或者更新操作。定位到桶的位置之后，如果恰好链表的头结点等于key值，则直接将头结点进行更新。如果是红黑树，就调用树的插入操作，如果是链表，则遍历整个链表，其中如果在链表中能找到对应的key值，则更新这个点，否则就将其插入链表的尾部，当链表长度大于8时，将链表转化为红黑树。最后只要table的容量大于阈值，就要进行扩容。

在插入时，如果链表长度超过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)
        resize();
    // 计算第一个节点的位置，也就是对应hash值的桶的位置。
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 这边其实是以hd头结点，tl尾结点构架起一个双向链表结构。
        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);
    }
}

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;  //root节点
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next; //下一个节点
        x.left = x.right = null;  //设置左右节点为null
        if (root == null) {//第一次循环 root==null
            x.parent = null; //根节点的父节点为空
            x.red = false;//根节点设置为黑色
            root = x;//将x设置为根节点
        }
        else {//根节点不为空，也就是不是根节点的情况走这边
            K k = x.key; //获取链表中下一个节点的key
            int h = x.hash; //获取链表中下一个节点的hash
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {//从根开始遍历
                int dir, ph;
                K pk = p.key;//遍历到的节点的key
                if ((ph = p.hash) > h)//遍历到的节点的hash值大于待插入点的hash值的时候，往左走
                    dir = -1;
                else if (ph < h) //否则往右走
                    dir = 1;
                //如果上面的两个分支没有走，则匹配到了相同hash值，则根据比较对象定义的comparable进行比较。比较之后返回查询节点路径（左或右）
                else if ((kc == null && 
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
				
                TreeNode<K,V> xp = p;
                // 当父节点的左右节点都为null的时候，进行节点的插入操作。这边的for一直循环，只有进到if里面才有机会break掉，也就是会一直找到一个左右节点都为空的节点，然后将待插入节点根据前面的dir值插入到左子树或者右子树。
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 相当于是红黑树插入了一个节点之后，需要对红黑树进行调整，转换成红黑树要求的形式。
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

继续进入到balanceInsertion(root, x);函数中，进行树的左右旋转调整。插入了x这个节点之后，需要对红黑树进行平衡调整。

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // 默认刚刚插入的点是红色的
    x.red = true;
    /**
    * xp:x的父节点
    * xpp:x的祖父节点
    * xppl:x的祖父节点的左孩子
    * xppr:x的祖父节点的右孩子
    */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 如果x没有父节点，说明当前x节点就是root节点，根据红黑树的性质，根节点为黑色
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 情况一：如果xp是黑色节点，那么x是红色节点插入就没关系，因为不影响平衡。可以直接返回
        // 情况二：如果x的父节点就是root，x是红色节点，那么父节点xp必为黑色节点。满足红黑树的条件，无需调整，直接返回。
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 如果x的父节点是左节点时候
        /**
                    xpp（黑 or 红）
                   /
                 xp（黑）
        */
        if (xp == (xppl = xpp.left)) {
            // 如果祖父节点的右节点不等于null，也就是父节点有兄弟节点，并且兄弟节点是红色。
            // 那么将xppr变为黑色，xp也变为黑色，xpp变为红色，达到平衡。
            /**
                     xpp（黑）                   xpp（黑）
                    /   \                       /  \
             （黑）xp   xppr(红)  ----->    (黑)xp  xppr(黑) 
                  /                           /
                 x（红）                     x(红)
            */
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                // 将x赋值为祖父节点。
                x = xpp;
            }
            else {
                if (x == xp.right) {
                    // 左旋
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        // 右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        // x的父节点为右节点
        else {
            // 验证是否需要旋转
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    // 右旋
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        // 左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

到此为止，关于红黑树的一些操作到此为止。接着回到该节的第一段代码，看看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;
    // 判断旧表容量值是否大于0，从而来判断是否是初始化的扩容。
    if (oldCap > 0) {
        // 如果旧表容量大于定义的容量最大值了，就把阈值设置为最大阈值的整数值，这边没有对旧表进行任何操作。
        // 转化为十进制后，MAXIMUM_CAPACITY = 1073741824 Integer.MAX_VALUE = 2147483647
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 初始化新容量值为旧容量值的2倍，然后与最大容量值比较，当新容量值小于最大容量值，且旧容量值大于等于默认初始化容量值，这时也对新阈值赋值为旧阈值的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap = 0时进入这个分支，也就是第一次初始化表。将新容量赋值为旧的阈值，旧的阈值也就是HashMap的初始化容量，因为在HashMap构造函数中有这么一句话   this.threshold = tableSizeFor(initialCapacity);
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 当oldCap 和 oldThr都为0的时候，用初始化容量对容量赋值，用初始化容量乘上负载因子对阈值赋值。这边应该是HashMap无参构造函数才有这种情况。
    else {               // zero initial threshold signifies using defaults
        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;
    // 因为数组不能扩容，所以扩容的话需要重新创建新容量长度的数组，然后将旧的数组上的值映射上去。
    @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;
                // 如果链表没有下一个元素，也就是链表的长度为1，则将e直接映射到新表。
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是红黑树，则按红黑树进行处理
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 在链表中有其他元素，而且也不是红黑树，说明链表长度不超过8，但是大于1。按照链表来处理。
                else { // preserve order
                    // 这里与jdk1.7有所不同，1.7是直接遍历元素计算散列值，然后再放入新的表中。具体的做法是新table[]的列表采用LIFO方式，即队头插入。这样做的目的是：避免尾部遍历。尾部遍历是为了避免在新列表插入数据时，遍历队尾的位置。因为，直接插入的效率更高，但是不可避免的在多线程环境下会出现死循环的问题。而在1.8做了优化。
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // resize之后不需要改变原来元素的位置。将这类元素存放在链表lo中，loHead为链表的头，loTail为链表的尾。
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // resize之后原来元素的位置改变。将这类元素存放在链表hi中，hiHead为链表的头，hiTail为链表的尾。
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 对一条链处理完毕之后会产生两条新的链表，lo是不变位置的点组成的链表，hi是位置变化的点组成的链表。
                    if (loTail != null) {
                        loTail.next = null;
                        // 直接插入新表的j这个位置。
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 插入到j+oldCap的位置。
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

我们把上面后半部分将数据插入新表的代码拿出来分析一下。

• (e.hash & oldCap) == 0 是什么意思？

如果这个判断为true则说明e这个节点在resize之后不需要挪位置，反之则需要换个位置。举个简单的例子，比如有1，17两个数，在HashMap大小是16的时候，他们的hash值都是1，如果此时扩容为32，可以看出1的hash是不变的，但是17是会变，也就是说 1 & 16 = 0， 17 & 16 != 0

• 在jdk1.7中产生死循环，CPU占用率100%的原因？

在单线程的情况下的rehash，每次都是插入在链表的头结点上，用这种头插法也提高了插入的效率。

但是一旦在并发的情况下rehash就可能出现问题

如上图，当线程一e指向key=3，next指向key=7。线程二执行完成，由于是头插法，key=7在key=3之前。此时线程一继续执行。执行newTable[i]=e 和 e=next 两句。忽略key=5的那一个，执行线程一发现，此时3的next指向了7。造成了一个循环。

此时，如果调用get方法去取key值为7或者3的时候，就会引发死循环的发生。而在jdk1.8中，通过增加tail指针，既避免了死循环问题（让数据直接插入到队尾），又避免了遍历链表提高了效率。扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。但是在并发的情况下还是会有问题。

至此为止，问题三几乎都能解决了

• hashmap中get过程是怎么样的？

见上文get部分的代码

• hashmap中put过程是怎么样的？

见上文put部分的代码

• hash算法有哪些？

Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。 比较出名的有MurmurHash、MD4、MD5等等

• String中hashcode的实现？

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

输入的字符串是“abcd”的话，计算方式就是：

第一次：h = 31*0 + a = 97

第二次：h = 31*97 + b = 3105

第三次：h = 31*3105 + c = 96354

第四次：h = 31*96354 + d = 2987074

计算公式就是：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

那为什么以31为质数呢?

主要是因为31是一个奇质数，所以31*i=32*i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。

继续解释问题四

• 为什么在解决哈希冲突的时候，不直接用红黑树而是选择先用链表，再用红黑树？

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。 当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

• 红黑树用二叉查找树可以吗？

二叉查找树是可以的，但是在特殊的情况下会变成一条线，查找效率低下，具体的可以参看我关于红黑树的博客。

• 为什么链表转化为红黑树的阈值是8？

这个问题我参考了网上的一些回答，各有个的说法，其实选择为8应该是在时间和空间上权衡出来的结果。我认为这篇博客的观点比较有道理一些，可以参考一下。

• 当链表转化为红黑树之后还会退化成链表吗？如果会退化，什么时候退化成链表？

为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

顺带着把问题五给解决了

• HashMap在并发编程环境下有什么问题？(针对jdk1.7来说)

在多线程的情况下进行扩容，rehash的时候会造成问题，引起死循环。

多线程put的时候导致元素的丢失

put非null元素后get出来确实null

• 在jdk1.8中还有这些问题吗？

在jdk1.8中死循环的问题已经解决，但是其他两个问题在多线程的情况下还是存在的。

• 并发问题一般应该如何解决？

可以用线程安全的集合类，比如说ConcurrentHashmap，Hashtable等。

5.删除

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 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        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;
}

有了查找插入等的源码基础，看明白删除就是一件非常简单的事了。删除也就是在找到对应的元素后将该元素移除即可。同样的，会涉及到链表的操作或者红黑树的删除操作等，这边就不赘述了。

这边再回答一下问题六

• Key值可以为空吗？

key是可以为null的，之前提到的hash函数是这样写的

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

这边可以看到，当key值为null的时候，返回的hashcode也就是0，最后取模之后也就是存放在table的第0个位置。

• 一般用什么当做HashMap的Key？

一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。注意：在使用自定义类对象当做hashmap的key的时候，需要重写hashCode()以及equals()方法。

• 可变类当HashMap的Key有什么问题吗？

当可变类当做hashmap的key值的时候，可能当这个类型的对象发生改变后，hashcode值会发生改变，导致无法get出来。

• 如果要自己实现一个自定义的class作为HashMap的key应该如何实现？

1.要设计一个不变类当做key

2.根据特定的需求来重写hashcode和equals方法。

三、总结

最后再来总结一下hashmap常见的几个问题

1.问题

Q：从jdk1.7到jdk1.8，HashMap做了哪些修改？

A：

• jdk1.8之前是采用数组+链表的结构，而到了jdk1.8之后就改为数组+链表+红黑树的结构。并且在链表长度达到8以上的时候自动转化为红黑树，在节点数量达到6的时候又退化成链表。
• 优化了高位运算的hash算法：h^(h>>>16)，减少了碰撞的概率。
• 扩容部分发生的变化，jdk1.8在扩容重新分配上使用了新的方法，jdk1.7的扩容是直接对每个元素重新计算hash取余的结果，再用头插法插入相应的位置中，但是jdk1.8是采用将结果暂时放在两个链表中，扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。这也在jdk1.8中解决了并发情况下的死循环问题。

更新：2019年10月10日

2.扩展

HashMap的用法和源码解析基本都在上面可以找到了，另外还有两个特殊的Map类，分别是LinkedHashMap和ConcurrentHashMap，都是十分常见的，可以用于不同的场景，那么它们是如何实现的？

LinkedHashMap

1.介绍：首先LinkedHashMap继承于HashMap，并实现了Map接口。众所周知，HashMap是无序的，当我们希望有顺序地去存储key-value的时候，就需要用到LinkedHashMap了。也就是当一组数据，它们以什么顺序插入，那么就会以什么顺序输出。

2.那么简单的说它是如何实现有序的呢？它是通过维护一个运行于所有条目的双向链表，LinkedHashMap才能保证元素迭代的顺序，但是却增加了时间和空间上的开销。具体的源码层面的分析会在后面再写。

ConcurrentHashMap

1.介绍：之前也介绍过ConcurrentHashMap这个类，用于并发情况下的Map类，与前面介绍的HashMap不同的，它是一个线程安全类。

2.那么简单的说它是如何实现线程安全的呢？

jdk1.7使用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构。

jdk1.8是利用CAS+Synchronized来保证并发更新的安全，底层采用数组+链表+红黑树的存储结构。具体的源码层面的分析会在后面再写。

参考

https://www.cnblogs.com/gxyandwmm/p/9537669.html

https://zhuanlan.zhihu.com/p/76735726