详解HashMap、HashTable、ConcurrentHashMap、HashSet的异同

标签: Java

保留所有版权,请引用而不是转载本文(原文地址 https://yeecode.top/blog/02/ )。

之前的文章《HashMap源码详解》中我们已经结合Java1.8中HashMap的源码对数据结构、数据存取、数据写入、扩容等操作进行了详细的梳理。

而HashMap又是HashSet、HashTable、ConcurrentHashMap这三种数据结构的基础。今天的文章我们就在《HashMap源码详解》的基础上,介绍HashSet、HashTable、ConcurrentHashMap的源码,并比较他们与HashMap的异同。

1 HashTable

HashTable和HashMap的关系最近,可以认为是HashMap的线程安全版本。

我们仍然以Java1.8为例,对HashTable进行分析后发现,其读、写、扩容等操作与HashMap基本一致,但是所有方法都增加了synchronized关键词的修饰,将其变为了同步方法。

1.1 源码分析

我们不再对所有的方法的源码进行一一分析,仅以put方法为例,进行介绍。其供外部公开调用的put方法如下:

public synchronized V put(K key, V value) {
    // 不允许插入null
    if (value == null) {
        throw new NullPointerException();
    }

    // 这里要确认要插入的元素不是已经存在在动态数组中
    Entry<?,?> tab[] = table;
    // 根据hash计算要插入元素的位置
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    // 要插入的元素之前在动态数组中不存在,开始真正插入操作
    addEntry(hash, key, value, index);
    return null;
}

对比《HashMap源码详解》中我们分析的HashMap的源码,我们主要发现了两点不同。

一是在进行真正插入前判断了要插入的元素在HashTable中不存在。在HashMap中其实也进行了对应的操作,只是将其放入了插入操作的子函数中,因此这点差异可以忽略。

二是在计算插入元素key的index时,相关的哈希值和位置计算并没有抽成一个子方法。这主要是:

因此,最好的办法就是每个方法中都写一遍,这是一种用空间换取性能的办法。

好了,我们继续看真正的插入方法:

private void addEntry(int hash, K key, V value, int index) {
    // 类似版本号
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

其中modCount类似于版本号,这是供悲观锁使用的。即如果在遍历过程中发现modCount改变,程序会报错。

count是存储元素的总数。用来作为扩容等操作的依据。

其他地方和HashMap操作一致。

1.2 对比

HashTable和HashMap的区别主要有:

2 ConcurrentHashMap

因为HashTable是基于同步方法实现的线程安全,其效率很低,因此基本很少使用。而HashMap又不支持并发操作。那并发时大家都使用什么呢?就是我们这节所讲的ConcurrentHashMap。

HashTable中的同步方法实际上是对整个HashTable对象加锁,任何操作都会锁住整个对象。这样,当操作变多时,或者HashTable变大时,性能会很差。

而ConcurrentHashMap则采用了另外一种思路,它对整个数组进行了分段。然后对每一个小段进行同步保护,每次加锁只加给一小段数据加锁,那么只要多个操作分布在不同的段上,就可以安全地并发进行。因此提高了性能。

2.1 源码分析

ConcurrentHashMap的源码比较复杂,但是与HashMap的思路相似,再次基础上增加了分段(Segment),默认的分段数是16。也就是最多能够支持16个并发,即16个操作分别操作不同的段不会引发冲突和阻塞。而且,该分段数目一经初始化使用后,不允许在修改。

而每个分段内,则更像是一个HashMap。其初始化、扩容等操作都是针对于每个分段内而言的,每个分段内的数组独立扩容,大小可能各不相同,因此,整体而言ConcurrentHashMap是一组聚集在一起的HashMap。

而在进行插入、读取操作时,都是先找到对应的分段,然后在分段内进行操作。分段内的操作就类似于HashMap了,具体参考《HashMap源码详解》,我们不再重复讲解。

2.2 特点

我们对ConcurrentHashMap的特点进行总结:

3 HashSet

为什么分析HashMap和相关Map却说道了HashSet?因为HashSet是基于HashMap实现的!

首先,我们看到HashMap中先引入了一个HashMap:

private transient HashMap<E,Object> map;

我们在HashSet中存入的值实际上是存入在了HashMap的key位置,而value处就填入下面的对象:

private static final Object PRESENT = new Object();

看一下HashSet的初始化方法:

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

就是创建HashMap。所以其他的操作也都是基于HashMap进行的。我们就不再细讲了。

4 总结

本文我们在之前HashMap的基础上,分析了HashTable、ConcurrentHashMap、HashSet的源码,并总结了他们各自的特点:

本文首发于个人知乎:易哥(https://www.zhihu.com/people/yeecode),欢迎关注。

作者书籍推荐