java集合类之HashMap

概述

世间本没有集合，只有数组、链表，特定场景的需求多了，就逐渐衍生出了集合，java中的集合也确实是比较好的源代码，并且面试的过程中 也会比较多的考到这些内容，因此有必要去详细的剖析一下，就先从HashMap说起吧。

详解

在介绍代码以及操作之前，先来看一下HashMap的结构，这样后面也会有一个比较清晰的认知：

如上图所示HashMap是由一个链表和一个数组构成的，通常来说我们看代码的核心在于源代码，不过HashMap的核心个人以为在于重要的参数， 这里我们先来看一下这些参数分别是什么，后面再分别来看一下为什么这些参数的的值设置成这些。

• DEFAULT_INITIAL_CAPACITY = 1 << 4;：这个是桶的默认的大小，也就是上图中数组的大小
• MAXIMUM_CAPACITY = 1 << 30;：这个是桶的最大的大小，也就是最多可以是2^30，一般很少能够达到这个体量
• DEFAULT_LOAD_FACTOR = 0.75f;：负载因子，该值代表的是HashMap扩容的阈值，该阈值是集合中元素的个数和桶个数的比值，并非是使用的桶的比例（有可能出现hash冲突，多个元素放置到一个桶中）
• TREEIFY_THRESHOLD = 8;：这个参数是在JDK8中新引入的，代表了当某一个桶中的元素个数由于哈希冲突达到一定的阈值之后，链表就会树化，不过这并不是充分条件，而是必要条件，树化的 另外一个必要条件是桶的大小达到了64以上
• UNTREEIFY_THRESHOLD = 6;：由树退化成链表的条件，这里不是7的原因是留一个缓冲区，避免链表和树频繁的转化
• MIN_TREEIFY_CAPACITY = 64;：桶中的链表树化的另外一个必要条件

构造函数

提起hashmap，还是先从构造函数说起吧：

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

上面的构造函数中可以看到HashMap的构造函数其实仅仅初始化了两个参数：initialCapacity、loadFactor，这两个参数是HashMap 的核心参数，分别代表了初始的容量的大小，以及负载因子的大小，不过上面上面在计算扩容阈值的时候，并不是简单的将构造函数传进来的 initialCapacity和loadFactor简单的相乘，而是调用了tableSizeFor(initialCapacity)函数，这里我们也来看一下究竟做了什 么处理，如下：

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

来到这里一眼望过去就是一堆的移位操作，想说一句MMP的，什么鬼玩意儿。概括的来说：这里就是为了取一个不比cap小的最小的2^n幂。 至于为什么取成这么一个值，我们可以先不用关心，继续往下看。

上面的构造函数的过程中我们并没有看到桶的初始化，而仅仅是初始化了一些基本的变量，那么不禁要问一句，桶的初始化是在哪里呢？ 这里是一种lazy 的机制，只有在使用到HashMap的时候才会真正的创建HashMap所需要的桶，我们就来看一下put操作是什么样子的：

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
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;
    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);
    else {
        Node<K,V> e; K k;
        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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                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;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

在解读集合代码的时候很多人都说要多看注释，起初我是不以为意的，但是随着了解的深入就发现，确实注释是比较有营养的。 在put操作上面的注释中我们可以看到HashMap是允许key值为null的，并且允许value为null，因此当我们使用获取某一个值返回为null的时候 并不能说明HashMap中没有该key，也有可能是key对应的value为null。

续接上文，桶的初始化是什么样的一个流程，在我们真正的使用put操作取填充HashMap的时候，我们看到首先定义了一坨变量，并进行了响应的判断：

Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

这里首先是判断table是否为空或者长度为0，如果是的话，这里首先会使用resize方法初始化tab，如下：

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    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;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    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;
}

如上，前面一坨代码是用来确定桶的大小以及阈值并创建空桶的，真正的操作在于下面的循环中，不过当前由于oldTab为null，因此这里会直接返回一个新生成的 桶。

真正的put操作还在上一个代码段的下半部分，首先会进行一个判断(p = tab[i = (n - 1) & hash]) == null，在继续解说之前还必须要讲明白的就是hash 值是怎么来的，如下：

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

这里就到了精髓部分了，我们可以看到当key为null的时候将会得到一个0的hashcode，而key不是null的时候是会将key的hashcode值和其自身无符号右移16为按位异或， 这里可能会有人有疑问，为什么要无符号右移16为，直接取hashcode不香么？这个原因在于通常情况下我们的桶的数量都是比较小的，如果我们直接将得到的hashcode与桶的大小 进行取模，可能产生的hash冲突会比较大，原因在于hashcode的高位都没有用上，因此这里采用了这种方式将hashcode进行移位操作来充分使用高位的数据，至于这里为什么要 使用异或的方式，&或者|可不可以呢？那肯定也是可以的，只不过这种不是一个好的选择，原因在于按位|的方式当hashcode的某一位为1的时候，结果就可以确定了，而当hashcode的某一位 为0的时候，按位&的方式结果也确定了，这从一定的程度上缩小了离散的可能性，增大了hash冲突的可能，因此这里才使用了异或的方式来计算hashcode的值。

续接上文对某一个桶是否为空的判断，当桶中对应的元素为null的时候表示桶还是空的，因此我们可以直接放入数据，当桶中存在数据的时候会对桶中跟节点的类型进行判断， 具体分成两种情况，如果是一个TreeNode，我们就调用树的方法存放对应的数据，否则的话就直接通过一个死循环将节点追加到列表中，不过在追加的过程中增加了对是否树化的判断， 具体条件就是链表的长度是否达到了8并且桶的大小是否已经达到了64。最后判断桶中容量的大小是否已经扩容的阈值，如果达到扩容的阈值就进行resize，resize代码如上。

这里我们假定已经达到了阈值需要进行resize，我们可以看一下resize具体执行了什么操作吧

• 容量和阈值都通过移位操作扩充为原来的2倍
• 通过rehash操作将桶中的链表进行rehash

阈值以及容量扩充为原来的2倍，这个我们没有疑问，rehash的一个过程是什么样子的呢？核心在于：

if ((e.hash & oldCap) == 0) {
    lo.....
}
else {
    hi.....
}

最初看到这段代码的时候我其实是一脸疑惑的，后来查阅资料才发现这里其实也是为什么桶的长度设置为2^n的原因原因在于rehash的过程中，很多人第一眼看到 e.hash & oldCap可能会和e.hash & (n-1)混淆，不过真实因为&oldCap，所以这里其实是取的e.hash&100000....而不是e.hash&111111....， 这里oldCap要多出来一位，因此如果e.hash & oldCap为0的话，则说明e.hash的高1位并没有什么卵用，因此重新rehash的时候依然是落在这个桶里面， 而e.hash & oldCap如果不为0的话，hashcode的高位必然是有用的（并且&的结果是oldCap），因此最终的结果必然是将该元素移动到current+oldCap的位置。

get方法

上面简要的分析了一下构造函数以及put的整体流程，接下来看一下我们获取元素的方法，如下：

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

hashmap的get方法如上所示，先来解读一下注释：注释说了，存在两种情况

• 一种是返回不是null的情况，这种情况下可能是key为null或者key不为null的情况，不过元素肯定是存在桶中的
• 另一种是返回值为null的情况，这种情况下key可能为null并且对应的value存在且为null，或者元素根本就不存在桶中

区分key到底寸步存在不可以使用get方法进行判断，而只可以使用containKey方法进行判断

上面的get方法最终会执行到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;
}

可以发现，整个过程也是比较简单的过程，是直接判断链表中、或者树中的的每一个元素是否 满足hash值是否相同并且key相等或者key使用equals方法判断仍然相等，如果是说明我们找到了该元素，否则的话就继续找下去。

参数取值考究

红黑树及阈值

为什么jdk8使用红黑树：红黑树的查询效率为O(log n)，链表的查询效率为O(n)，既然如此为什么不从一开始就考虑使用红黑树 来代替链表呢，这是因为红黑树的一个TreeNode占用的空间为Node的2倍（可以通过查看内部类）。既然如此，为什么树化的阈值是8呢？因为 使用随机的hashcode的情况下，很少会出现桶中元素的个数大于8的情况，如果用于自己实现了并不是优选的hash算法，可能会 导致某一个桶中的数据会比较多，使用随机的hashcode的情况下所有的桶中数据的分布会呈现波松分布，如下：

* 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

可以看到一个桶中长度为8的可能性是：0.00000006（这里波松分布是指在桶中存放的元素的个数的概率分布，元素长度 概率分布随元素的个数呈现出波松分布），这几乎是不可能的事情，因此 树化的阈值选择了8，而由treeNode转化为链表的阈值是6，并不是7，这是增加了一个长度的缓冲区，避免树和链表之间频繁的转化。

为什么loadfactor是0.75

hashmap存在负载因子是在时间和空间上做的折中，时间上的折中是如果我们的负载因子为1，那么我们往里面存放数据等于 桶的个数的时候才会进行扩容，如果我们的hash算法能尽量保持均衡的话还好一点，否则我们将有可能在某一个桶中存放了一个长的 链表，我们知道链表的查询效率为O(n)，降低loadfactor就可以让数据在较少的时候触发rebalance，这样可以减小由于hash碰撞 生成的链表过长导致的查询效率降低的问题。而如果loadfactor太低的时候，可能出现的问题是桶的利用率太低，浪费很多空间，至于为什么 是0.75而不是0.6或者0.8，这个也只是个经验值，也是经过大量的统计得出的最优质。

hashmap为什么每次扩充元素，选择为原来的2倍：

这个要回归到hashmap确定元素的方法上来：tab=[(n - 1) & hash]，当n为2的n次幂的时候，一个好处就是n-1的低位全部是1， 这样就能够hash的低位特征能够被全部保留下来，至于不采用取余的方式，是因为位运算的效率肯定是高于取余运算的，如果我们 设定的table不是2的幂，那么会有什么问题呢，其实这个也不会有问题，在上面的构造函数中，我们可以看到有一行代码： this.threshold = tableSizeFor(initialCapacity);，这一行代码就是专门用来将我们非标的容量参数转化为标准的参数的， 具体如下：

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

这一步的操作是将cap-1的低位全部置为1的过程，最后判断n是否小于0或者大于允许的最大容量，来确定最终的容量的大小的过程！

modCount引发的问题

在实际的工程实践中，曾经遇到过的问题是在遍历一个map的过程中又改变了map的结构，这里改变结构是指增加或者删除一个元素，结果 引发了一个并发改动的异常问题，模拟代码如下所示：

@Test
public void test() {

    Map<String, Object> map = new HashMap<String, Object>(){{
        put("aaa", 123);
        put("bbb", 456);
        put("ccc", 678);
    }};

    for (String key : map.keySet()) {
        if ("aaa".equals(key)) {
            map.remove(key);
        }
    }
}

抛出异常如下：

java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
	at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
	at com.hw.config.BatchConfig.test(BatchConfig.java:21)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
	at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:68)
	at com.intellij.rt.execution.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:47)
	at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:242)
	at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:70)

通过跟进代码发现是由于一个变量：

/**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
transient int modCount;

由于HashMap并非是线程安全的类，因此，当有一个线程在访问HashMap的时候，另外一个线程改变了HashMap的结构，这样就可能会引发并发的问题，因此 采用了这种fast-fail的方式尽量保证了多线程情况下的程序的正确执行。上面的代码中很明显是一个线程，不过这里很明显缩小了失败条件的范围。

其他

头插法与尾插法

resize采用的是尾插的方式，如果是头插的方式会存在并发的问题，参见： 头插法死循环问题

小结

上面初步对HashMap进行了分析，后面会对比一下HashMap的其他实现类以及其他的集合类的具体实现