[Java]重学Java-关于HashMap被问就倒这件事

为什么需要Map

前面我们介绍了数组和链表，他们可以按照插入的次序进行排序，但是查询需要用到index，要么就是要遍历，如果列表中放置了很多元素，此时遍历带来的搜索成本会大大增加，所以我们需要一种集合，来实现快速查找而不在意顺序这么一个需求。Map就油然而生了。

哈希表

哈希表通过哈希算法为每个元素计算出一个整数(hashCode)，然后跟桶(桶的概念就是数组+链表)的总数做取余操作，得到桶的索引值。
在这个过程中，会出现哈希冲突的问题,也就是不同数值的key都算出了一样的hashCode，这个时候就要解决哈希冲突。
在Java里面，解决哈希冲突采用的是链地址法，满足一定的条件后，会进行rehash.

假设一开始是一个数组:

数组

发生哈希冲突,两个元素都算出了0这个索引.

冲突

此时，又会产生一个新的问题，假设一直在这个"0"索引发生了冲突，会导致一条很长的链表，那其实搜索的成本又增高了,这个时候，可能会进行红黑树化

红黑树

如果桶元素超过了一定的数量，那么就会进行扩容，然后rehash.

HashMap的重要参数

初始化容量

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

别看着这东西很唬人，其实就是用位运算算出16，也就是初始化容量是16.

装载因子

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

如果构造器不指定，那么就是0.75，也就是元素达到这个16*0.75=12的时候，会进行扩容，扩容其实就是执行以下操作，变成原来的2倍:

 newThr = oldThr << 1;

树化因子

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

通过代码阅读，当元素大小超过64(MIN_TREEIFY_CAPACITY)并且链表长度大于这个树化因子8的时候，链表就会转换成红黑树

为什么装载因子是0.75，树化因子是8?

问这个就有点卷了，不过不用担心，作者已经告诉你答案了。

 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million

意思就是，根据概率论中的泊松分布原理，在0.75和8的作用下，再冲突的概念已经达到千万分之一了，如果硬要转，那就转成我们的红黑树.

如果觉得不能理解，可以看以下的博客:

HashMap加载因子为什么是0.75？转化红黑树阈值为8？

非树化因子

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

如果红黑树的元素小于6，那么退化成这个链表.

put

为什么put这么重要，我敢说很多面试的人都死在这里，那么既然面试官这么喜欢问，我们就来好好看.

hash

• java.util.HashMap#put

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

• java.util.HashMap#hash

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

这里我们看到，key不为空的时候，执行的操作是(h = key.hashCode()) ^ (h >>> 16),背后有很多学问。

1. 先做hashCode得到h.
2. 将h做右移16位的操作(为什么先执行这步，其实就是先算括号里面的公式再进行符号操作)得到另一个数.
3. 将h和h右移16位之后的值做异或(^)操作

为什么要做高位异或

先来看一下JDK的解释:

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

Google翻译一下:

计算 key.hashCode() 并将哈希的较高位传播（XOR）到较低位。 由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突。 （已知的例子是在小表中保存连续整数的 Float 键集。）因此，我们应用了一种变换，将高位的影响向下传播。 在位扩展的速度、实用性和质量之间存在折衷。 因为许多常见的散列集已经合理分布（所以不要从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，我们只是以最便宜的方式对一些移位的位进行异或，以减少系统损失， 以及合并最高位的影响，否则由于表边界，这些最高位将永远不会用于索引计算。

我先说一下我的理解，hashCode在二进制上是32位的,大量的实践表明，低位的掩码容易发生冲突(也就是算出来都一样),那么最终会导致，很多不同的key算出来其实都在同一个bucket的位置上。这个时候，将h右移16位，然后做异或操作(这个也见过面试官提问，异或是最为散列的一种方法)，可以得到更加散列的数据，也就是冲突会大大减少.

关于这个问题，你也可以看:
肥朝:JDK1.8中HashMap如何应对hash冲突？

定位

好，算出所谓的hash值后，还得经过p = tab[i = (n - 1) & hash来做定位.

• java.util.HashMap#putVal

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);   

在做求索引值之前，会先判断当前的table是否为空，如果为空，需要进行初始化.
否则，根据hash算出p所指向的元素位置,这里注意看，if里面的逻辑一定会执行，但是newNode不一定执行.

Node为空，直接插入

• java.util.HashMap.Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

Node，其实就是链表元素的实现。如果是一个链表，那么next会指向下一个Node.

• java.util.HashMap#putVal

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

这里通过hash和n-1做与操作后，计算出tab[index],然后赋值给p,那么此时p指向了计算后的Node,如果当前Node指向null,那么进行new Node，也就是放入当前元素。

Node不为空，先做equals,如果equals相同则更新

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 省略
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
    // 省略
}

如果hash值相等，那么进行equals比较是否为同一个key，如果是，那么进行更新值就行,如果不是，那么就是发生了哈希冲突，就要进行我们上面所说的操作了，链地址法或者红黑树。
这里就是为什么我们说，如果使用对象作为Key,一定要重写hashCode和equals的原因。

哈希冲突,如果Node为红黑树，转换后进行put

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 省略
    else {
        // 省略
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    }
}

如果当前的Node属于红黑树，那么转换成红黑树的对象(TreeNode)再做put操作.

哈希冲突,逐一遍历Node，进行equals操作，如果true则break并更新元素，如果穷举节点，则插入元素

else {
    for (int binCount = 0; ; ++binCount) {
        // 如果next指向null,说明要插入一个Node
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            // 如果binCount大于7，从0开始，其实就是说，链表长度大于8了
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        // 如果能找到euqals相等的值，做更新操作g
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

到了这里，其实进入到了一个死循环里面，要跳出这个死循环，就看里面的两个大的if条件:

1. e = p.next)== null，穷举到最后的节点了，说明此时前面的元素都被equals比较过了，没有发现需要更新的元素，那么这是一个新增的操作，执行插入。然后再看binCount，每次循环都会自增，这个代表的是链表的长度，如果大于8，那么就要执行treeifyBin.
2. e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))),就是对比hash和equals，如果相等，说明要做更新操作，退出循环,此时的e已经指向存在的那个元素了,更新完直接return:

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;

先插入，然后看看元素是否超过threshold,这个值是在初始化的时候赋值的,它的取值:
threshold=capacity*loadFactor,也就是元素不能超过总容量的75%.

get

理解了put后，再看get就清晰很多

• java.util.HashMap#get

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

• java.util.HashMap#getNode

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        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;
}

1. 定位，也就是通过hash和(n-1)&hash算出index
2. 查询首节点是否为空，空则直接返回
3. 进行equals和hash操作,如果是同一个key，return
4. 遍历，如果是树，则按树的取值流程返回；如果是链表逐一euqals比对得到Node后返回;如果未能匹配，返回null.

为什么HashMap的底层数组长度总是2的n次方

首先是hash进行了高位异或，为了更好地进行与操作代替取模，就要求length为2的幂次方.

答案可以前往这里查看: JDK1.8中HashMap如何应对hash冲突？

Hash线程不安全的表现

JDK1.7扩容产生的环形链表

这个需要结合数据结构理解，好文推荐:
疫苗：JAVA HASHMAP的死循环

JDK1.8值覆盖

简而言之，就是put的时候，有两个线程，都进行了hash得到当前node为空的判断，然后A进行了new Node,随便B得到时间片，也进行了new Node，那么此时在同一个槽位，只会得到一个元素。按正常的逻辑走，应该是后面进来的需要判断前面的线程已经插入了数据，做链地址法的操作才对。

肥朝:彻底理解HashMap及LinkedHashMap

链表何时转化为红黑树

链表长度为8时，进入java.util.HashMap#treeifyBin代码块，然后再判断(n = tab.length) < MIN_TREEIFY_CAPACITY是否小于64，如果是则扩容，否则进行树化。
那么答案就是,链表长度>8并且bucket元素超过64时.

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

强烈推荐

Java 8系列之重新认识HashMap
JDK1.8中HashMap如何应对hash冲突？
肥朝:彻底理解HashMap及LinkedHashMap