• CopyOnWriteArrayList的特点与用法
• CopyOnWriteArrayList的数据结构
• CopyOnWriteArrayList的常用方法及实现

CopyOnWriteArrayList的特点与用法

CopyOnWriteArrayList的数据结构和用法与ArrayList基本都相同,区别主要在于CopyOnWriteArrayList在添加和删除元素等修改集合状态的操作时，都会重新复制一个新的数组，以保证多线程下的安全性。因为每次修改数据结点都要复制整个对象数组，会比较耗时间，所以CopyOnWriteArrayList适合读多写少情况下的多线程场景，如缓存之类的。

CopyOnWriteArrayList的数据结构

CopyOnWriteArrayList的数据结构与ArrayList的基本一样，只是它不再有扩容之类的操作，因为每次修改都是一个新的数组。。。

CopyOnWriteArrayList的常用方法及实现

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
}

从CopyOnWriteArrayList的类结构就可以看出，它的方法签名与ArrayList基本一致，这里就不再重复了。下面讲讲它方法的特殊实现。

1. 构造方法
   CopyOnWriteArrayList的默认构造方法会创建一个长度为0的数组来储存数据，而不是像ArrayList那样创建一个长度为10的数组

   /**Sets the array. */    
   final void setArray(Object[] a) {
     array = a;
   }
   
   /**
   * Creates an empty list.
   */
   public CopyOnWriteArrayList() {
       setArray(new Object[0]);
   }
   

2. 添加方法

   /**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return {@code true} (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();
       }
   }
   

3. 修改方法

   方法在进入和退出时有加锁、释放锁

   /**
    * 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();
       }
   }
   

4. 删除方法

   /**
    * 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
    * {@code i} such that
    * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
    * (if such an element exists).  Returns {@code true} 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 {@code true} if this list contained the specified element
    */
   public boolean remove(Object o) {
       Object[] snapshot = getArray();
       int index = indexOf(o, snapshot, 0, snapshot.length);
       return (index < 0) ? false : remove(o, snapshot, index);
   }
   
   /**
    * A version of remove(Object) using the strong hint that given
    * recent snapshot contains o at the given index.
    */
   private boolean remove(Object o, Object[] snapshot, int index) {
       final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           Object[] current = getArray();
           int len = current.length;
           if (snapshot != current) findIndex: {
               int prefix = Math.min(index, len);
               for (int i = 0; i < prefix; i++) {
                   if (current[i] != snapshot[i] && eq(o, current[i])) {
                       index = i;
                       break findIndex;
                   }
               }
               if (index >= len)
                   return false;
               if (current[index] == o)
                   break findIndex;
               index = indexOf(o, current, index, len);
               if (index < 0)
                   return false;
           }
           Object[] newElements = new Object[len - 1];
           System.arraycopy(current, 0, newElements, 0, index);
           System.arraycopy(current, index + 1,
                            newElements, index,
                            len - index - 1);
           setArray(newElements);
           return true;
       } finally {
           lock.unlock();
       }
   }
   
   /**
    * Removes from this list all of the elements whose index is between
    * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
    * Shifts any succeeding elements to the left (reduces their index).
    * This call shortens the list by {@code (toIndex - fromIndex)} elements.
    * (If {@code toIndex==fromIndex}, this operation has no effect.)
    *
    * @param fromIndex index of first element to be removed
    * @param toIndex index after last element to be removed
    * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
    *         ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
    */
   void removeRange(int fromIndex, int toIndex) {
       final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           Object[] elements = getArray();
           int len = elements.length;
   
           if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
               throw new IndexOutOfBoundsException();
           int newlen = len - (toIndex - fromIndex);
           int numMoved = len - toIndex;
           if (numMoved == 0)
               setArray(Arrays.copyOf(elements, newlen));
           else {
               Object[] newElements = new Object[newlen];
               System.arraycopy(elements, 0, newElements, 0, fromIndex);
               System.arraycopy(elements, toIndex, newElements,
                                fromIndex, numMoved);
               setArray(newElements);
           }
       } finally {
           lock.unlock();
       }
   }
   

5. 遍历

   遍历时，直接使用内部的数组，这样可以避开多线程时的问题,类似的还有indexOf

   public void forEach(Consumer<? super E> action) {
       if (action == null) throw new NullPointerException();
       Object[] elements = getArray();
       int len = elements.length;
       for (int i = 0; i < len; ++i) {
           @SuppressWarnings("unchecked") E e = (E) elements[i];
           action.accept(e);
       }
   }
   
   public int indexOf(E e, int index) {
       Object[] elements = getArray();
       return indexOf(e, elements, index, elements.length);
   }
   

• LinkedHashMap的特点
• LinkedHashMap的数据结构
• LinkedHashMap的常用方法及实现

LinkedHashMap的特点

• LinkedHashMap继承于HashMap，拥有HashMap的所有特点

• LinkedHashMap可以保证元素的顺序，支持插入或者访问的顺序，这是通过在构造时提供accessOrder参数来进行控制

  /**
   * Constructs an empty <tt>LinkedHashMap</tt> instance with the
   * specified initial capacity, load factor and ordering mode.
   *
   * @param  initialCapacity the initial capacity
   * @param  loadFactor      the load factor
   * @param  accessOrder     the ordering mode - <tt>true</tt> for
   *         access-order, <tt>false</tt> for insertion-order
   * @throws IllegalArgumentException if the initial capacity is negative
   *         or the load factor is nonpositive
   */
  public LinkedHashMap(int initialCapacity,
                       float loadFactor,
                       boolean accessOrder) {
      super(initialCapacity, loadFactor);
      this.accessOrder = accessOrder;
  }
  

• 因为LinkedHashMap支持访问顺序，所以它可以很方便地用来实现LRU算法

LinkedHashMap的数据结构

LinkedHashMap除了使用HashMap的数据-链表来储存数据之外，还提供一个单独的链接来储存节点的顺序。同时，通过参数accessOrder来决定是使用访问顺序还是插入顺序

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

private static final long serialVersionUID = 3801124242820219131L;

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

LinkedHashMap的常用方法及实现

HashMap在实现时就已经为子类的拓展留下了很多的接口，如afterNodeAccess、afterNodeInsertion等等。LinkedHashMap通过重写这些方法，来保存元素的顺序

1. putVal

   HashMap:

   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);
       else {
           Node<K,V> e; K k;
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               e = p;
           else if (p instanceof TreeNode)
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           else {
               for (int binCount = 0; ; ++binCount) {
                   if ((e = p.next) == null) {
                       p.next = newNode(hash, key, value, null);
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           treeifyBin(tab, hash);
                       break;
                   }
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       break;
                   p = e;
               }
           }
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               afterNodeAccess(e);
               return oldValue;
           }
       }
       ++modCount;
       if (++size > threshold)
           resize();
       afterNodeInsertion(evict);
       return null;
   }
   

   LinkedHashmap:

   void afterNodeInsertion(boolean evict) { // possibly remove eldest
       LinkedHashMap.Entry<K,V> first;
       if (evict && (first = head) != null && removeEldestEntry(first)) {
           K key = first.key;
           removeNode(hash(key), key, null, false, true);
       }
   }
   

2. get

   public V get(Object key) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return null;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }   
   
   void afterNodeAccess(Node<K,V> e) { // move node to last
       LinkedHashMap.Entry<K,V> last;
       if (accessOrder && (last = tail) != e) {
           LinkedHashMap.Entry<K,V> p =
               (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
           p.after = null;
           if (b == null)
               head = a;
           else
               b.after = a;
           if (a != null)
               a.before = b;
           else
               last = b;
           if (last == null)
               head = p;
           else {
               p.before = last;
               last.after = p;
           }
           tail = p;
           ++modCount;
       }
   }
   

3. remove

HashMap

/**
 * Implements Map.remove and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

LinkedHashMap:

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}