详解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的区别主要有：

HashMap是非线程安全的，HashTable是线程安全的。HashTable实现线程安全的办法是在方法上加同步锁，因此性能更差。
HashMap允许插入null值，而HashTable不允许。插入null时，HashTable会抛出NullPointerException。
HashMap默认初始化数组大小是16，HashTable的默认初始化数组大小是11。HashMap扩容容量变为2n，HashTable扩容时容量变为2n+1，这样元素分布更为均匀。

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的特点进行总结：

是线程安全的。并且内部采用分段加锁的策略，其效率比HashTable要高。
和HashTable一样，不允许存入null值。

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的源码，并总结了他们各自的特点：

HashTable是线程安全的。原理是在方法上加同步锁，因此性能更差。
ConcurrentHashMap是线程安全的。并且内部采用分段加锁的策略，其效率比HashTable要高。
HashSet是基于HashMap实现的。

可以访问个人知乎阅读更多文章：易哥（https://www.zhihu.com/people/yeecode），欢迎关注。

易哥

高级软件架构师