(转载)多线程环境下的Map一定要同步吗？

原文地址：http://pt.alibaba-inc.com/wp/experience_644/map-multi-threaded-environment-you-must-be-synchronized.html

 

我们都知道在多线程操纵Map时，需要对Map数据结构进行同步，因为通过同步可以保证数据的一致性。但是同步化的同时，程序性能也往往会随之下降。在数据一致性与程序性能之间寻找平衡，是个挺纠结的事儿-_-|||…我们一定要在多线程环境下对Map进行同步吗？

不是的。例如应用场景对Map中的数据无一致性要求时，即可不做同步。当然，这种情况是很少发生的。那在要求Map中数据一致时怎样呢？这个…这个要具体问题具体分析啦！

对Map只有读操作

Map数据结构在初始化后，所有相关线程只做读操作，这时就没有必要进行同步了。因为不牵扯到数据修改，所以此时Map就相当于static的。我们在平时的应用场景中，还是存在一些这种情况的，只是我一时想不起来啦。哈哈。在只读情况下，HashMap与ConcurrentHashMap的性能还是有较大差距的。在10个线程，每个线程对Map数据读100000次的情况下，读取HashMap的耗时约是读取ConcurrentHashMap的耗时的1/2。

所以在对Map数据结构只有读操作的场景中，还是用HashMap更合算一些。

对Map既有读操作又有修改已有value值的操作（但每个线程都固定在Map中的特定Hash值区域）

Map数据结构在初始化后，所有相关线程既有读操作又有修改已有value值的操作，但是每个线程的操作都固定在Map中的特定区域，且相互不重叠。有图有真相：

如上图所示，存在4个线程：Thread1、Thread2、Thread3、Thread4。Thread1操作Map中的A区域，Thread2操作Map中的B区域，Thread3操作Map中的C区域，Thread4操作Map中的D区域。因为A、B、C、D四个区域互不重叠，所以不存在多个线程同时操作同一数据的情况。这种情况该如何处理呢？当然是用HashMap啦。可以把A、B、C、D这4个区域分别认为是线程Thread1、Thread2、Thread3、Thread4的local变量。

对Map既有读操作又有修改已有value值的操作同时还有Map.Entry的增减操作（但每个线程都固定在Map中的特定Hash值区域且Map的threshold不变）

-_-|||…情况比较BT啊。咱们还拿这个图说事儿：

假设Thread2在对B区域的Entry进行增删操作，Thread3在对C区域的Entry进行读写操作，Thread4在对D区域的Entry进行增删操作。那么Thread3会受到Thread2与Thread4的影响吗？在HashMap的情况下，只要threshold不变，就不会受到影响。也就是说，在这种场景下使用HashMap即可，无需使用ConcurrentHashMap。我们来根据HashMap的源码说明一下原因。

/**

* The table, resized as necessary. Length MUST Always be a power of two.

*/

Transient Entry[] table;

HashMap是使用Entry[]类型的table属性来存储key-value的。Entry类有4个属性，分别是：final K key、V value、Entry<K, V> next、final int hash。其中Entry<K, V> next的值在HashMap中一般为null，只有在key出现hash冲突时才将新Entry的next属性指向原有的Entry，从而形成一个单项链表。而table[i]始终指向同一hash值的最新Entry。这是因为给HashMap增加key-value的方法是public V put(K key, V value)与private V putForNullKey(V value)，而这两个方法在添加新Entry（而不是修改已有Entry）时都要调用void addEntry(int hash, K key, V value, int bucketIndex)方法。该方法源码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];

    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

    if (size++ >= threshold)

        resize(2 * table.length);

}

我们可以看到第三行table[bucketIndex] = new Entry<K,V>(hash, key, value, e)。其中new一个Entry<K, V>时，其构造方法的第四个参数是e，即新Entry的next属性值。但是从第二行Entry<K,V> e = table[bucketIndex]我们知道e为原有的Entry，即table[bucketIndex]。而方法public V put(K key, V value)与private V putForNullKey(V value)在对HashMap中已有table[i]赋值时，均不改变其next属性。所以table[i]的next属性值在HashMap中要么为null，要么为相同hash值但不同key值的Entry。这就说明HashMap中table数组的各个Entry元素是无联系的。

不改变threshold是因为当threshold改变时牵扯到table的扩容，而table的扩容又牵扯到原有Entry[]的赋值等等。这些过程是非同步的，在多线程时容易出现问题。具体代码可以看void resize(int newCapacity)方法，这里我就不贴啦-_-|||…正是因为table数组中各个Entry的无关联性以及threshold的不变，使得在这种场景下可以使用非同步的HashMap。

那我们如何判断threshold是否会在运行过程中发生变化呢？这个问题问得很好-_-|||…这个就要看大家对应用场景的认识程度以及个人经验了。如果这两方面都不是很充分怎么办呢？哈哈，那就看人品啦。

另外HashMap有一个子类LinkedHashMap。这个LinkedHashMap是否可在这种场景使用呢？不行，因为LinkedHashMap的Entry有Entry<K, V>类型的两个属性：before与after。也就是说LinkedHashMap中各个Entry是相关联的。

对Map既有读操作又有修改已有value值的操作且每个线程都不固定在Map中的特定区域

Map数据结构在初始化后，所有相关线程既有读操作又有修改已有value值的操作，而且每个线程的操作都不固定在Map中的特定区域，即可能相互重叠。这时为了保证数据一致性，必须采用同步。那么我们是否一定要用ConcurrentHashMap来实现呢？不用的-_-|||…我们知道对同步进行优化的最有效手段就是不同步。哈哈。但是如果非要同步的话，那我们应该尽可能的缩小同步范围。如下图所示：

Thread1在对A区域的数据进行读写，Thread2与Thread3同时在对B区域的数据进行读写。如果我们使用ConcurrentHashMap，则Thread1、Thread2、Thread3需要顺序执行。但是我们发现，其实Thread1的执行，并不影响Thread2与Thread3的执行，所以Thread1完全可以和Thread2或Thread3并行执行。要实现这点，就需要把同步的范围从Map缩小的Value。为了演示，我分别对ConcurrentHashMap<Integer, Integer>与HashMap<Integer, MyInteger>进行测试。MyInteger的源码如下：

public class MyInteger {

    public MyInteger(int i) {

        super();

        this.i = i;

    }

    public synchronized void setI(int i) {

        this.i = i;

    }

    public synchronized int getI() {

        return i;

    }

    private int i;

}

在10个线程，每个线程对Map数据读写100000次的情况下，读写HashMap<Integer, MyInteger>的耗时约是读写ConcurrentHashMap<Integer, Integer>的耗时的1/2。

对Map既有读操作又有写操作同时还有Map.Entry的增减操作且每个线程都不固定在Map中的特定区域

那…那就java.util.concurrent.ConcurrentHashMap<K,V>吧-_-|||…