不定期更新中……
List
ArrayList 的底层实现
ArrayList 是基于数组实现的，是一个动态数组，其容量能自动增长，类似于 C 语言中的动态申请内存，动态增长内存。
ArrayList 不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类，也可以使用并发包下的 CopyOnWriteArrayList 类。
ArrayList 如何扩容？
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。
当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。
Map
HashMap 的底层实现
JDK 1.8 之前使用数组 + 单链表实现，JDK 1.8 以后使用数组 + 单链表/红黑树实现。
JDK 1.8 中 HashMap 为什么要引入红黑树？
当 HashMap 中出现较多哈希冲突时，链表有可能会变得非常长，而链表是从链表的 head 或者 tail 查询的，效率会随着长度的增长而降低。引入红黑树就是为了解决链表过长带来的查询效率问题。红黑树的树形结构使原本查询链表的时间复杂度 O(n) 降到了 O(logn)。
HashMap 什么情况使用链表？什么情况会使用红黑树？
若桶中链表元素超过 8 时，会自动转化成红黑树；若桶中元素小于等于 6 时，树结构还原成链表形式。
原因：
- 红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要。
- 链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
- 中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。