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...