如何线程安全的使用HashMap

为什么HashMap是线程不安全的？

1、讲讲一下HashMap的存储结构

transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

可以看到HashMap内部存储使用了一个node数组（默认大小是16），而Node类包含一个Node类型的next变量，指向下一个node相当于一个链表，所有根据Hash值计算的key一样的的数据会存储到一个bucket(桶)中(一个链表中)，如下图

注意：java8中如果hash值相同的key的数量大于容量（默认8）时，会使用平衡树代替链表。

2、讲讲HashMap的扩容机制

HashMap内部的node数组默认是16，假设有100万个元素，每个桶（node）中平均存储62500个元素，那么Map的remove,get,put等方法的效率也会下降，为了解决这个问题，hashMap提供了自动扩容机制，当bucket个数超过容量（默认16）*loadfactor(默认0.75)之后，会把数组大小扩展为2*16=32个，并重新计算每个元素在在新数组中的位置。

图来源http://coding-geek.com/how-does-a-hashmap-work-in-java/

从图中可以看出，在已知key的情况下，没扩容之前获取EntryE需要遍历5次，扩容之后获取EntryE需要2次。

3、讲讲为什么线程不安全

两个方法，两个并发线程同时put元素，如果根据key值计算的hash值一样，那么put的数据会被覆盖；如果两个线程同时检测到当前数组大小大于容量*loadactory之后，会同时扩容并重新计算元素的新位置，并更新数组，这样最后就会出现有一个线程的数据会丢失。HashMap在线程并发时会容易死循环，死循环不是发生在put时而发生在扩容时。

4、讲讲如何安全的使用HashMap

//Hashtable
Map<String, String> hashtable = new Hashtable<>();
//synchronizedMap
Map<String, String> synchronizedHashMap = Collections.synchronizedMap(new HashMap<String, String>());
//ConcurrentHashMap
Map<String, String> concurrentHashMap = new ConcurrentHashMap<>();

HashTable 中使用synchronized来保证线程安全，显然效率很低，不能

public synchronized V get(Object key) {
    // 省略实现
}
public synchronized V put(K key, V value) {
    // 省略实现
}

ConcurrentHashMap（简称CHM）

CHM是在JDK1.5之后引入的，用来替代HashTable，是concurrent包的重要成员，在JDK1.5之前如果要保证线程安全的使用map，只能选择HashTable或者SynchronizedMap，但是在操作map时，HashTable和SynchronizedMap会锁住整个map，引入了ConcurrentHashMap之后，在操作map时，只锁住了部分，允许多线程的并发读操作，同时通过同步锁保证了，数据的完整性。

CHM允许多线程的读操作，同时根据默认并发级别（可以在构造函数中传入，默认16）个数，允许16个线程同时进入操作map，而SynchronizedMap和HashTable只允许一个线程进入操作map，但是如果是更新操作，比如remove，put，clear可以并发执行，所以不能保证最后返回的结果是最新的。如果只有很少的线程操作map，建议将并发级别设置少一些。

有时候我们在往map中put元素时，我们需要预判断一下是否存在该元素，再执行put操作，同时为了并发操作，我们可能会加锁避免并发get和put。如下：

synchronized(map){
    if (map.get(key) == null){
    return map.put(key, value);
    } else{
    return map.get(key);
    }
    }

但是我们可以使用chm的putIfAbsent(key,value)方法可以保证数据的原子性，以及避免线程的竞争。

什么时候使用CHM，建议读的线程数量大于写的线程数量时使用，如果写的数量大于读的数量，比如达到了并发级别，会锁住整个map，读操作要等写操作完成才能执行，所以CHM适用于做缓存，在容器启动时可以被多个线程请求访问。

SynchronizedMap

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;
    }

    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);}
    }