关于后端:详解HashMapHashTableConcurrentHashMapHashSet的异同

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 的源码，咱们次要发现了两点不同。
《2020 最新 Java 根底精讲视频教程和学习路线！》

一是在进行真正插入前判断了要插入的元素在 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://juejin.cn/post/690131…