容器

1. ArrayList
   0. 通过数组实现
   1. add，会进行扩容（当前数组大小 + （当前数组大小 / 2））
   2. remove，删除对应的下标，并通过System.arraycopy进行数组平移
   3. 不能使用for循环进行数组的删除，因为删除数组会平移，应该使用迭代器
   4. 多线程并发不能使用ArrayList，要使用CopyOnWriteArrayList
   5. 添加多，查找少应该使用LinkedList，避免频繁copy

2. LinkedList
   0. 通过双向链表实现
   1. add直接在末尾添加一个Node
   2. remove，通过遍历记数找到对应的下标。index < (size >> 1)如果是前半段则顺序查找，如果是后半段则倒序查找
   3. 修改多，应该用LinkedList。查询多则使用ArrayList

3. CopyOnWriteArrayList
   1. 底层原理与ArrayList相似
   2. 线程安全
   3. 每次数组操作都是通过拷贝新数组进行操作，然后再赋值回去
   4. add，通过ReentrantLock + 数组拷贝 + volatile实现线程安全。通过ReentrantLock加锁，volatile实现内存共享，数组拷贝触发内存地址变更，同步其他线程
   5. 尽量使用addAll和removeAll，来进行批量操作，因为每次add或remove都会进行一次数组拷贝。

4. hashMap
   0. 数组 + 链表 + 红黑树实现
   1. 当链表长度大于8链表转为红黑树，当红黑树大小小于等于6时，变回链表。（红黑树的出现是为了解决链表过长的问题）
   2. put的实现过程：1. 对key计算Hash值（计算公式：hash = (h = key.hashCode()) ^ (h >>> 16)） 2. 通过计算((n - 1) & hash)获得数组的下标，如果对应的下标中没有值，则直接进行赋值。如果有值，意味着发生了hash冲突，需要解决冲突。 3. 出现冲突时首先判断key是否相等，内存地址是否相等。如果都相等，那就直接覆盖。 4. 如果key不相等，则先判断当前的node，如果是红黑树，则根据红黑树的规则直接插入。如果是链表，则直接插入链表末尾。如果链表长度大于等于8且数组长度大于64，则扩展为红黑树。
   3. 为什么链表长度是8？
   因为当链表长度为8时，链表的冲突概率已经很小了。为了处理特殊情况（大于等于8）就转为红黑树。虽然红黑树的访问复杂度是O(LogN)，链表的是O(n)，红黑树比链表访问要快，但是红黑树的内存占用是链表的2倍。
   4. 扩容算法（参考）
   jdk1.7：在插入元素时，判断如果当前元素(键值对)个数超过阈值，并且出现了hash冲突，此时会进行扩容，将数组变为原来的两倍，并且所有元素重新计算hash，放到新的数组中。因为1.7中元素的链表插入是采用的头插法，所以多线程下会出现死循环的问题。
   jdk1.8：扩容是发生在插入元素之后。如果插入的链表后，链表个数是7个，那么就会进行扩容，如果数组长度超过64，则当前链表改为红黑树，如果没有超过64，则数组的大小变为原来的2倍。如果链表个数没有达到7个，则判断hashMap的元素个数是否超过阈值(size > 0.75 * 16)，如果超过了，同样进行扩容（之后扩大数组的容量，不会转换红黑树）。
   5. 调用 new HashMap(1000) 构造方法，内部还会扩容吗？
   会的，因为HashMap的构造参数中还有一个加载因子（0.75），所以实际上容量不到1000，后续还需要扩容。加载因子的作用是判断HashMap内部是否需要扩容。即当内部容量达到1000 * 0.75 = 750之后，就会扩容，而不是达到1000才扩容。扩容之后，空间变大了，hash冲突降低了。

5. ArrayMap
   0. 由两个数组组成的Map
   1. 数组1存放hash值，数组2存放key+value
   2. get，通过计算hash找到对应的下标，再通过二分查找，找到hash对应的key/value
   3. put，通过计算hash找到数组2中的下标，如果对应下标没有值，直接插入。如果有值，则插入到后面，后面的数组统一后移
   4. 缓存机制：缓存数组长度为4或者8的数组，每个上限10个。目的：为了减少频繁创建和销毁数组对象。

6. ConcurrentHashMap
   0. 通过volatile修饰Map，保证其在内存中的可见性，确保线程同步
   1. 在putValue时，通过for循环和CAS自旋确保不会出现同步问题
   2. 在扩容时，会通过状态确保扩容过程
   3. 在操作节点时，通过synchronized锁住节点

7. LinkedBlockingQueue和ArrayBlockingQueue
   在队列存放满后，存数据的线程会进入阻塞，等待空间。
   在队列为空时，取数据的线程会进入阻塞，等待新的数据到来。
   通过AQS的await进行阻塞，通过signal进行唤醒

   名字	底层实现	容量大小
   LinkedBlockingQueue	使用链表实现	Int.MAX_VALUE
   ArrayBlockingQueue	使用数组实现	需要初始化时指定容量

8. LRU数据结构实现（https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247490403&idx=1&sn=dd361a87d74eec4ca9ef97efe016c906）
   双向链表 + HashMap

参考资料：
面试官: 我必问的容器知识点! - 掘金 (juejin.cn)
Carson带你学Java：手把手带你源码分析 HashMap 1.7
重读源码之 SparseArray 和 ArrayMap