【Java集合】之 ConcurrentHashMap 和 Hashtable

清疚 2023-02-22 10:52 43阅读 0赞

***HashMap 在多线程环境下存在线程安全问题，一般如何处理这种情况？***

一般在多线程的场景，我都会使用好几种不同的方式去代替：

*  使用Collections.synchronizedMap(Map)创建线程安全的map集
 *  Hashtable
 *  ConcurrentHashMap

不过出于线程并发度的原因，我都会舍弃前两者使用最后的ConcurrentHashMap，他的性能和效率明显高于前两者。

***哦，那 Collections.synchronizedMap 是怎么实现线程安全的你有了解过么？***

（卧槽！不按照套路出牌呀，正常不都是问 Hashtable 和 ConcurrentHashMap 么，这次怎么问了这个鬼东西，没事，我的知识储备还是挺足的！）

您这个问题真好！那我就开始装逼了。。。

在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁 mutex：

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable { 
        private static final long serialVersionUID = 1978198479659022715L;
    
        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize
    
        SynchronizedMap(Map<K,V> m) { 
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }
    
        SynchronizedMap(Map<K,V> m, Object mutex) { 
            this.m = m;
            this.mutex = mutex;
        }

我们在调用方法 Collections.synchronizedMap(new HashMap<>(16)) 的时候就需要传入一个 Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。

如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。

创建出synchronizedMap之后，再操作map的时候，就会对方法上锁，从下面可以看到全是锁：

public int size() { 
        synchronized (mutex) { return m.size();}
    }
    public boolean isEmpty() { 
        synchronized (mutex) { return m.isEmpty();}
    }
    public boolean containsKey(Object key) { 
        synchronized (mutex) { return m.containsKey(key);}
    }
    public boolean containsValue(Object value) { 
        synchronized (mutex) { return m.containsValue(value);}
    }
    public V get(Object key) { 
        synchronized (mutex) { return m.get(key);}
    }
    
    public V put(K key, V value) { 
        synchronized (mutex) { return m.put(key, value);}
    }
    public V remove(Object key) { 
        synchronized (mutex) { return m.remove(key);}
    }
    public void putAll(Map<? extends K, ? extends V> map) { 
        synchronized (mutex) { m.putAll(map);}
    }
    public void clear() { 
        synchronized (mutex) { m.clear();}
    }

（卧槽！小伙子，秒啊，其实我早就忘了源码了，就是瞎问一下，没想到还真的回答上来了）

***回答得不错，能跟我聊一下Hashtable么？***

（就等着你问这个问题了）

跟HashTable相比HashMap是线程安全的，适合在多线程的情况下使用，但是效率可不太乐观。

***哦，你能说说他效率低的原因么？***

好的，面试官，我看过它的源码，他在对数据操作的时候都会上锁，所以效率比较低下：

public synchronized V put(K key, V value) { 
        // Make sure the value is not null
        if (value == null) { 
            throw new NullPointerException();
        }
    
    public synchronized V get(Object key) { 
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();

***除了这个你还能说出一些Hashtable 跟HashMap不一样点么？***

（呐呢！？这叫什么问题嘛？这个又是知识盲区呀！）

呃，Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null

***那为啥 Hashtable 是不允许 KEY 和 VALUE 为 null, 而 HashMap 则可以呢？***

（尼玛！还来？）

因为Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

***但是你还是没说为啥 Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null？***

这是因为Hashtable使用的是**安全失败机制（fail-safe）**，fail-safe 允许在遍历的过程中对容器中的数据进行修改，所以这种机制会使你此次读到的数据不一定是最新的数据。

如果你使用 null 值，就会使得其无法判断对应的 key 是不存在还是为空，因为你无法再调用一次contain(key）来对 key 是否存在进行判断，ConcurrentHashMap 同理.

***还有其他不同点吗？***

*  **实现方式不同**：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类
 *  **初始化容量不同**：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75
 *  **扩容机制不同**：当现有容量大于总容量 \* 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1
 *  **迭代器不同**：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的

所以，当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。

***fail-fast是啥？***

（卧槽！你自己不知道么？为啥问我！！！还好我有所准备！）

**快速失败（fail—fast**是Java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

***他的原理是啥？***

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。

集合在被遍历期间如果内容发生变化，就会改变modCount的值。

每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历

这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。

***它的应用场景是什么？***

java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）算是一种安全机制吧。

既然Hashtable 的并发度不够，性能很低，这个情况你是怎么处理的？

这样的场景，我们在开发过程中都是使用ConcurrentHashMap，他的并发的相比前两者好很多。

***哦？那你跟我说说他的数据结构吧，以及为啥他并发度这么高？***

HashMap 底层是基于 `数组 + 链表` 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。

在1.7中的数据结构中，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是**数组加链表**。

Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable { 
    
        private static final long serialVersionUID = 2249069246763182397L;
    
        // 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
        transient volatile HashEntry<K,V>[] table;
    
        transient int count;
            // 记得快速失败（fail—fast）么？
        transient int modCount;
            // 大小
        transient int threshold;
            // 负载因子
        final float loadFactor;
    
    }

HashEntry跟HashMap差不多的，但是不同点是，他使用volatile去修饰了他的数据Value还有下一个节点next。

***volatile的特性是什么？***

*  保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（实现**可见性**）
 *  禁止进行指令重排序。（实现**有序性**）
 *  volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证**原子性**。

***那 ConcurrentHashMap 并发度高的原因是什么？***

ConcurrentHashMap 采用了**分段锁**技术，其中 Segment 继承于 ReentrantLock，不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。

每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment，就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。

具体步骤为，他先定位到Segment，然后再进行put操作，put操作第一步会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 `scanAndLockForPut()` 自旋获取锁：

1.  尝试自旋获取锁
2.  如果重试的次数达到了 `MAX_SCAN_RETRIES` 则改为阻塞锁获取，保证能获取成功

***那它的 get 逻辑呢？***

get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值，ConcurrentHashMap 的 get 方法是非常高效的，**因为整个过程都不需要加锁**。

虽然 1.7 可以支持每个Segment并发访问，但是还是存在一些问题，因为基本上还是数组加链表的方式，我们去查询的时候，还得遍历链表，会导致效率很低，这个跟jdk1.7的HashMap是存在的一样问题，所以他在jdk1.8完全优化了。

***下面我们来聊聊 jdk1.8 的数据结构***

在 1.8 中抛弃了原有的 Segment 分段锁，而采用了 `CAS + synchronized` 来保证并发安全性，跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）。

ConcurrentHashMap 在 1.8 中进行put操作的还是比较复杂的，大致可以分为以下步骤：

1.  根据 key 计算出 hashcode
2.  判断是否需要进行初始化
3.  即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功
4.  如果当前位置的 `hashcode == MOVED == -1`,则需要进行扩容
5.  如果都不满足，则利用 synchronized 锁写入数据
6.  如果数量大于 `TREEIFY_THRESHOLD` 则要转换为红黑树

***CAS是什么？自旋又是什么？***

CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。

CAS 操作的流程为：线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。

再比如我现在要修改数据库的一条数据，修改之前我先拿到他原来的值，然后在SQL里面还会加个判断，原来的值和我手上拿到的他的原来的值是否一样，一样我们就可以去修改了，不一样就证明被别的线程修改了你就return错误就好了。

这是一种乐观策略，认为并发操作并不总会发生。

***CAS 存在的 ABA 问题***

就是说来了一个线程把值改回了B，又来了一个线程把值又改回了A，对于这个时候判断的线程，就发现他的值还是A，所以他就不知道这个值到底有没有被人改过，其实很多场景如果只追求最后结果正确，这是没关系的。

解决ABA问题的方法有很多种，比如：用版本号去保证，在修改前去查询他原来的值的时候再带一个版本号，每次判断就连值和版本号一起判断，判断成功就给版本号加1。

除了版本号之外，还可以用时间戳，查询的时候把时间戳一起查出来，对的上才修改并且更新值的时候一起修改更新时间，这样也能保证。

***jdk1.8升级之后的synchronized***

synchronized之前一直都是重量级的锁，但是后来java官方是对他进行过升级的，他现在采用的是锁升级的方式去做的。

针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用**偏向锁**优先同一线程然后再次获取锁，如果失败，就升级为 **CAS 轻量级锁**，如果失败就会短暂**自旋**，防止线程被系统挂起。最后如果以上都失败就升级为**重量级锁**。