一文精通HashMap灵魂七问,你学还是不学

如果让你看一篇文章,就可以精通HashMap,成为硬刚才面试官的高手,你学还是不学?

别着急,开始之前不如先尝试回来下面几个问题吧:

HashMap的底层结构是什么?

什么时候HashMap中的链表会转化为红黑树?

为什么当链表长度超过8个时候会转化成红黑树?这为什么是8个而不是3个呢?

HashMap是线程安全的嘛?

HashMap为什么是线程不安全的?有哪些具体体现?

ConcurrentHashMap和HashTable是如何实现线程安全的呢?有何不同呢?

一、HashMap底层结构是什么样的?

HashMap底层是数组+链表+红黑树组成的复合结构。

数组被分为一个个的桶(bucket),通过哈希值决定键值对在数组中存储的位置;

当键值对的哈希值相同,则以链表形式存储;

当链表长度大于或等于阈值(默认为 8)的时候,如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY(默认为 64)的要求,就会把链表转换为红黑树。同样,后续如果删除了元素,当红黑树的节点小于或等于 6 个以后,又会恢复为链表。

HashMap 的结构示意图:

二、为什么需要将链表转化为红黑树呢?

因为红黑树有和链表不一样的查找性能。从链表中查找一个元素,时间复杂度是 O(n)。而从红黑树查找,由于红黑树有自平衡的特点,可以防止不平衡情况的发生,所以时间复杂是 O(log(n))。如果链表长度较短,O(n) 和 O(log(n)) 的区别不大,但是如果链表较长,那么这种差异就会很明显了。所以为了提升HashMap查找性能,在链表长度超过阈值的时候将链表转化为红黑树进行存储。

三、既然红黑树查找性能优于链表,那为什么不在一开始就使用红黑树呢?而是要经历一个转换的过程呢?

世上本没有“银弹”,红黑树也不是“银弹”。单个 TreeNode 需要占用的空间大约是普通链表Node 的两倍,所以只有当包含足够多的 Nodes 时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的形式,以便节省空间。

这其实是一种tradeoff,指的是一种取舍、一种权衡,最后达成折中平衡。在HashMap里面,如果要性能就需要牺牲空间,要空间就要牺牲性能,鱼与熊掌不可兼得,最后达成折中方案:链表加红黑树,在适当情况下进行转化。

四、为什么链表转化为红黑树的这个阈值要默认设置为 8 呢?

如果 hashCode 分布良好,也就是哈希算法足够好,计算出来的哈希值散离散程度高,那么很少出现哈希冲突和链表很长的情况,红黑树这种形式也就很少会被用到。在理想情况下,链表长度符合泊松分布,各个长度的命中概率依次递减,当长度为 8 的时候,概率仅为 0.00000006。这是一个小于千万分之一的概率,通常我们的 Map 里面是不会存储这么多的数据的,所以通常情况下,并不会发生从链表向红黑树的转换。请看源码(本文源码均为Java8版本)注释:

* 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

如果在调试过程中发现HashMap中的链表结构经常转换为红黑树进行存储,那么这时候应该注意下哈希函数是不是出现问题了。

五、对比一下Hashtable、HashMap、TreeMap 有什么不同?

Hashtable、HashMap、TreeMap 都是最常见的Map实现,是以键值对的形式存储和操作数据的容器类型。

Hashtable 是早期 Java 类库提供的一个哈希表实现,本身是同步的,不支持 null 键和值,由于同步导致的性能开销,所以已经不建议使用。

HashMap 是目前最常用的哈希表实现,与 HashTable 的主要区别在于: HashMap 不是同步的,支持 null 键和值等。通常情况下,HashMap 进行 put 或者 get 操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选。

TreeMap 则是基于红黑树的一种提供顺序访问的 Map,和 HashMap 不同,它的 get、put、remove 之类操作都是 O(log(n))的时间复杂度,如果有排序的诉求可以选择使用。

六、HashMap为什么是线程不安全的?具体有哪些体现?

put方法中的++modCount

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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;
}

++modCount ++size看似一行代码,但是该操作并不能保证原子性,实际上是分三个步骤执行的,会存在并发问题。modCount这个参数在HashMap中表述HashMap内部结果改变的次数,例如rehash。如果++modCount发生并发问题,会抛出ConcurrentModificationException。

在put方法中,通过比较++size和threshold的大小判断是否进行扩容操作,如果++size发生并发问题,可能使得HashMap在应该扩容的时候未进行扩容,导致put操作的时候元素插入失败或者丢失。

/**
 * 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 默认初始容量为16,如果不停地往 map 中添加新的数据,当元素个数大于负载因子容量大小的时候,会进行扩容,扩至原来的2倍。
newThr = oldThr << 1

在扩容期间,它会新建一个新的空数组,并且将老数组中的元素重新放置到新数组中。那么,在这个填充的过程中,如果有线程获取值,很可能会取到 null 值。

同时put导致数据丢失

比如,有多个线程同时使用 put 方法来添加元素,而且恰好两个 put 的 key 的哈希值是一样的,计算出来的 bucket 位置一样,并且两个线程又同时判断该位置是空的,可以写入,所以这两个线程的两个不同的 value 便会添加到数组的同一个位置,这样最终就只会保留一个数据,丢失一个数据。

死循环造成CPU100%

该问题是多线程同时扩容的时候链表死循环而引起的CPU100%问题。可参考:https://coolshell.cn/articles/9606.html

七、同样是线程安全的,ConcurrentHashMap和Hashtable有什么区别?ConcurrentHashMap在Java7 和Java8又有何不同?

虽然 ConcurrentHashMap 和 Hashtable 它们两个都是线程安全的,但是从原理上分析,Hashtable 实现并发安全的原理是通过 synchronized 关键字实现的。

ConcurrentHashMap在Java7中是通过Segment实现线程安全的,在Java8是通过Node + CAS + synchronized实现的。

Java7中的ConcurrentHashMap最外层是多个Segment,每个Segment的底层数据结构与HashMap类似,仍然是数组加链表组成。

Java8中的ConcurrentHashMap依然是数组+ 链表+ 红黑树的方式实现的,结构和HashMap一致。

ConcurrentHashMap在Java7 和Java8的对比如下:

Java7 Java8
数据结构 Segment + 数组+链表 数组+链表+红黑树
并发原理 Segment Node + CAS + synchronized
并发度 Segment个数,默认16 数组长度
Hash冲突 拉链法 拉链法+红黑树

如果看完有帮忙,能不能帮我点个赞呢?

页面下部广告
分类: