public interface Lock {
    // 获得锁资源
    void lock();
    // 尝试获得锁，如果当前线程被调用了interrupted则中断，并抛出异常，否则就获得锁
    void lockInterruptibly() throws InterruptedException;
    // 判断能否获得锁，如果能获得，则获得锁，并返回true(此时已经获得了锁);否则返回false
    boolean tryLock();
    // 保持给定的等待时间，如果期间能拿到锁，则获得锁，同样如果期间被中断，则抛异常
    boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
    // 释放锁
    void unlock();
    // 返回与此Lock对象绑定Condition实例
    Condition newCondition();
}

public interface Condition {
    // 让当前线程等待，直到被通知或者被中断
    void await() throws InterruptedException;
    // 与前者的区别是，当等待过程中被中断时，仍会继续等待，直到被唤醒，才会设置中断状态
    void awaitUninterruptibly();
    // 让当前线程等待，直到它被告知或中断，或指定的等待时间已经过。
    boolean await(long time, TimeUnit unit) throws InterruptedException;
    // 与上面的类似，让当前线程等待，不过时间单位是纳秒
    long awaitNanos(long nanosTimeout) throws InterruptedException;
    // 让当前线程等待到确切的指定时间，而不是时长
    boolean awaitUntil(Date deadline) throws InterruptedException;
    // 唤醒一个等待当前condition的线程，有多个则随机选一个
    void signal();
    // 唤醒所有等待当前condition的线程
    void signalAll();
}

public interface ReadWriteLock {
    // 写锁
    Lock writeLock();
    // 读锁
    Lock readLock();
}

class Test
{
    // 锁定当前对象
    public void method1() {
        synchronized(this) 
        {
            // todo
        }
    }
    
    //锁定指定对象obj
    public void method2(Object obj) {
        synchronized(obj)
        {
            // todo
        }
    }
    
    private byte[] lock = new byte[0];  // 特殊的instance变量
    //当没有明确的对象作为锁，只是想让一段代码同步时，可以创建一个特殊的对象来充当锁
    //说明：零长度的byte数组对象创建起来将比任何对象都经济――查看编译后的字节码：生成零长度的byte[]对象只需3条操作码，而Object lock = new Object()则需要7行操作码
    public void method3()
    {
       synchronized(lock) {
          // todo 同步代码块
       }
    }
}

public synchronized void method()
{
   // todo
}

//等同于
public void method()
{
   synchronized(this) {
      // todo
   }
}

public synchronized static void method() {
   // todo
}

pulbic class Something {
    public synchronized void isSyncA(){}
    public synchronized void isSyncB(){}
    public static synchronized void cSyncA(){}
    public static synchronized void cSyncB(){}
}

class ClassName {
   public void method() {
      synchronized(ClassName.class) {
         // todo
      }
   }
}

public enum State {
    NEW,
    RUNNABLE,
    BLOCKED,
    WAITING,
    TIMED_WAITING,
    TERMINATED;
}

public static native void yield();

public static native void sleep(long millis) throws InterruptedException;

//源码
public final synchronized void join(long millis)
throws InterruptedException {
    long base = System.currentTimeMillis();
    long now = 0;

    if (millis < 0) {
        throw new IllegalArgumentException("timeout value is negative");
    }

    if (millis == 0) {	
        while (isAlive()) {	//millis为0，进入死循环
            wait(0);
        }
    } else {
        while (isAlive()) {//millis 控制线程wait时间
            long delay = millis - now;
            if (delay <= 0) {
                break;
            }
            wait(delay);
            now = System.currentTimeMillis() - base;
        }
    }
}

// 主线程
public class Father extends Thread {
    public void run() {
        Son s = new Son();
        s.start();
        s.join();	//实际上是调用wait()方法等待，而wait()方法的对象是当前线程Father
        ...
    }
}
// 子线程
public class Son extends Thread {
    public void run() {
        ...
    }
}

public void interrupt() {
    if (this != Thread.currentThread())
        checkAccess();	//验证是否可进入

    synchronized (blockerLock) {
        Interruptible b = blocker;
        if (b != null) {
            interrupt0();           // 仅仅设置中断标志
            b.interrupt(this);
            return;
        }
    }
    interrupt0();
}

@Override
public void run() {
    try {
        // 1. isInterrupted()保证，只要中断标记为true就终止线程。
        while (!isInterrupted()) {	//3. 可通过额外添加标志 volatile flag
            // 执行任务...
        }
    } catch (InterruptedException ie) {  
        // 2. InterruptedException异常保证，当InterruptedException异常产生时，线程被终止。
    }
}

public class Thread implements Runnable

public interface Runnable {
    public abstract void run();
}

public interface Callable<V> {
    V call() throws Exception;
}

public interface Queue<E> extends Collection<E>

public interface Deque<E> extends Queue<E>

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

//未指定容量时，默认为16
public ArrayDeque() {
    elements = new Object[16];
}
//指定初始容量
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
//指定初始值
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
//指定容量小于8时，返回8
//否则，返回initialCapacity=2^n，2^n越界时，则取2^30
//容量必须为2^n，否则指针移动	head &（elements.length - 1）将出现空位
private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}

//实际存放元素的数组
 transient Object[] elements; 
 //头指针
 transient int head;
 //尾指针
 transient int tail;
 //默认最小容量
 private static final int MIN_INITIAL_CAPACITY = 8;

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;	//数组长度翻倍
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);	//复制head指针右边的数据
    System.arraycopy(elements, 0, a, r, p);	//复制head指针左边的数据
    elements = a;
    head = 0;	//重新初始化head,tail
    tail = n;
}

//在头部插入数据
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;	//head指针从右向左移
    if (head == tail)
        doubleCapacity();
}

//在尾部插入数据
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)	//head指针从左向右移动
        doubleCapacity();
}

//删除头部数据
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

//删除尾部数据
public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

public Iterator<E> iterator() {
    return new DeqIterator();
}

private class DeqIterator implements Iterator<E> {
    //游标，从head开始遍历
    private int cursor = head;
	//记录tail指针，判断是否结构改变
    private int fence = tail;
	//next()返回的索引
    private int lastRet = -1;

    public boolean hasNext() {
        return cursor != fence;
    }

    public E next() {
        if (cursor == fence)
            throw new NoSuchElementException();
        @SuppressWarnings("unchecked")
        E result = (E) elements[cursor];
        // This check doesn't catch all possible comodifications,
        // but does catch the ones that corrupt traversal
        if (tail != fence || result == null)
            throw new ConcurrentModificationException();
        lastRet = cursor;
        cursor = (cursor + 1) & (elements.length - 1);
        return result;
    }
}

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

//queue[n] 子节点为 queue[2*n+1] ， queue[2*(n+1)]
//queue[n] <= queue[2*n+1]， queue[n] <= queue[2*(n+1)]
transient Object[] queue;
//实际元素个数
private int size = 0;
//比较器，自然序为null
private final Comparator<? super E> comparator;
//fast-fail机制
transient int modCount = 0;

//构建堆
private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--) //从数组 （size >>> 1) - 1 开始	
        siftDown(i, (E) queue[i]);
}

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);	//比较器的区别
    else
        siftDownComparable(k, x);
}

//从父节点向下调整堆
//是一个递归操作，一旦发生了父节点和子节点的交换，交换下去的新的子节点可能和该子节点的子节点不满足堆特性，需要调整
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;	//取左节点，左节点一定存在
        Object c = queue[child];	
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)	
            c = queue[child = right];	//取左右节点的最小值
        if (comparator.compare(x, (E) c) <= 0)	//比较父节点和子节点最小值
            break;
        queue[k] = c;	        // 将k位置赋值成较小值
        k = child;		//指定k为child，进入下一次循环。因为出现了交换，为了保证交换下去的节点也能满足小顶堆，需要继续调整堆
    }
    queue[k] = x;	//重新赋值k
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);	//进行扩容  Double size if small; else grow by 50%
    //newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
    size = i + 1;
    if (i == 0)
        queue[0] = e;	//首元素
    else
        siftUp(i, e);	//向上
    return true;
}

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
//递归和父节点比较，最小元素上浮
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null; //最后的元素丢到堆顶
    if (s != 0)
        siftDown(0, x); //调整堆顶元素
    return result;
}

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

// 默认构造函数
public HashSet() 

// 带集合的构造函数
public HashSet(Collection<? extends E> c) {
    //hashMap 负载因子0.75，c.size()/.75f) + 1 计算出来的为总的空间大小，不需要扩容
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

// 指定HashSet初始容量和加载因子的构造函数
public HashSet(int initialCapacity, float loadFactor) 

// 指定HashSet初始容量的构造函数
public HashSet(int initialCapacity) 

// 指定HashSet初始容量和加载因子的构造函数,dummy没有任何作用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);		//LinkedHashSet使用
}

Set s = Collections.synchronizedSet(new HashSet(...));

private transient HashMap<E,Object> map;	//基于map实现
// PRESENT是向map中插入key-value对应的value
// 因为HashSet中只需要用到key，而HashMap是key-value键值对；
// 所以，向map中添加键值对时，键值对的值固定是PRESENT
private static final Object PRESENT = new Object();

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

//value为PRESENT对象
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

//克隆一个HashSet，并返回Object对象
public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

// java.io.Serializable的写入函数
// 将HashSet的“总的容量，加载因子，实际容量，所有的元素”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out HashMap capacity and load factor
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());

    // Write out size
    s.writeInt(map.size());

    // Write out all elements in the proper order.
    for (E e : map.keySet())
        s.writeObject(e);
}

// java.io.Serializable的读取函数
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read capacity and verify non-negative.
    int capacity = s.readInt();
    if (capacity < 0) {
        throw new InvalidObjectException("Illegal capacity: " + capacity);
    }

    // Read load factor and verify positive and non NaN.
    float loadFactor = s.readFloat();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " + loadFactor);
    }

    // Read size and verify non-negative.
    int size = s.readInt();
    if (size < 0) {
        throw new InvalidObjectException("Illegal size: " + size);
    }

    // Set the capacity according to the size and load factor ensuring that
    // the HashMap is at least 25% full but clamping to maximum capacity.
    capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                              HashMap.MAXIMUM_CAPACITY);

    // Create backing HashMap
    map = (((HashSet<?>)this) instanceof LinkedHashSet ?
           new LinkedHashMap<E,Object>(capacity, loadFactor) :
           new HashMap<E,Object>(capacity, loadFactor));

    // Read in all elements in the proper order.
    for (int i=0; i<size; i++) {
        @SuppressWarnings("unchecked")
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

//将TreeMap 赋值给NavigableMap
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

//不带参数构造函数
public TreeSet() {
    this(new TreeMap<E,Object>());
}

//带比较器构造函数
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
//创建TreeSet，并将集合c中的全部元素都添加到TreeSet中
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

private transient NavigableMap<E,Object> m; 	//NavigableMap对象，基于TreeMap实现（传入new TreeMap<E,Object>()）
private static final Object PRESENT = new Object();	//value所存值

//将集合中的元素赋值给TreeSet
public  boolean addAll(Collection<? extends E> c) {
    // Use linear-time version if applicable
    if (m.size()==0 && c.size() > 0 &&
        c instanceof SortedSet &&
        m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        Comparator<?> cc = set.comparator();
        Comparator<? super E> mc = map.comparator();
        if (cc==mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT);		// 红黑树添加SortedSet节点
            return true;
        }
    }
    return super.addAll(c);
}

//返回TreeSet的顺序排列的迭代器
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

//返回TreeSet的逆序排列的迭代器
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

//添加e到TreeSet
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

//删除TreeSet对象
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

//java.io.Serializable的写入函数
//将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden stuff
    s.defaultWriteObject();

    // Write out Comparator
    s.writeObject(m.comparator());

    // Write out size
    s.writeInt(m.size());

    // Write out all elements in the proper order.
    for (E e : m.keySet())
        s.writeObject(e);
}

//java.io.Serializable的读取函数：根据写入方式读出
//先将TreeSet的“比较器、容量、所有的元素值”依次读出
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden stuff
    s.defaultReadObject();

    // Read in Comparator
    @SuppressWarnings("unchecked")
    Comparator<? super E> c = (Comparator<? super E>) s.readObject();

    // Create backing TreeMap
    TreeMap<E,Object> tm = new TreeMap<>(c);
    m = tm;

    // Read in size
    int size = s.readInt();

    tm.readTreeSet(size, s, PRESENT);
}

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

protected Object[] elementData;		//动态数组，增长由ensureCapacity()控制
protected int elementCount;			//数组实际大小
protected int capacityIncrement;	//动态数组的增长系数，创建时候若指定capacityIncrement，则每次扩容时候增加大小为capacityIncrement

public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //设置了capacityIncrement，则增长capacityIncrement长度，否则增长一倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);	//复制到新数组中
}

public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    int j = elementCount - index - 1;
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

public synchronized boolean addAll(int index, Collection<? extends E> c) {
    modCount++;
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityHelper(elementCount + numNew);	

    int numMoved = elementCount - index;	//移动数据长度
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount += numNew;
    return numNew != 0;
}

//返回Vector中全部元素对应的Enumeration, Enumeration迭代不会出现线程安全问题
public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;

        public boolean hasMoreElements() {
            return count < elementCount;
        }

        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

public class Stack<E> extends Vector<E>

//将元素存入栈顶
public E push(E item) {
    addElement(item);	//在Vector中实现
    return item;
}

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

//获取栈顶元素，删除
public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

//获取栈顶元素，不删除
public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

transient Object[] elementData;
private int size;

// jdk1.8
int newCapacity = oldCapacity + (oldCapacity >> 1); // 默认1.5倍
    
// jdk1.6
int newCapacity = (oldCapacity * 3)/2 + 1;

public boolean add(E e) { // 添加元素
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {	//是否为空数组
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;	//扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);	// 新容量小于参数指定容量，修改新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)		// 新容量大于最大容量
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);	//拷贝
}

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;	// 需要移动的元素的个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);		//把指定下标到数组末尾的元素向前移动一个单位
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

public Object clone() {
    try {
    ArrayList<?> v = (ArrayList<?>) super.clone();
    v.elementData = Arrays.copyOf(elementData, size);
    v.modCount = 0;
    return v;
    } catch (CloneNotSupportedException e) {
    // this shouldn't happen, since we are Cloneable
    throw new InternalError(e);
    }
}

//java.io.Serializable的写入函数
// 将ArrayList的“容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // 写入“数组的容量”
    s.writeInt(elementData.length);

    // 写入“数组的每一个元素”
    for (int i=0; i<size; i++)
    s.writeObject(elementData[i]);

    if (modCount != expectedModCount) {
    throw new ConcurrentModificationException();
    }
}

// java.io.Serializable的读取函数：根据写入方式读出
// 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // 从输入流中读取ArrayList的“容量”
    int arrayLength = s.readInt();
    Object[] a = elementData = new Object[arrayLength];

    // 从输入流中将“所有的元素值”读出
    for (int i=0; i<size; i++)
    	a[i] = s.readObject();
}

private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    // 新建COWIterator时，将集合中的元素保存到一个新的拷贝数组中。
    // 这样，当原始集合的数据改变，拷贝数据中的值也不会变化。
    snapshot = elements;
}

public class LinkedList<E>
	extends AbstractSequentialList<E>
	implements List<E>, Deque<E>, Cloneable, java.io.Serializable

// jdk1.8
transient int size = 0;
transient Node<E> first;  // Pointer to first node
transient Node<E> last;  // Pointer to last node

class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
	
	Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

// jdk 1.6
// 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
private transient Entry<E> header = new Entry<E>(null, null, null);

private static class Entry<E> {
	// 当前节点所包含的值
	E element;
	// 下一个节点
	Entry<E> next;
	// 上一个节点
	Entry<E> previous;
}

public boolean add(E e) {
    // 添加到末尾
    linkLast(e);
    return true;
}
  
void linkLast(E e) {
    // 保存尾结点，l为final类型，不可更改
    final Node<E> l = last;
    // 新生成结点的前驱为l,后继为null
    final Node<E> newNode = new Node<>(l, e, null);
    // 重新赋值尾结点
    last = newNode;    
    if (l == null) // 尾结点为空
        first = newNode; // 赋值头结点
    else // 尾结点不为空
        l.next = newNode; // 尾结点的后继为新生成的结点
    // 大小加1    
    size++;
    // 结构性修改加1
    modCount++;
}

// 添加一个集合
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查插入的的位置是否合法
    checkPositionIndex(index);
    // 将集合转化为数组
    Object[] a = c.toArray();
    // 保存集合大小
    int numNew = a.length;
    if (numNew == 0) // 集合为空，直接返回
    	return false;    
    Node<E> pred, succ; // 前驱，后继
    if (index == size) { // 如果插入位置为链表末尾，则后继为null，前驱为尾结点
        succ = null;
        pred = last;
    } else { // 插入位置为其他某个位置
        succ = node(index); // 寻找到该结点
        pred = succ.prev; // 保存该结点的前驱
    }

    for (Object o : a) { // 遍历数组
        @SuppressWarnings("unchecked") E e = (E) o; // 向下转型
        // 生成新结点
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) // 表示在第一个元素之前插入(索引为0的结点)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) { // 表示在最后一个元素之后插入
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 修改实际元素个数
    size += numNew;
    // 结构性修改加1
    modCount++;
    return true;
}

Node<E> node(int index) {
    // 判断插入的位置在链表前半段或者是后半段
    if (index < (size >> 1)) { // 插入位置在前半段
        Node<E> x = first; 
        for (int i = 0; i < index; i++) // 从头结点开始正向遍历
            x = x.next;
        return x; // 返回该结点
    } else { // 插入位置在后半段
        Node<E> x = last; 
        for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历
            x = x.prev;
        return x; // 返回该结点
    }
}

E unlink(Node<E> x) {
    // 保存结点的元素
    final E element = x.item;
    // 保存x的后继
    final Node<E> next = x.next;
    // 保存x的前驱
    final Node<E> prev = x.prev;
    
    if (prev == null) { // 前驱为空，表示删除的结点为头结点
        first = next; // 重新赋值头结点
    } else { // 删除的结点不为头结点
        prev.next = next; // 赋值前驱结点的后继
        x.prev = null; // 结点的前驱为空，切断结点的前驱指针
    }

    if (next == null) { // 后继为空，表示删除的结点为尾结点
        last = prev; // 重新赋值尾结点
    } else { // 删除的结点不为尾结点
        next.prev = prev; // 赋值后继结点的前驱
        x.next = null; // 结点的后继为空，切断结点的后继指针
    }

    x.item = null; // 结点元素赋值为空
    // 减少元素实际个数
    size--; 
    // 结构性修改加1
    modCount++;
    // 返回结点的旧元素
    return element;
}

// 将LinkedList的“容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();
    // Write out size
  	s.writeInt(size);
  
  	// Write out all elements in the proper order.
  	for (Node<E> x = first; x != null; x = x.next)
     	 s.writeObject(x.item);
}

// 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
  	s.defaultReadObject();  
  	// Read in size
  	int size = s.readInt();
  
  	// Read in all elements in the proper order.
  	for (int i = 0; i < size; i++)
    	  linkLast((E)s.readObject());
}

public interface Map<K,V>

public abstract class AbstractMap<K,V> implements Map<K,V>

public abstract Set<Entry<K,V>> entrySet();

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

transient volatile Set<K> keySet;  //1.8 去除volatile
transient volatile Collection<V> values;

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  
    final K key;
    V value;
    Node<K,V> next; //指向下一个节点的指针
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    Entry<K,V> before, after;	 //LinkedHashMap.Entry<K,V>

    final int hash;			//HashMap.Node<K,V>
    final K key;
    V value;
    Node<K,V> next;
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//兼顾高低位, 优化hash值位置冲突
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {  //first指向hash值对应数组位置中的Node节点
        if (first.hash == hash && // 如果first节点对应的hash和key的hash相等(在数组相同位置,只是说明 hash&(n-1) 操作结果相等, 说明hash值的部分低位相等, 并不代表整个hash值相等), 并且first对应的key也相等的话, first节点就是要查找的
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {  //说明存在hash冲突
            if (first instanceof TreeNode)  //说明由红黑树对hash值冲突进行管理
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  //查找红黑树
            do {  //说明hash值冲突是由链表进行管理
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);  //对链表进行遍历
        }
    }
    return null;
}

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