cow容器之CopyOnWriteArrayList
博客专区 > Mr_Qi 的博客 > 博客详情
cow容器之CopyOnWriteArrayList
Mr_Qi 发表于2个月前
cow容器之CopyOnWriteArrayList
  • 发表于 2个月前
  • 阅读 137
  • 收藏 6
  • 点赞 0
  • 评论 0
腾讯云 技术升级10大核心产品年终让利>>>   
java并发容器中有个不得不提的概念,cow(CopyOnWrite) 在jdk1.5之前需要在多线程使用同步集合,一般各位会采用如下方法添加synchronized来实现。synchronize 比如我们对某个集合进行同步 执行 Collections.synchronizedList(list) /** * Returns a synchronized (thread-safe) list backed by the specified * list. In order to guarantee serial access, it is critical that * <strong>all</strong> access to the backing list is accomplished * through the returned list.<p> * * It is imperative that the user manually synchronize on the returned * list when iterating over it: * <pre> * List list = Collections.synchronizedList(new ArrayList()); * ... * synchronized (list) { * Iterator i = list.iterator(); // Must be in synchronized block * while (i.hasNext()) * foo(i.next()); * } * </pre> * Failure to follow this advice may result in non-deterministic behavior. * * <p>The returned list will be serializable if the specified list is * serializable. * * @param list the list to be "wrapped" in a synchronized list. * @return a synchronized view of the specified list. */ public static <T> List<T> synchronizedList(List<T> list) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list)); } 假设为ArrayList那么将会返回SynchronizedRandomAccessList /** * @serial include */ static class SynchronizedCollection<E> implements Collection<E>, Serializable { private static final long serialVersionUID = 3053995032091335093L; final Collection<E> c; // Backing Collection final Object mutex; // Object on which to synchronize SynchronizedCollection(Collection<E> c) { if (c==null) throw new NullPointerException(); this.c = c; mutex = this; } SynchronizedCollection(Collection<E> c, Object mutex) { this.c = c; this.mutex = mutex; } public int size() { synchronized (mutex) {return c.size();} } public boolean isEmpty() { synchronized (mutex) {return c.isEmpty();} } public boolean contains(Object o) { synchronized (mutex) {return c.contains(o);} } public Object[] toArray() { synchronized (mutex) {return c.toArray();} } public <T> T[] toArray(T[] a) { synchronized (mutex) {return c.toArray(a);} } public Iterator<E> iterator() { return c.iterator(); // Must be manually synched by user! } public boolean add(E e) { synchronized (mutex) {return c.add(e);} } public boolean remove(Object o) { synchronized (mutex) {return c.remove(o);} } public boolean containsAll(Collection<?> coll) { synchronized (mutex) {return c.containsAll(coll);} } public boolean addAll(Collection<? extends E> coll) { synchronized (mutex) {return c.addAll(coll);} } public boolean removeAll(Collection<?> coll) { synchronized (mutex) {return c.removeAll(coll);} } public boolean retainAll(Collection<?> coll) { synchronized (mutex) {return c.retainAll(coll);} } public void clear() { synchronized (mutex) {c.clear();} } public String toString() { synchronized (mutex) {return c.toString();} } private void writeObject(ObjectOutputStream s) throws IOException { synchronized (mutex) {s.defaultWriteObject();} } } 核心思路就是所有的操作均加上一把锁,此时自然是thread-safe。(注意iterator并未同步,也就是说做迭代的时候仍然可能有问题。

CopyOnWrite

另一个思路对于所有的读操作不处理,而做写操作的时候将原来的容器复制一份出来操作,当写操作完成后直接把引用更新即可。 /** * A thread-safe variant of {@link java.util.ArrayList} in which all mutative * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by * making a fresh copy of the underlying array. * * <p> This is ordinarily too costly, but may be <em>more</em> efficient * than alternatives when traversal operations vastly outnumber * mutations, and is useful when you cannot or don't want to * synchronize traversals, yet need to preclude interference among * concurrent threads. The "snapshot" style iterator method uses a * reference to the state of the array at the point that the iterator * was created. This array never changes during the lifetime of the * iterator, so interference is impossible and the iterator is * guaranteed not to throw <tt>ConcurrentModificationException</tt>. * The iterator will not reflect additions, removals, or changes to * the list since the iterator was created. Element-changing * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and * <tt>add</tt>) are not supported. These methods throw * <tt>UnsupportedOperationException</tt>. * * <p>All elements are permitted, including <tt>null</tt>. * * <p>Memory consistency effects: As with other concurrent * collections, actions in a thread prior to placing an object into a * {@code CopyOnWriteArrayList} * <a href="http://chbailu.com/my_/package-summary.html#MemoryVisibility"><i>happen-before</i></a> * actions subsequent to the access or removal of that element from * the {@code CopyOnWriteArrayList} in another thread. * * <p>This class is a member of the * <a href="http://chbailu.com/my_/{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @since 1.5 * @author Doug Lea * @param <E> the type of elements held in this collection */ public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8673264195747942595L; /** The lock protecting all mutators */ transient final ReentrantLock lock = new ReentrantLock(); /** The array, accessed only via getArray/setArray. */ private volatile transient Object[] array; /** * Gets the array. Non-private so as to also be accessible * from CopyOnWriteArraySet class. */ final Object[] getArray() { return array; } /** * Sets the array. */ final void setArray(Object[] a) { array = a; } /** * {@inheritDoc} * * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { return get(getArray(), index); } /** * Replaces the element at the specified position in this list with the * specified element. * * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); E oldValue = get(elements, index); if (oldValue != element) { int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; setArray(newElements); } else { // Not quite a no-op; ensures volatile write semantics setArray(elements); } return oldValue; } finally { lock.unlock(); } } /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); } } /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @throws IndexOutOfBoundsException {@inheritDoc} */ 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); else { newElements = new Object[len + 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, newElements, index + 1, numMoved); } newElements[index] = element; setArray(newElements); } finally { lock.unlock(); } } /** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). Returns the element that was removed from the list. * * @throws IndexOutOfBoundsException {@inheritDoc} */ 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)); 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(); } } /** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ public boolean remove(Object o) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; if (len != 0) { // Copy while searching for element to remove // This wins in the normal case of element being present int newlen = len - 1; Object[] newElements = new Object[newlen]; for (int i = 0; i < newlen; ++i) { if (eq(o, elements[i])) { // found one; copy remaining and exit for (int k = i + 1; k < len; ++k) newElements[k-1] = elements[k]; setArray(newElements); return true; } else newElements[i] = elements[i]; } // special handling for last cell if (eq(o, elements[newlen])) { setArray(newElements); return true; } } return false; } finally { lock.unlock(); } } } 可以看出一个存在两个方法 getArray和setArray。当调用任何读操作不需要加锁,而做写操作则需要做lock
  1. 存在内存问题(大集合可能出现fullgc超长)当出现写操作可能出现double size+的内存(同时存在老的集合和新的集合,比较容易引发fullgc)
  2. 不一致性(某个线程调用完了add,其实此时并不能读到该元素,因为此时可能setArray尚未调用),但是达成最终一致性
  3. 读效率高,和ArrayList集合基本持平,适合读多写少的场景(比如缓存!)

    而synchronizedList无论读写的效率均会受到影响,可以当CopyOnWrite容器不合适的需要同步的场景。
共有 人打赏支持
粉丝 191
博文 199
码字总数 207127
×
Mr_Qi
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: