Java8 HashMap常见问题的源码简读

HashMap是最常用的Map集合,从代码实现上讲也有很多巧妙的地方,所以面试的时候相关的问题也很多,这次我们就带着问题来简单看看HashMap的源代码,找到问题的答案。

Hashtable、HashMap、TreeMap三者的区别

在看HashMap之前,先了解一下其他的Map。Hashtable、HashMap、TreeMap三者的区别是面试中经常遇到的问题。

线程安全方面:Hashtable是线程安全的;HashMap、TreeMap是非线程安全的。

键值方面:Hashtable的键值都不支持null; HashMap的键值都可以为null; TreeMap的键不能为null,但值可以为null。

是否有序:Hashtable和HashMap是无序的; TreeMap是有序的,具体顺序由Comparator来决定,或者根据键的自然顺序来判断。此外,还有一个LinkedHashMap也是有序的,顺序是按照插入顺序排列。

LinkedHashMap

LinkedHashMap其实就是继承了HashMap,不同之处是它通过维护了一个双向链表,记录了Entry的插入顺序,使我们在遍历时可以按照插入的顺序访问。

另外我们使用LinkedHashMap可以很轻松的实现LRU算法(Least Recently Used的缩写),即最近最少使用。我们在维护内存或者缓存时都可以用到LRU的思想,如果一个对象最近被访问,那么我们可能还会访问它;如果一个对象一段时间内都没有被访问,那么之后可能也不会访问它,那么在空间不足时优先删除不常访问的对象。

LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<String, Integer>(8, 0.75F,true){
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size()>3;
    }
};

使用LinkedHashMap我们只需要设置accessOrder为true并且重写removeEldestEntry方法,设置最大缓存空间,上面设置为3,即只能缓存3个对象,插入第四个的时候,会自动删除最老的对象。

要注意,在我们设置了accessOrder为true后,我们访问某个对象时,这个对象都会被重新放置到队尾,从而实现了最老的对象在队首,最新的对象在队尾。

HashMap

终于到了HashMap,先来说说JDK1.8对HashMap的优化。
在1.7及以前,HashMap原理就是数组+链表。而从1.8开始,HashMap变成了数组+(链表or红黑树)。那么我们的第一个问题也就来了。

1.HashMap为什么要树化?

java8中HashMap为什么变成了数组+(链表or红黑树),归根结底是性能问题。我们知道HashMap的时间复杂度通常是常数级的,但是在特殊情况下,所有的对象全部都在一个桶中,那么HashMap就会退化为链表,最坏的情况为O(n)。为了防止这种情况的发生,在一定情况下我们把链表转换为红黑树,避开最坏情况。

但是为什么是红黑树而不是其他树呢?第一它查找元素非常高效。第二,红黑树是自平衡的二叉树,在增加和删除节点时都会自平衡,满足HashMap的使用场景。

既然红黑树这么好,为什么不直接采用数组+红黑树呢?因为红黑树非常复杂,增加和删除节点的时还要左旋右旋变色等操作,也是会消耗性能的。所以在元素较少时我们还是使用链表,毕竟增删很方便。

什么时候树化呢?这个问题就必须要看源代码了。
树化是通过treeifyBin方法来实现的:

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    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) {
            // 树化过程
        }
    }

当容量(又或者说桶的个数、数组长度)小于MIN_TREEIFY_CAPACITY时,只是进行扩容。也就是说,容量必须大于等于64时才会考虑是否树化。等等,这个数字怎么和网上其他人说的不一样啊?别急,我们再看看哪儿在调用treeifyBin方法。
看putVal方法中的这一段代码:

    /**
     * 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;

    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);

binCount是链表的长度,也就是说树化有2个条件:
1.hashMap的容量大于64。
2.链表的长度需要大于等于8个。

树化其实就是JDK1.8中HashMap的最大变化了,至此好像关于树化的问题就搞定了,毕竟红黑树怎么旋转其实是另外一个话题了。

2.HashMap怎么确定一个元素应该在哪个桶中?

HashMap的hash和Object的hashCode是不同的。

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

HashMap有自己的hash算法,它会把key的hashCode的高16位和低16为做异或运算,从而得出hash。

为什么要把高16为与低16为做异或运算呢?简单的说是为了把元素尽可能随机的放到对应的桶中。因为有的元素可能hashCode的差异主要是在高16位,如果不做这样的操作,那么元素可能会集中在某几个桶中,影响性能。

不过仅仅这样还是不足以保证元素随机分配到不同的桶里。这里就涉及到了另一个问题:为什么HashMap的容量都是2的N次幂的大小?我们又看看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);
    else {
        // ......

在增加元素的时候,首先判断了一下table是否为null,为null或者容量为0则需要去创建table,创建table是调用的resize方法,可见resize既负责扩容,又负责创建HashMap。

代码tab[i = (n - 1) & hash]其实就是tab[(n - 1) & hash],n就是容量。而这个元素的位置是(n-1)和之前计算的hash值做与运算得到的。

为了方便理解,我们举一个栗子。我们创建一个容量为8,负载因子为0.75的HashMap,现在我们往里面增加元素。
第一个元素的hash的二进制为0001,(n-1)的二进制为0111,得到桶的下标的二进制为0001,即tab[1]。
第二个元素的hash的二进制为0011,(n-1)的二进制为0111,得到桶的下标的二进制为0011,即tab[3]。

这两个元素被放在了不同的桶中。现在我们假设容量不是8,而是6。
第一个元素的hash的二进制为0001,(n-1)的二进制为0101,得到桶的下标的二进制为0001,即tab[1]。
第二个元素的hash的二进制为0011,(n-1)的二进制为0101,得到桶的下标的二进制为0001,即tab[1]。

发现问题了吗?他们被放在的同一个桶中,而由于是做&运算,所以tab[2]是永远不可能有元素的,这个桶就被浪费了。所以,只有让容量为2的N次幂,才能保证每个桶都被用到,再加上之前的hash算法,就能尽可能保证每个元素被随机放到桶中。

那么如果我们偏偏就不把容量设置为2的N次幂,你能把我怎么样呢?不怕,看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);
}
/**
* 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;
}

HashMap会自动将你输入的容量,设置为比它大的、最近的一个2的N次幂数。比如7会设置为8;10会设置为16;17会设置为32等等。

3.HashMap是怎么扩容的?

为什么需要扩容呢?HashMap默认的容量是16,当我们有很多个元素需要放到HashMap中的时候,很显然每个桶中的链表就会变长,导致性能下降,所以需要扩容。之前说了,HashMap的扩容方法是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;
    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
                    // ...
                }
            }
        }
    }
    return newTab;
}

从上面我们也可以知道resize方法身兼两职,既需要负责初始化,又需要负责扩容。扩容必须要满足前提,小于最大容量限制,即2的30次方。

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

在此基础上,会把原来的容量,通过位运算翻倍,也顺便保证了容量为2的N次幂。

那么什么时候会进行扩容呢?扩容的条件是什么?看putVal的代码后面的一段:

if (++size > threshold)
    resize();

threshold即阈值,这个阈值是怎么来的呢?

/**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

看注释:capacity * load factor。同时再看看resize方法中的这一段代码:

    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

阈值为容量*负载因子。默认容量16的情况下,阈值为12,即超过12个就会发生扩容。

知乎上看了这么一个问题:hashmap扩容时每个entry需要再计算一次hash吗?现在的问题是如何理解这个“重新计算hash”。网上有人认为需要,理由是resize的时候需要重新计算下标,规则是hash & (n - 1),如果把计算下标也理解为“重新计算hash”的一部分,那么答案是需要的。但是如果是指的Node的hash,那么不需要,同一个entry的key值是固定的,key不变,对应的hashCode也不会变,所以计算的hash也就不会变,所以不需要重新计算hash。但是!扩容的时候需要根据hash重新把所有元素放入对应的桶中,这一点就是之前对应的重新计算下标的那一步,一定不要忘记。

想想原来是16个桶,扩容后变为32个桶,如果不重新将元素放入32个桶中对应的桶,那么在取元素的时候是按照32个桶来计算下标的,取元素就会出错。

那么问题又又又来了,扩容会影响性能,那么怎么尽可能防止扩容带来的影响呢?虽然随着数据量增加扩容不可避免,不过我们可以尽可能的避免扩容的发生。刚刚我们已经知道了,当元素个数大于容量*负载因子的时候,会发生扩容。所以我们可以在初始化的时候设置容量的大小为(元素总数 / 负载因子)即可。

HashMap负载因子默认为0.75,一般来说不需要改动。如果负载因子变小,那么可能会浪费更多的空间;如果负载因子变大,那么每个桶中的元素个数可能变多,影响性能。

好了,到此HashMap的问题基本就差不多了,以上虽然只有3个大点,但是每个大点都包含了很多小点,加粗字体别忘了看。如果还有什么问题,请留言。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据