java复制代码10  % 4 = 2
-10 % 4 = -2      // 负数
10  & (4 - 1) = 2
-10 & (4 - 1) = 2 // 正数

java复制代码String str1 = "Aa";
String str2 = "BB";
System.out.println(str1.hashCode());  // 2112
System.out.println(str2.hashCode());  // 2112 散列冲突

bash复制代码装载因子 = 散列表中键值对数目 / 散列表的长度

java复制代码public class ArrayDeque<E> extends AbstractCollection<E>
		implements Deque<E>, Cloneable, Serializable
{
    // 疑问 1：为什么字段都声明 private 关键字？
    // 疑问 2：为什么字段都声明 transient 关键字？
    // 疑问 3：为什么 elements 字段不声明为泛型类型 E？
    // 疑问 4：为什么没有看到 ArrayList 类似的 MAX_ARRAY_SIZE 最大容量限制？

    // 底层数组
    transient Object[] elements; // non-private to simplify nested class access

    // 队头指针
    transient int head;

    // 队尾指针
    transient int tail;

    // new ArrayDeque(0) 最小初始容量
    private static final int MIN_INITIAL_CAPACITY = 8;

    // 尾指针 - 头指针
    public int size() {
        return (tail - head) & (elements.length - 1);
    }
}

java复制代码// 无参构造方法
public ArrayDeque() {
    elements = new Object[16];
}

// 带初始容量的构造方法
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

// 带集合的构造方法
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    // 疑问 5：为什么带集合的构造方法不使用 Arrays 工具整体复制，而是逐个添加？
    addAll(c);
}

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

// 求离 numElements 最近的 2 的整数幂，即 nextPow2 问题
// 疑问 6：为什么 ArrayDeque 要求容量是 2 的整数幂？
// 疑问 7：calculateSize() 的函数体解释一下？
private static int calculateSize(int numElements) {
    // 如果 numElements 小于 8（MIN_INITIAL_CAPACITY），则返回 8
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        // 五轮无符号右移和或运算后，变成最高有效位开始后面都是 1
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        // 加 1 进位，得到最近 2 的整数幂
        initialCapacity++;
			
        // 变成负数（高位是 1000，低位都是 0000）
        if (initialCapacity < 0)
            // 右移 1 位，取 2^30 为初始容量
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

java复制代码// 逐个添加元素
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

java复制代码size     = 0 0 0 1 0 0 0 0 0 0     // 2^n 的补码
size - 1 = 0 0 0 0 1 1 1 1 1 1     // 2^n - 1 的补码
-1       = 1 1 1 1 1 1 1 1 1 1     // -1 的补码
0        = 0 0 0 0 0 0 0 0 0 0     // 0 的补码

// 尾指针的循环：
1、如果 tail + 1 <= size - 1，则 (tail + 1) & (size - 1) 后保持不变
2、如果 tail + 1 == size，则 size & (size - 1) 为 0
// 头指针的循环
1、如果 head - 1 >= 0，则（head - 1) & (size - 1) 后保持不变
2、如果 head - 1 == -1，则 -1 & (size - 1) 后为 size - 1

java复制代码n = 0 0 0 0 1 x x x x x     // n
n = 0 0 0 0 1 1 x x x x     // n |= n >>> 1;
n = 0 0 0 0 1 1 1 1 x x     // n |= n >>> 2;
n = 0 0 0 0 1 1 1 1 1 1     // n |= n >>> 4;
n = 0 0 0 0 1 1 1 1 1 1     // n |= n >>> 8;（这一步对 n 没有影响了）
n = 0 0 0 0 1 1 1 1 1 1     // n |= n >>> 16;（这一步对 n 没有影响了）
n = 0 0 0 1 0 0 0 0 0 0     // n ++（进位，得到最近 2 的整数幂）

java复制代码public void addLast(E e) {
    // 疑问：为什么 ArrayDeque 不支持添加 null 元素
    if (e == null)
        throw new NullPointerException();
    // tail 指针本身就是指向下一个位置，所以直接填充
    elements[tail] = e;
    // 修改 tail 指针到下一个位置，并通过取余操作循环到数组头部
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

public void addFirst(E e) {
    // 疑问 8：为什么 ArrayDeque 禁止存储 null 元素？
    if (e == null)
        throw new NullPointerException();
    // 修改 head 指针到前一个位置，并通过取余操作循环到数组尾部
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

bash复制代码While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicated that the deque is empty.

java复制代码public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    // 队列为空
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

java复制代码// 扩容操作
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    // 队头指针到数组末尾的元素个数
    int r = n - p;
    // 容量翻倍
    int newCapacity = n << 1;
    // 容量变成负数
    if (newCapacity < 0)
        // ArrayList 扩容整型溢出时会抛出 OutOfMemoryError
        // ArrayDeque 扩容整型溢出时会抛出 IllegalStateException
        // 看了一下，发现这两个容器出自不同作者，不能统一下吗哈哈
        throw new IllegalStateException("Sorry, deque too big");
    // 创建新数组
    Object[] a = new Object[newCapacity];
    // 将队头指针到数组末尾的元素拷贝到数组头部
    System.arraycopy(elements, p, a, 0, r);
    // 拷贝剩下的从数组头部到尾指针的元素
    System.arraycopy(elements, 0, a, r, p);
    // 指向新数组
    elements = a;
    // 重置头尾指针
    head = 0;
    tail = n;
}

java复制代码public E pollFirst() {
    // head 指针本身就是指向队头元素，所以直接获取
    int h = head;
    E result = (E) elements[h];
    if (result == null)
        return null;
    elements[h] = null;
    // 修改 head 指针
    head = (h + 1) & (elements.length - 1);
    return result;
}

public E pollLast() {
    // tail 指针本身是指向队尾元素的下一个位置，所以需要返回上一个位置
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

java复制代码private class DeqIterator implements Iterator<E> {

    private int cursor = head;

    private int fence = tail;

    private int lastRet = -1;

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

    public E next() {
        if (cursor == fence) throw new NoSuchElementException();
        E result = (E) elements[cursor];
        // 无法检测到所有并发修改的情况
        if (tail != fence || result == null)
            throw new ConcurrentModificationException();
        lastRet = cursor;
        cursor = (cursor + 1) & (elements.length - 1);
        return result;
    }
    ...
}

java复制代码// 序列化过程
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    // 写入数组长度
    s.writeInt(size());
    // 写入从 head 指针到 tail 指针之间的有效元素
    int mask = elements.length - 1;
    for (int i = head; i != tail; i = (i + 1) & mask)
        s.writeObject(elements[i]);
}

// 反序列化过程
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    // 读取数组长度
    int size = s.readInt();
    // 计算最近的 2 的整数幂
    int capacity = calculateSize(size);
    // 分配数组
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
    allocateElements(size);
    // 设置头尾指针
    head = 0;
    tail = size;
    // 将数据规整到数组下标 0 位置
    for (int i = 0; i < size; i++)
        elements[i] = s.readObject();
}

java复制代码public ArrayDeque<E> clone() {
    try {
        @SuppressWarnings("unchecked")
        ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
        result.elements = Arrays.copyOf(elements, elements.length);
        return result;
    } catch (CloneNotSupportedException e) {
        throw new AssertionError();
    }
}

java复制代码public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    // 疑问 1：为什么字段都不声明 private 关键字？
    // 疑问 2：为什么字段都声明 transient 关键字？
    // 元素个数
    transient int size = 0;

    // 头指针
    transient Node<E> first;

    // 尾指针
    transient Node<E> last;

    // 链表节点
    private static class Node<E> {
        // 节点数据
        // （类型擦除后：Object item;）
        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;
        }
    }
}

java复制代码// 无参构造方法
public LinkedList() {
}

// 带集合的构造方法
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

// 在链表尾部添加集合
public boolean addAll(Collection<? extends E> c) {
    // 索引为 size，等于在链表尾部添加
    return addAll(size, c);
}

java复制代码public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        // 在尾部添加
        linkLast(element);
    else
        // 在指定位置添加
        linkBefore(element, node(index));
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在链表头部添加
private void linkFirst(E e) {
    // 1. 找到插入位置的后继节点（first）
    final Node<E> f = first;
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点（null）
    // 4. 将新节点的 next 指针指向后继节点（f）
    // 5. 将前驱节点的 next 指针指向新节点（前驱节点是 null，所以没有这个步骤）
    final Node<E> newNode = new Node<>(null, e, f);
    // 修改 first 指针
    first = newNode;
    if (f == null)
        // f 为 null 说明首个添加的元素，需要修改 last 指针
        last = newNode;
    else
        // 6. 将后继节点的 prev 指针指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}

// 在链表尾部添加
void linkLast(E e) {
    final Node<E> l = last;
    // 1. 找到插入位置的后继节点（null）
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点（l）
    // 4. 将新节点的 next 指针指向后继节点（null）
    final Node<E> newNode = new Node<>(l, e, null);
    // 修改 last 指针
    last = newNode;
    if (l == null)
        // l 为 null 说明首个添加的元素，需要修改 first 指针
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        l.next = newNode;
    // 6. 将后继节点的 prev 指针指向新节点（后继节点是 null，所以没有这个步骤）
    size++;
    modCount++;
}

// 在指定节点前添加
// 1. 找到插入位置的后继节点
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点（pred）
    // 4. 将新节点的 next 指针指向后继节点（succ）
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

// 在指定位置添加整个集合元素
// index 为 0：在链表头部添加
// index 为 size：在链表尾部添加
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    // 事实上，c.toArray() 的实际类型不一定是 Object[]，有可能是 String[] 等
    // 不过，我们是通过 Node中的item 承接的，所以不用担心 ArrayList 中的 ArrayStoreException 问题
    Object[] a = c.toArray();
    // 添加的数组为空，跳过
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // 1. 找到插入位置的后继节点
    // pred：插入位置的前驱节点
    // succ：插入位置的后继节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 找到 index 位置原本的节点，插入后变成后继节点
        succ = node(index);
        pred = succ.prev;
    }
    // 插入集合元素
    for (Object o : a) {
        E e = (E) o;
        // 2. 构造新节点
        // 3. 将新节点的 prev 指针指向前驱节点
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            // pred 为 null 说明是在头部插入，需要修改 first 指针
            first = newNode;
        else
            // 5. 将前驱节点的 next 指针指向新节点
            pred.next = newNode;
        // 修改前驱指针
        pred = newNode;
    }

    if (succ == null) {
        // succ 为 null 说明是在尾部插入，需要修改 last 指针
        last = pred;
    } else {
        // 4. 将新节点的 next 指针指向后继节点
        pred.next = succ;
        // 6. 将后继节点的 prev 指针指向新节点
        succ.prev = pred;
    }
    // 数量增加 numNew
    size += numNew;
    modCount++;
    return true;
}

// 将 LinkedList 转化为 Object 数组
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

java复制代码// 寻找指定位置的节点，时间复杂度：O(n)
Node<E> node(int index) {
    if (index < (size >> 1)) {
        // 如果索引位置小于 size/2，则从头节点开始找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 如果索引位置大于 size/2，则从尾节点开始找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

java复制代码// 删除头部元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除尾部元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 删除指定元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

java复制代码public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

// 非静态内部类
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // 创建迭代器时会记录外部类的 modCount
    private int expectedModCount = modCount;

    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public E next() {
        // 更新 expectedModCount
        checkForComodification();
        ...
    }
    ...
}

java复制代码// 序列化和反序列化只考虑有效数据

// 序列化过程
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // 写入链表长度
    s.writeInt(size);

    // 写入节点上的有效数据
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

// 反序列化过程
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // 读取链表长度
    int size = s.readInt();
		
    // 读取有效元素并用 linkLast 添加到链表尾部
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

php复制代码private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // 将原链表中的数据依次添加到新立案表中
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

java复制代码List<String> list = new ArrayList();
list.add("xiao");
list.add("peng");
list.add(".");

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    // 可能抛出 ConcurrentModificationException 异常
    iterator.next();
}

java复制代码public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

// 使用 synchronized 实现线程安全
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
    final List<E> list;

    public boolean equals(Object o) {
        if (this == o) return true;
        synchronized (mutex) {return list.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return list.hashCode();}
    }

    public E get(int index) {
        synchronized (mutex) {return list.get(index);}
    }
    public E set(int index, E element) {
        synchronized (mutex) {return list.set(index, element);}
    }
    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }
    public E remove(int index) {
        synchronized (mutex) {return list.remove(index);}
    }
		...
}

java复制代码// 锁
final transient ReentrantLock lock = new ReentrantLock();

// 在 Java 11 中，ReentrantLock 被替换为 synchronized 锁
// The lock protecting all mutators.  (We have a mild preference for builtin monitors over ReentrantLock when either will do.)
final transient Object lock = new Object();

// 底层数组
// 疑问 1：为什么 array 要使用 volatile 关键字？
private transient volatile Object[] array;

java复制代码// 疑问 2：为什么 CopyOnWriteArrayList 不提供预初始化容量的构造器？

// 无参构造方法
public CopyOnWriteArrayList() {
    // 创建空数组
    setArray(new Object[0]);
}

// 带集合的构造方法
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // 这个“奇怪”的分支在 ArrayList 文章中分析过，去看看
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

// 带数组的构造方法
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 疑问 3：为什么要把 E[] 类型的入参转化为 Object[] 类型
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, *Object[]*.class));
}

final Object[] getArray() {
    return array;
}

final void setArray(Object[] a) {
    array = a;
}

public Object[] toArray() {
    Object[] elements = getArray();
    return Arrays.copyOf(elements, elements.length);
}

java复制代码// 在数组尾部添加元素
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    // 复制新数组
    Object[] elements = getArray();
    int len = elements.length;
    // 疑问 4：在添加方法中，为什么扩容只增大 1 容量，而 ArrayList 会增大 1.5 倍？
    Object[] newElements = Arrays.copyOf(elements, len + 1 /* 容量 + 1*/);
    // 在新数组上添加元素
    newElements[len] = e;
    // 设置新数组
    setArray(newElements);
    // 释放锁
    lock.unlock();
    return true;
}

// 在数组尾部添加元素
public void add(int index, E element) {
    // 原理相同，省略
    ...
}

// 批量在数组尾部添加元素
public boolean addAll(Collection<? extends E> c) {
    // 原理相同，省略
    ...
}

java复制代码// 修改数组元素
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    // 旧元素
    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);
    }
    // 释放锁
    lock.unlock();
    // 返回旧数据
    return oldValue;
}

java复制代码// 删除数组元素
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    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);
    }
    // 释放锁
    lock.unlock();
    // 返回旧数据
    return oldValue;
}

java复制代码private E get(Object[] a, int index) {
    return (E) a[index];
}

public E get(int index) {
    return get(getArray(), index);
}

public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
}

java复制代码// 注意看：有 static 关键字，直接引用底层数组
static final class COWIterator<E> implements ListIterator<E> {
    // 底层数组
    private final Object[] snapshot;
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
}

java复制代码// 注意看：没有 static 关键字，通过外部类引用来访问底层数组
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}
    ...
}

scss复制代码// 序列化过程
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    Object[] elements = getArray();
    // 写入数组长度
    s.writeInt(elements.length);
    // 写入有效元素
    for (Object element : elements)
        s.writeObject(element);
}

// 反序列化过程
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    // 设置 ReentrantLock 对象
    resetLock();
    // 读取数组长度
    int len = s.readInt();
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, len);
    // 创建底层数组
    Object[] elements = new Object[len];
    // 读取数组对象
    for (int i = 0; i < len; i++)
        elements[i] = s.readObject();
    // 设置新数组
    setArray(elements);
}

// 疑问 5：resetLock() 方法不好理解，解释一下？
private void resetLock() {
    // 等价于带 Volatile 语义的 this.lock = new ReentrantLock()
    UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
}

// Unsafe API
private static final sun.misc.Unsafe UNSAFE;
// lock 字段在对象实例数据中的偏移量
private static final long lockOffset;

static {
    // 这三行的作用：lock 字段在对象实例数据中的偏移量
    UNSAFE = sun.misc.Unsafe.getUnsafe();
    Class<?> k = CopyOnWriteArrayList.class;
    lockOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("lock"));
}

typescript复制代码public Object clone() {
    try {
        @SuppressWarnings("unchecked")
        // 疑问 6：为什么 array 数组没有深拷贝？
        CopyOnWriteArrayList<E> clone = (CopyOnWriteArrayList<E>) super.clone();
        // 设置 ReentrantLock 对象（相当于 lock 字段的深拷贝）
        clone.resetLock();
        return clone;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
}

java复制代码public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
    // 底层就是 OnWriteArrayList
    private final CopyOnWriteArrayList<E> al;

    // 无参构造方法
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    // 带集合的构造方法
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 入参是 CopyOnWriteArraySet，说明是不重复的，直接添加
            CopyOnWriteArraySet<E> cc = (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            // 使用 addAllAbsent 添加不重复的元素
            al = new CopyOnWriteArrayList<E>();
            al.addAllAbsent(c);
        }
    }

    public int size() {
        return al.size();
    }
}

java复制代码public boolean add(E e) {
    return al.addIfAbsent(e);
}

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

java复制代码public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot);
}

public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
}

// 通过线性扫描匹配元素位置，而不是计算哈希匹配，时间复杂度是 O(n)
private static int indexOf(Object o, Object[] elements, int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null) return i;
    } else {
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i])) return i;
    }
    return -1;
}

java复制代码public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // new ArrayList() 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // new ArrayList(0) 的全局空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // new ArrayList() 的全局空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 修改次数记录
    protected transient int modCount = 0;

    // 数组的最大长度
    // 疑问 4：为什么 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.MAX_VALUE 不行吗？
    // 疑问 5：为什么 ArrayList 的最大容量是 MAX_VALUE - 8，一定会减 8 吗？
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

    // 疑问 1：为什么不声明 private（后文回答）
    // 疑问 2：为什么声明 transient（后文回答）
    // 疑问 3：为什么不声明为泛型类型 E
    // 底层数组
    transient Object[] elementData;

    // 数组的有效长度（不是 elementData.length）
    private int size;

    // size() 返回的是数组的有效长度（合理，底层数组我们不关心）
    public int size() {
        return size;
    }
}

java复制代码// 带初始容量的构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 创建 initialCapacity 长度的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 指向第 1 个全局空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 不合法的初始容量
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

// 无参构造方法
public ArrayList() {
    // 指向第 1 个全局空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 带集合的构造方法
public ArrayList(Collection<? extends E> c) {
    // 将集合转为数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 疑问 7：这一个条件语句好奇怪，toArray() 的返回值类型就是 Object[] 啊？
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

java复制代码OutOfMemoryError: Requested array size exceeds VM limit

java复制代码// 在数组末尾添加元素
public boolean add(E e) {
    // 先确保底层数组容量足够容纳 size + 1，不足会扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 在 size + 1 的位置赋值
    elementData[size++] = e;
    return true;
}

// 在数组中间插入元素
public void add(int index, E element) {
    // 范围检查
    rangeCheckForAdd(index);
    // 先确保容量足够容纳 size + 1，不足会扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 先搬运数据腾出空位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 在 index 的位置赋值
    elementData[index] = element;
    // 长度加一
    size++;
}

// 在数组末尾添加集合
public boolean addAll(Collection<? extends E> c) {
    // 集合转数组
    Object[] a = c.toArray();
    // 先确保底层数组容量足够容纳 size + numNew，不足会扩容
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 搬运原数据
    System.arraycopy(a, 0, elementData, size, numNew);
    // 长度加 numNew
    size += numNew;
    return numNew != 0;
}

// 在数组中间插入集合
public boolean addAll(int index, Collection<? extends E> c) {
    // 略，原理类似
}

// 尝试扩容
// （提示：源码调用了 calculateCapacity() 函数，这里做内联简化）
private void ensureCapacityInternal(int minCapacity) {
    // 使用无参构造器初始化时，指定扩容为 10 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity =  Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 疑问 8：不应该是 elementData.length - minCapacity > 0 吗？
    // 如果底层数组长度不够 minCapacity 最小容量要求，则需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // 旧容量
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 * 1.5 倍（有可能整型溢出）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量小于最小容量要求，则使用最小容量（addAll 大集合的情况）
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    // （提示：上一个 if 的 newCapacity 有可能是溢出的）
    // 如果新容量超出最大数组长度限制，说明无法扩容 1.5 倍，回归到 minCapacity 上
    // （提示：源码调用了 hugeCapacity() 函数，这里做内联简化）
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        // 最小容量要求发生整型溢出，无法满足要求，只能直接抛出 OOM
        if (minCapacity < 0) throw new OutOfMemoryError();
        // 如果最小容量要求超出最大数组长度限制，则扩容到 MAX_VALUE（说明不一定会减 8）
        // 否则，扩容到最大数组长度限制（MAX_VALUE - 8）
        newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
    // 扩容到 newCapacity 长度
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    // 已经内联简化到 grow 方法中
}

java复制代码// 缩容
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }
}

java复制代码private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    // 创建迭代器是会记录外部类的 modCount
    int expectedModCount = modCount;
    ...

    Itr() {}

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

    @SuppressWarnings("unchecked")
    public E next() {
        // 检查
        checkForComodification();
        ...
    }

    public void remove() {
        ...
        // 更新
        expectedModCount = modCount;
    }
}

java复制代码// 序列化和反序列化只考虑有效元素
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(size);

    // 写入有效元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

typescript复制代码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复制代码public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

private class SubList extends AbstractList<E> implements RandomAccess {
    // 原 ArrayList
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        // modCount 记录
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
        rangeCheck(index);
        // 在 ArrayList 上增加或删除元素，会导致 SubList 抛出 ConcurrentModificationException 异常
        checkForComodification();
        // 在 SubList 上增加或删除元素，会影响到 ArrayList；
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
}

java复制代码// 假设没有特殊处理
List<String> list = new ArrayList<>(Arrays.asList("list"));
// class java.util.ArrayList
System.out.println(list.getClass());

Object[] listArray = list.toArray();
// 如果过没有特殊处理，实际类型是 [Ljava.lang
System.out.println(listArray.getClass());
// 如果过没有特殊处理，将抛出 ArrayStoreException 异常
listArray[0] = new Object();

java复制代码public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {
    // 泛型擦除后：Object[] a;
    private final E[] a;

    // 泛型擦除后：Object[] array;
    // Java 数组是协变的，能够接收 String[] 类型的数组
    ArrayList(E[] array) {
        // 赋值
        a = Objects.requireNonNull(array);
    }

    // 实际返回的数组可能是 Object[] 类型，也可能是 String[] 类型
    @Override
    public Object[] toArray() {
        return a.clone();
    }
}

java复制代码public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    transient Object[] elementData;

    // 带集合的构造方法
    public ArrayList(Collection<? extends E> c) {
        // 将集合转为数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 疑问 7：这一个条件语句好奇怪，toArray() 的返回值类型就是 Object[] 啊？
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
}

java复制代码public Cache<String, User> createUserCache() {
    return CacheBuilder.newBuilder().maximumSize(10000L).build();
}

java复制代码public Cache<String, String> createUserCache() {
    return CacheBuilder.newBuilder()
            .maximumWeight(50000)
            .weigher((key, value) -> (int) Math.ceil(value.length() / 1000))
            .build();
    }

java复制代码public static void main(String[] args) {
    try {
        Cache<String, String> cache = CacheBuilder.newBuilder()
            .weigher((key, value) -> 2)
            .maximumSize(2)
            .build();
        cache.put("key1", "value1");
        cache.put("key2", "value2");
        System.out.println(cache.size());
    } catch (Exception e) {
        e.printStackTrace();
    }
}

css复制代码java.lang.IllegalStateException: maximum size can not be combined with weigher
	at com.google.common.base.Preconditions.checkState(Preconditions.java:502)
	at com.google.common.cache.CacheBuilder.maximumSize(CacheBuilder.java:484)
	at com.veezean.skills.cache.guava.CacheService.main(CacheService.java:205)

java复制代码public static void main(String[] args) {
    try {
        Cache<String, String> cache = CacheBuilder.newBuilder()
                .maximumSize(2)
                .removalListener(notification -> {
                    System.out.println("---监听到缓存移除事件：" + notification);
                })
                .build();
        System.out.println("put放入key1");
        cache.put("key1", "value1");
        System.out.println("put放入key2");
        cache.put("key2", "value1");
        System.out.println("put放入key3");
        cache.put("key3", "value1");
        System.out.println("put操作后，当前缓存记录数：" + cache.size());
        System.out.println("查询key1对应值：" + cache.getIfPresent("key1"));
    } catch (Exception e) {
        e.printStackTrace();
    }
}

arduino复制代码put放入key1
put放入key2
put放入key3
---监听到缓存移除事件：key1=value1
put操作后，当前缓存记录数：2
查询key1对应值：null

java复制代码public static void main(String[] args) {
    try {
        Cache<String, String> cache = CacheBuilder.newBuilder()
                .expireAfterWrite(1L, TimeUnit.SECONDS)
                .recordStats()
                .build();
        cache.put("key1", "value1");
        cache.put("key2", "value2");
        cache.put("key3", "value3");
        System.out.println("put操作后，当前缓存记录数：" + cache.size());
        System.out.println("查询key1对应值：" + cache.getIfPresent("key1"));
        System.out.println("统计信息：" + cache.stats());
        System.out.println("-------sleep 等待超过过期时间-------");
        Thread.sleep(1100L);
        System.out.println("执行key1查询操作：" + cache.getIfPresent("key1"));
        System.out.println("当前缓存记录数：" + cache.size());
        System.out.println("当前统计信息：" + cache.stats());
        System.out.println("剩余数据信息：" + cache.asMap());
    } catch (Exception e) {
        e.printStackTrace();
    }
}

ini复制代码put操作后，当前缓存记录数：3
查询key1对应值：value1
统计信息：CacheStats{hitCount=1, missCount=0, loadSuccessCount=0, loadExceptionCount=0, totalLoadTime=0, evictionCount=0}
-------sleep 等待超过过期时间-------
执行key1查询操作：null
当前缓存记录数：1
当前统计信息：CacheStats{hitCount=1, missCount=1, loadSuccessCount=0, loadExceptionCount=0, totalLoadTime=0, evictionCount=2}
剩余数据信息：{}

java复制代码public static void main(String[] args) {
    try {
        Cache<String, String> cache = CacheBuilder.newBuilder()
                .expireAfterWrite(1L, TimeUnit.SECONDS)
                .concurrencyLevel(1)  // 添加这一约束，强制所有数据放在一个分片中
                .recordStats()
                .build();

                // ...省略其余逻辑，与上一段代码相同

    } catch (Exception e) {
        e.printStackTrace();
    }
}

ini复制代码put操作后，当前缓存记录数：3
查询key1对应值：value1
统计信息：CacheStats{hitCount=1, missCount=0, loadSuccessCount=0, loadExceptionCount=0, totalLoadTime=0, evictionCount=0}
-------sleep 等待超过过期时间-------
执行key1查询操作：null
当前缓存记录数：0
当前统计信息：CacheStats{hitCount=1, missCount=1, loadSuccessCount=0, loadExceptionCount=0, totalLoadTime=0, evictionCount=3}
剩余数据信息：{}

jsx复制代码<div id="foo">bar</div>

javascript复制代码React.createElement("div", {id: "foo"}, "bar");

javascript复制代码function Foo({id}) {
  return <div id={id}>foo</div>
}

<Foo id="foo">
  <div id="bar">bar</div>
</Foo>

javascript复制代码function Foo({id}) {
  return React.createElement("div", {id: id}, "foo")}

React.createElement(Foo, {id: "foo"},
  React.createElement("div", {id: "bar"}, "bar")
);

javascript复制代码<div id="foo">
  <div id="bar">bar</div>
	<div id="baz">baz</div>
  <div id="qux">qux</div>
</div>

javascript复制代码React.createElement("div", { id: "foo"}, 
  React.createElement("div", {id: "bar"}, "bar"), 
  React.createElement("div", {id: "baz"}, "baz"),
  React.createElement("div", {id: "qux"}, "qux")
);

javascript复制代码// 简化后
export {createElement} from './src/React';

javascript复制代码import {
  createElement as createElementProd
} from './ReactElement';

const createElement = __DEV__
  ? createElementWithValidation
  : createElementProd;

export { createElement };

javascript复制代码const RESERVED_PROPS = {
  key: true,
  ref: true,
  __self: true,
  __source: true,
};

export function createElement(type, config, ...children) {
  let propName;

  // Reserved names are extracted
  const props = {};

  // 第一段
  let key = '' + config.key;
  let ref = config.ref;
  let self = config.__self;
  let source = config.__source;

  // 第二段
  for (propName in config) {
    if (config.hasOwnProperty(propName) && !RESERVED_PROPS.hasOwnProperty(propName)) {
      props[propName] = config[propName];
    }
  }

  // 第三段
  props.children = children;

  // 第四段
  if (type && type.defaultProps) {
    const defaultProps = type.defaultProps;
    for (propName in defaultProps) {
      if (props[propName] === undefined) {
        props[propName] = defaultProps[propName];
      }
    }
  }

  // 第五段
  return ReactElement(
    type,
    key,
    ref,
    self,
    source,
    ReactCurrentOwner.current,
    props,
  );
}

javascript复制代码<div id="foo">bar</div>
// 转译为
React.createElement("div", {id: "foo"}, "bar");

javascript复制代码  // 第一段
  let key = '' + config.key;
  let ref = config.ref;
  let self = config.__self;
  let source = config.__source;

javascript复制代码var _jsxFileName = "/Users/kevin/Desktop/react-app/src/index.js";
React.createElement("div", {
  id: "foo",
  __self: this,
  __source: {
    fileName: _jsxFileName,
    lineNumber: 5,
    columnNumber: 13
  }
}, "bar");