查看“集合与同步集合的比较”的源代码

[[category:Java]]

== 关于集合、同步集合 ==
集合框架中的集合、映射，一般都不是线程安全的，而实现线程安全也有几种方式。

== List ==

List相关的有：
# Vector：线程安全（但不推荐使用）；
# ArrayList、LinkedList：线程不安全；
# SynchronizedList：线程安全，Collections子类实现；
# CopyOnWriteArrayList：线程安全，采用修改copy的方法解决同步问题；

=== 为什么不推荐 Vector（和Stack） ===
*（Stack 继承于 Vector）都使用“synchronized”修饰方法（包括读操作），实现同步；


因为：
# 对于不需要同步的场景：ArrayList和Vector操作没有区别，但没有锁开销；
# 对于需要同步的场景：Vector 对操作方法加锁，却没有对迭代器操作加锁；
#: 通常需要同步一个整个序列的操作，同步单个操作是不安全的。
#: 如：在Vector上进行迭代操作，仍然需要手动加一个锁，以避免其他人同时更改集合，否则将导致“ConcurrentModificationException”；

=== SynchronizedList 与 CopyOnWriteArrayList ===

==== SynchronizedList ==== 
部分源码：
<syntaxhighlight lang="java" line highlight="8,13,16,19,23,26">
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
        ...
        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }
        ...
        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }
        ...
        public ListIterator<E> listIterator() {
            return list.listIterator(); // Must be manually synched by user
        }
        public ListIterator<E> listIterator(int index) {
            return list.listIterator(index); // Must be manually synched by user
        }
</syntaxhighlight>
由源码可以看出：
* 继承于“SynchronizedCollection”，都是'''使用Synchronized锁住了对象的同步变量（对整个对象加锁）'''；
* synchronizedList是将List集合作为参数来创建的synchronizedList集合；
* 采用内部锁（'''synchronized'''）开销大（依赖于Java版本对synchronized优化了）；
* 迭代器（ListIterator）方法却没有加锁处理；


==== CopyOnWriteArrayList ==== 
部分源码：
<syntaxhighlight lang="java" line highlight="7,11,35">
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    /** The array, accessed only via getArray/setArray. */  
    private volatile transient Object[] array;//保证了线程的可见性  
    ...
    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
    ...
    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);  //copy一份比当前数组长度+1的array数组
            else {
                newElements = new Object[len + 1];         //将add的参数赋值
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1, numMoved);
            }
            newElements[index] = element;
            setArray(newElements);           //将原数组指向新的数组
        } finally {
            lock.unlock();
        }
    }

    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;    
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));    //copy一份比当前数组长度-1的array数组
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index, numMoved);
                setArray(newElements);      //将原数组指向新的数组
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

    /**
     * 将原数组指向新的数组
     */
    final void setArray(Object[] a) {
        array = a;
    }
</syntaxhighlight>
由其源码可以看出：
:执行add方法和remove方法的时候，分别创建了一个当前数组长度+1和-1的数组，将数据copy到新数组中，然后执行修改操作。修改完之后调用setArray方法来指向新的数组。
* '''使用“ReentrantLock”对修改操作代码块加锁'''；
* 并且使用volatile修饰数组来保证修改后的可见性；
* 其迭代器（实现了Iterator的内部类COWIterator）方法也实现了同步（依旧采用 ReentrantLock）；


==== 对比 ====
二者主要区别在于实现：
{| class="wikitable"
!  !! SynchronizedList !! CopyOnWriteArrayList
|-
| 对比
| 
# 使用“<span style="color: blue">Synchronized</span>”锁定同步变量（锁定对象）；
# 迭代器方法不同步；
| 
# 使用“<span style="color: blue">ReentrantLock</span>”锁定修改操作代码块；
# 迭代器方法同步；
|}

== Map ==

Map 相关的有：
# HashMap、TreeMap、SortedMap、LinkedHashMap：线程不安全；
# Hashtable：线程安全（但不推荐使用）；
# synchronizedMap：线程安全，Collections子类实现；
# ConcurrentHashMap：线程安全，采用修改copy的方法解决同步问题；

=== 为什么不推荐 HashTable ===
* 使用“synchronized”修饰方法（包括读操作），实现同步；


因为：
# 对于不需要同步的场景：HashMap没有锁开销更适用；
# 对于需要同步的场景：ConcurrentHashMap的锁粒度更低更合适；
# Hashtable继承了被弃用的父类“Dictionary”；
#: Dictionary：除了常规的get，put请求外，还提供了一些遍历的方法，返回的是“Enumeration”类型（Enumeration接口，已经被功能更多更方便的Iterator替换了）


* HashTable的 K，V 都不能是null；

=== synchronizedMap 与 ConcurrentHashMap ===

==== synchronizedMap ====
部分源码：
<syntaxhighlight lang="java">
略（关键点与“SynchronizedList ”类似）
</syntaxhighlight>
* synchronizedMap：（与“SynchronizedList”类似）<s>使用内部锁（Synchronized）修饰每一个方法</s>，锁住的是整个Table对象；
*: 关于'''“锁住整个对象”，是因为“使用Synchronized锁住了对象的同步变量”'''，而非单纯用Synchronized修饰方法：（[[Synchronized关键字的使用]]）
*: <syntaxhighlight lang="java">
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
    final Object mutex;        // Object on which to synchronize
    ...
    public V put(K key, V value) {
        synchronized (mutex) {return m.put(key, value);}
    }
</syntaxhighlight>
* 其对象集的迭代器“Iterator”操作不加锁；
*# synchronizedMap 的“entrySet()”方法返回的是“SynchronizedSet<E>”；
*#“SynchronizedSet”（、“SynchronizedList”）继承自“SynchronizedCollection”，其迭代器“Iterator”操作并不加锁；

==== ConcurrentHashMap ====
部分源码：
<syntaxhighlight lang="java" line highlight="32,45">
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable {
    public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; 
            int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        ...
                        }
                        else if (f instanceof TreeBin) {
                        ...
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
</syntaxhighlight>
*ConcurrentHashMap 实现了更细粒度的加锁：
*# 在JDK1.8之前，采用'''分段锁（“Segment”）'''：每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响（实际就是对桶加锁）；
*# JDK1.8之后，取消了Segment字段，采用'''行锁'''：直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率；
* 读不加锁，写操作加锁；
*: '''volatile'''关键字已经足以保证线程在读取数据时不会读取到脏数据，所以没有加锁的必要；

==== 对比 ====
{| class="wikitable"
! !!  synchronizedMap !! ConcurrentHashMap
|-
| 对比
| 
# '''同步整个对象，只有一把锁'''
# 对整个对象加锁：只允许同一时间内至多一个线程操作整个Map
# 读写操作都需要加锁
# SynchronizedHashMap会返回“Iterator”，当遍历时进行修改会抛出异常“ConcurrentModificationException”
| 
# 不同步整个Map，'''使用多个锁'''实现
# '''只对哈希表的某一个key加锁'''（或分段加锁）
# '''读不加锁，写操作加锁'''
# 在对象层次上不存在锁（即不会阻塞线程）
# ConcurrentHashMap不会抛出“ConcurrentModificationException”，即使一个线程在遍历的同时，另一个线程尝试进行修改
|}