基础篇：JAVA集合，面试专用

//ArrayList openJDK 13
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) //放不下了
        elementData = grow(); // 扩容
    elementData[s] = e;
    size = s + 1;
}
private Object[] grow() {
    return grow(size + 1);
}
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity,  // minCapacity - oldCapacity == 1
                oldCapacity >> 1 ); // oldCapacity == 1/2 oldCapacity
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

// ArraysSupport.newLength
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    //prefGrowth 是 oldLength 的 1/2，minGrowth 是 1。因此 newLength = 1.5 oldLength
    int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
    if (newLength - MAX_ARRAY_LENGTH <= 0) { // MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8
        return newLength;
    }
    return hugeLength(oldLength, minGrowth);
}

public static class LRU<T> {
    //默认的缓存大小
    private  int CAPACITY = 0;
    //引用一个双向链接表
    private LinkedList<T> list;
    //构造函数
    public LRU(int capacity) {
        this.CAPACITY = capacity;
        list = new LinkedList();
    }
    //添加一个元素
    public synchronized void put(T object) {
        if (list != null && list.contains(object)) {
            list.remove(object);
        }
        removeLeastVisitElement();
        list.addFirst(object);
    }
    //移除最近访问次数最少的元素
    private void removeLeastVisitElement() {
        int size = list.size();
        //注意，这儿必须得是CAPACITY - 1否则所获的size比原来大1
        if (size > (CAPACITY - 1)) {
            Object object = list.removeLast();
        }
    }
    //获取第N个索引下面的元素
    public  T get(int index) {
        return list.get(index);
    }
}

public E getFirst() //获取第一个元素
public E getLast()  //获取最后一个元素
public E removeFirst() // 移除第一个元素，并返回
public E removeLast() // 移除最后一个元素，并返回
public void addFirst(E e) //加入头部
public void addLast(E e)  //加入尾部
public void add(E e) //加入尾部
public boolean contains(Object o) //是否包含 元素 o
public E peek() //获取头部第一个元素
public E element()  // 获取头部第一个元素,不存在则报错
public E poll() //获取头部第一个元素，并移除
public boolean offer(E e) // 调用 add(E e)
public boolean offerFirst(E e) // 调用 addFirst
public boolean offerLast(E e) // 调用 addLast
public void push(E e) //在头部压入一个元素
public E pop()  //弹出第一个元素，并移除。不存在则报错

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    //可重入锁
    final transient ReentrantLock lock = new ReentrantLock();
    //数组，仅通过get和set方法操作
    private transient volatile Object[] array; 
    ....
    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); //调用set方法将新数组设置为当前数组
            return true;
        } finally {
            lock.unlock();//解锁
        }
    }

boolean contains(Object o) // 是否包含 o
boolean isEmpty(); // 是否为空
int size(); //集合元素
Iterator<E> iterator(); // 返回迭代器
Object[] toArray(); // 转为 Object数组
<T> T[] toArray(T[] a); // 转为具体类型数组
boolean add(E e); // 加入尾部
boolean remove(Object o); // 移除 o
boolean containsAll(Collection<?> c); //是否报考 集合 c
boolean addAll(Collection<? extends E> c);// 合并 c 
boolean retainAll(Collection<?> c);//保留只存在集合 c 的元素
void clear(); // 清除集合元素
void sort(Comparator<? super E> c) //根据 Comparator 排序
E get(int index); // 根据下标获取 元素
E set(int index, E element); // 设置第 index 的元素
E remove(int index); // 移除 第 index 的元素
<E> List<E> of(E e1.....) // jdk 9
List<E> copyOf(Collection<? extends E> coll)  // 复制

boolean synchronized contains(Object o);
boolean synchronized isEmpty();
boolean synchronized containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
public synchronized boolean add(E e)
public synchronized E get(int index);
public synchronized E set(int index, E element);
public synchronized E firstElement()
public synchronized void removeElementAt(int index)
public synchronized E lastElement()
public synchronized void setElementAt(E obj, int index)
public synchronized E remove(int index)
public void clear()
Iterator<E> iterator();

public E push(E item) //推入栈顶
public synchronized E pop() // 弹出栈顶元素，不存在则报错
public synchronized E peek() // 获取栈顶元素，不移除
public boolean empty()  // 栈是否为空
public synchronized int search(Object o) // 搜索元素 

K lowerKey(K key)  // 找到第一个比指定的key小的值
K floorKey(K key)  // 找到第一个比指定的key小于或等于的key
K ceilingKey(K key) // 找到第一个大于或等于指定key的值
K higherKey(K key) // 找到第一个大于指定key的值
Map.Entry<K,V> firstEntry() // 获取最小值
Map.Entry<K,V> lastEntry() // 获取最大值
Map.Entry<K,V> pollFirstEntry() // 删除最小的元素
Map.Entry<K,V> pollLastEntry() // 删除最大的元素
NavigableMap<K,V> descendingMap() //返回一个倒序的Map 
// 返回值小于 toKey 的 NavigableMap
NavigableMap<K,V> headMap(K toKey, boolean inclusive)
// 返回值大于 fromKey 的 NavigableMap
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
// 返回值小于 toKey 大于 的 fromKey NavigableMap
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey,   boolean toInclusive)

void and(BitSet set) // 两个BitSet 做与操作，结果并存入当前 BitSet
void andNot(BitSet set) //  两个BitSet 与非操作
void flip(int index) // 反转某一个指定 index 
boolean intersects(BitSet bitSet) // 是否有交集
int cardinality() //返回 true/1 的个数
void clear() // 重置
void clear(int startIndex, int endIndex) // startIndex~endIndex 重置
int nextSetBit(int startIndex) //检索在startIndex之后出现为1的第一位的索引
int nextClearBit(int startIndex) //检索在startIndex之后出现为0的第一位的索引

boolean add(E e); //加入队列尾部
boolean offer(E e); // 加入队列尾部，并返回结果
E remove(); //移除头部元素
E poll();  // 获取头部元素，并移除
E element(); // 获取头部元素，不存在则报错
E peek(); // 获取头部元素，不移除

void addFirst(E e); //加入头部
void addLast(E e);  //加入尾部
boolean offerFirst(E e); //加入头部，并返回结果
boolean offerLast(E e); //加入尾部，并返回结果
E removeFirst(); // 移除第一个元素
E removeLast(); // 移除最后一个元素
E getFirst(); //获取第一个元素,不存在则报错
E getLast();  //获取最后一个元素,不存在则报错
E pollFirst(); //获取第一个元素,并移除
E pollLast(); //获取最后一个元素,并移除
E peekFirst(); //获取第一个元素
E peekLast(); // 获取最后一个元素
void push(E e); //加入头部
E pop(); //弹出头部元素