- DEFAULT_CAPACITY 表示数组的初始大小，默认是 10，这个数字要记住；
- size 表示当前数组的大小，类型 int，没有使用 volatile 修饰，非线程安全的；
- modCount 统计当前数组被修改的版本次数，数组结构有变动，就会 +1。
- 是非线程安全的，多线程情况下，推荐使用线程安全类：Collections#synchronizedList；
- 允许 put null 值，会自动扩容；
- size、isEmpty、get、set、add 等方法时间复杂度都是 O (1)；
- 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。
- 无参数直接初始化，ArrayList 无参构造器初始化时，默认大小是空数组，并不是大家常说的 10，10 是在第一次 add 的时候扩容的数组值
- 指定大小初始化
- 指定初始数据初始化
-
判断是否需要扩容，如果需要执行扩容操作；
-
直接赋值
扩容注意四点
- 扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，直白来说，扩容后的大小是原来容量的 1.5 倍；
- ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。
- 新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
- 源码在扩容的时候，有数组大小溢出意识，就是说扩容后数组的大小下界不能小于 0，上界不能大于 Integer 的最大值，这种意识我们可以学习。
-
扩容本质：Arrays.copyOf(elementData, newCapacity);
删除要注意两点
- 新增的时候是没有对 null 进行校验的，所以删除的时候也是允许删除 null 值的；
- 找到值在数组中的索引位置，是通过 equals 来判断的，如果数组元素不是基本类型，需要我们关注 equals 的具体实现。
迭代的方法
- hasNext 还有没有值可以迭代
- next 如果有值可以迭代，迭代的值是多少
- remove 删除当前迭代的值
LinkedList 底层数据结构是一个双向链表
- 链表每个节点我们叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置；
- first 是双向链表的头节点，它的前一个节点是 null。
- last 是双向链表的尾节点，它的后一个节点是 null；
- 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
- 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。
private static 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;
}
}追加节点时，我们可以选择追加到链表头部，还是追加到链表尾部，add 方法默认是从尾部开始追加，addFirst 方法是从头部开始追加，我们分别来看下两种不同的追加方式：
add(方法)
// 从尾部开始追加节点
void linkLast(E e) {
// 把尾节点数据暂存
final Node<E> l = last;
// 新建新的节点，初始化入参含义：
// l 是新节点的前一个节点，当前值是尾节点值
// e 表示当前新增节点，当前新增节点后一个节点是 null
final Node<E> newNode = new Node<>(l, e, null);
// 新建节点追加到尾部
last = newNode;
//如果链表为空（l 是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点
if (l == null)
first = newNode;
//否则把前尾节点的下一个节点，指向当前尾节点。
else
l.next = newNode;
//大小和版本更改
size++;
modCount++;
}// 从头部追加
private void linkFirst(E e) {
// 头节点赋值给临时变量
final Node<E> f = first;
// 新建节点，前一个节点指向null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值
final Node<E> newNode = new Node<>(null, e, f);
// 新建节点成为头节点
first = newNode;
// 头节点为空，就是链表为空，头尾节点是一个节点
if (f == null)
last = newNode;
//上一个头节点的前一个节点指向当前节点
else
f.prev = newNode;
size++;
modCount++;
}//从头删除节点 f 是链表头节点
private E unlinkFirst(Node<E> f) {
// 拿出头节点的值，作为方法的返回值
final E element = f.item;
// 拿出头节点的下一个节点
final Node<E> next = f.next;
//帮助 GC 回收头节点
f.item = null;
f.next = null;
// 头节点的下一个节点成为头节点
first = next;
//如果 next 为空，表明链表为空
if (next == null)
last = null;
//链表不为空，头节点的前一个节点指向 null
else
next.prev = null;
//修改链表大小和版本
size--;
modCount++;
return element;
}// 根据链表索引位置查询节点
Node<E> node(int index) {
// 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思。
if (index < (size >> 1)) {
Node<E> x = first;
// 直到 for 循环到 index 的前一个 node 停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {// 如果 index 处于队列的后半部分，从尾开始找
Node<E> x = last;
// 直到 for 循环到 index 的后一个 node 停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}| 方法含义 | 返回异常 | 返回特殊值 | 底层实现 |
|---|---|---|---|
| 新增 | add(e) | offer(e) | 底层实现相同 |
| 删除 | remove() | poll(e) | 链表为空时，remove 会抛出异常，poll 返回 null。 |
| 查找 | element() | peek() | 链表为空时，element 会抛出异常，peek 返回 null。 |
- Deque 提供了 removeFirst 和 removeLast 两种方向的使用方式，但当链表为空时的表现都和 remove 方法一样，都会抛出异常。
因为 LinkedList 要实现双向的迭代访问，所以使用 Iterator 接口肯定不行了，因为 Iterator 只支持从头到尾的访问。Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代方法
| 迭代顺序 | 方法 |
|---|---|
| 从尾到头迭代方法 | hasPrevious、previous、previousIndex |
| 从头到尾迭代方法 | hasNext、next、nextIndex |
- ArrayList 无参数构造器构造，现在 add 一个值进去，此时数组的大小是多少，下一次扩容前最大可用大小是多少？
此处数组的大小是 1，下一次扩容前最大可用大小是 10，因为 ArrayList 第一次扩容时，是有默认值的，默认值是 10，在第一次 add 一个值进去时，数组的可用大小被扩容到 10 了
- 如果我连续往 list 里面新增值，增加到第 11 个的时候，数组的大小是多少
当增加到 11 的时候，此时我们希望数组的大小为 11，但实际上数组的最大容量只有 10，不够了就需要扩容，扩容的公式是：oldCapacity + (oldCapacity>> 1)，oldCapacity 表示数组现有大小，目前场景计算公式是：10 + 10 ／2 = 15，然后我们发现 15 已经够用了，所以数组的大小会被扩容到 15
-
数组初始化，被加入一个值后，如果我使用 addAll 方法，一下子加入 15 个值，那么最终数组的大小是多少？
第一题中我们已经计算出来数组在加入一个值后，实际大小是 1，最大可用大小是 10 ，现在需要一下子加入 15 个值，那我们期望数组的大小值就是 16，此时数组最大可用大小只有 10，明显不够，需要扩容，扩容后的大小是：10 + 10 ／2 = 15，这时候发现扩容后的大小仍然不到我们期望的值 16，这时候源码中有一种策略如下，所以最终数组扩容后的大小为 16。
// newCapacity 本次扩容的大小，minCapacity 我们期望的数组最小大小 // 如果扩容后的值 < 我们的期望值，我们的期望值就等于本次扩容的大小 if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
-
现在我有一个很大的数组需要拷贝，原数组大小是 5k，请问如何快速拷贝？
因为原数组比较大，如果新建新数组的时候，不指定数组大小的话，就会频繁扩容，频繁扩容就会有大量拷贝的工作，造成拷贝的性能低下，所以回答说新建数组时，指定新数组的大小为 5k 即可。
-
为什么说扩容会消耗性能
扩容底层使用的是 System.arraycopy 方法，会把原数组的数据全部拷贝到新数组上，所以性能消耗比较严重。
-
有一个 ArrayList，数据是 2、3、3、3、4，中间有三个 3，现在我通过 for (int i=0;i<list.size ();i++) 的方式，想把值是 3 的元素删除，请问可以删除干净么？最终删除的结果是什么，为什么？删除代码如下
List<String> list = new ArrayList<String>() {{ add("2"); add("3"); add("3"); add("3"); add("4"); }}; for (int i = 0; i < list.size(); i++) { if (list.get(i).equals("3")) { list.remove(i); } }
不能删除干净，最终删除的结果是 2、3、4，有一个 3 删除不掉，因为每次删除一个元素后，该元素后面的元素就会往前移动，而此时循环的 i 在不断地增长，最终会使每次删除 3 的后一个 3 被遗漏，导致删除不掉。
-
还是上面的 ArrayList 数组，我们通过增强 for 循环进行删除，可以么
不可以，会报错。因为增强 for 循环过程其实调用的就是迭代器的 next () 方法，当你调用 list#remove () 方法进行删除时，modCount 的值会 +1，而这时候迭代器中的 expectedModCount 的值却没有变，导致在迭代器下次执行 next () 方法时，expectedModCount != modCount 就会报 ConcurrentModificationException 的错误
-
还是上面的数组，如果删除时使用 Iterator.remove () 方法可以删除么，为什么？
可以的，因为 Iterator.remove () 方法在执行的过程中，会把最新的 modCount 赋值给 expectedModCount，这样在下次循环过程中，modCount 和 expectedModCount 两者就会相等。
-
ArrayList 和 LinkedList 有何不同？
可以先从底层数据结构开始说起，然后以某一个方法为突破口深入，比如：最大的不同是两者底层的数据结构不同，ArrayList 底层是数组，LinkedList 底层是双向链表，两者的数据结构不同也导致了操作的 API 实现有所差异，拿新增实现来说，ArrayList 会先计算并决定是否扩容，然后把新增的数据直接赋值到数组上，而 LinkedList 仅仅只需要改变插入节点和其前后节点的指向位置关系即可
-
ArrayList 和 LinkedList 应用场景有何不同
ArrayList 更适合于快速的查找匹配，不适合频繁新增删除，像工作中经常会对元素进行匹配查询的场景比较合适，LinkedList 更适合于经常新增和删除，对查询反而很少的场景。
-
ArrayList 和 LinkedList 两者有没有最大容量
ArrayList 有最大容量的，为 Integer 的最大值，大于这个值 JVM 是不会为数组分配内存空间的，LinkedList 底层是双向链表，理论上可以无限大。但源码中，LinkedList 实际大小用的是 int 类型，这也说明了 LinkedList 不能超过 Integer 的最大值，不然会溢出
-
ArrayList 和 LinkedList 是如何对 null 值进行处理的
ArrayList 允许 null 值新增，也允许 null 值删除。删除 null 值时，是从头开始，找到第一值是 null 的元素删除；LinkedList 新增删除时对 null 值没有特殊校验，是允许新增和删除的。
-
ArrayList 和 LinedList 是线程安全的么，为什么？
当两者作为非共享变量时，比如说仅仅是在方法里面的局部变量时，是没有线程安全问题的，只有当两者是共享变量时，才会有线程安全问题。主要的问题点在于多线程环境下，所有线程任何时刻都可对数组和链表进行操作，这会导致值被覆盖，甚至混乱的情况。
如果有线程安全问题，在迭代的过程中，会频繁报 ConcurrentModificationException 的错误，意思是在我当前循环的过程中，数组或链表的结构被其它线程修改了。
-
如何解决线程安全问题？
Java 源码中推荐使用 Collections#synchronizedList 进行解决，Collections#synchronizedList 的返回值是 List 的每个方法都加了 synchronized 锁，保证了在同一时刻，数组和链表只会被一个线程所修改，或者采用 CopyOnWriteArrayList 并发 List 来解决。
HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表。
- 允许 null 值，不同于 HashTable ，是线程不安全的；
- load factor（影响因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数组容量 > 需要的数组大小 /load factor；
- 如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；
- HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；
- 在迭代过程中，如果 HashMap 的结构被修改，会快速失败
//初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//桶上的链表长度大于等于8时，链表转化成红黑树
static final int TREEIFY_THRESHOLD = 8;
//桶上的红黑树大小小于等于6时，红黑树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//当数组容量大于 64 时，链表才会转化成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
//记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
transient int modCount;
//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
transient int size;
//存放数据的数组
transient Node<K,V>[] table;
// 扩容的门槛，有两种情况
// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
int threshold;
//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {
//红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {- 空数组有无初始化，没有的话初始化；
- 如果通过 key 的 hash 能够直接找到值，跳转到 6，否则到 3；（若无哈希冲突直接插入）
- 如果 hash 冲突，两种解决方案：链表 or 红黑树；
- 如果是链表，递归循环，把新元素追加到队尾；
- 如果是红黑树，调用红黑树新增的方法；
- 通过 2、4、5 将新元素追加成功，再根据 onlyIfAbsent 判断是否需要覆盖；
- 判断是否需要扩容，需要扩容进行扩容，结束。
当链表长度大于等于 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin，此方法有一个判断，当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树，当数组大小小于 64 时，只会触发扩容，不会转化成红黑树，
可能面试的时候，有人问你为什么是 8，这个答案在源码中注释有说，中文翻译过来大概的意思是：
链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗，所以我们需要定义出转化的边界值。
在考虑设计 8 这个值的时候，我们参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006意思是，当链表的长度是 8 的时候，出现的概率是 0.00000006，不到千万分之一，所以说正常情况下，链表的长度不可能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题，所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写代码，使用 HashMap 时，几乎不会碰到链表转化成红黑树的情况，毕竟概念只有千万分之一。
- 首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种：
- 如果节点没有实现 Comparable 接口，使用 equals 进行判断；
- 如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断。
- 新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大；
- 自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点；
- 把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；
- 进行着色和旋转，结束。
面试的时候，一般只会问到新增节点到红黑树上大概是什么样的一个过程，着色和旋转的细节不会问，因为很难说清楚，但我们要清楚着色指的是给红黑树的节点着上红色或黑色，旋转是为了让红黑树更加平衡，提高查询的效率，总的来说都是为了满足红黑树的 5 个原则：
- 节点是红色或黑色
- 根是黑色的
- 所有叶子都是黑色
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
- 从每个叶子到根的所有路径上不能有两个连续的红色节点
- 根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是我们需要寻找的 key，是的话直接返回，不是的话往下。
- 判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型。
- 分别走链表和红黑树不同类型的查找方法。
- 如果红黑树是平衡的，一般查找时间复杂度就是树的深度
-
HashMap 底层数据结构
HashMap 底层是数组 + 链表 + 红黑树的数据结构，数组的主要作用是方便快速查找，时间复杂度是 O(1)，默认大小是 16，数组的下标索引是通过 key 的 hashcode 计算出来的，数组元素叫做 Node，当多个 key 的 hashcode 一致，但 key 值不同时，单个 Node 就会转化成链表，链表的查询复杂度是 O(n)，当链表的长度大于等于 8 并且数组的大小超过 64 时，链表就会转化成红黑树，红黑树的查询复杂度是 O(log(n))，简单来说，最坏的查询次数相当于红黑树的最大深度。
-
HashMap、TreeMap、LinkedHashMap 三者有啥相同点，有啥不同点
相同点：
- 三者在特定的情况下，都会使用红黑树；
- 底层的 hash 算法相同；
- 在迭代的过程中，如果 Map 的数据结构被改动，都会报 ConcurrentModificationException 的错误。
不同点：
- HashMap 数据结构以数组为主，查询非常快，TreeMap 数据结构以红黑树为主，利用了红黑树左小右大的特点，可以实现 key 的排序，LinkedHashMap 在 HashMap 的基础上增加了链表的结构，实现了插入顺序访问和最少访问删除两种策略;
- 由于三种 Map 底层数据结构的差别，导致了三者的使用场景的不同，TreeMap 适合需要根据 key 进行排序的场景，LinkedHashMap 适合按照插入顺序访问，或需要删除最少访问元素的场景，剩余场景我们使用 HashMap 即可，我们工作中大部分场景基本都在使用 HashMap；
- 由于三种 map 的底层数据结构的不同，导致上层包装的 api 略有差别。
-
Map 的 hash 算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key 在数组中的位置公式：tab[(n - 1) & hash]hash 算法其实是一个数学问题，源码中就是通过以上代码来计算 hash 的，首先计算出 key 的 hashcode，因为 key 是 Object，所以会根据 key 的不同类型进行 hashcode 的计算，接着计算 h ^ (h >>> 16) ，这么做的好处是使大多数场景下，算出来的 hash 值比较分散。
一般来说，hash 值算出来之后，要计算当前 key 在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 = hash 值 % 数组大小，这样做的好处，就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上，但取模操作对于处理器的计算是比较慢的，数学上有个公式，当 b 是 2 的幂次方时，a % b = a &（b-1），所以此处索引位置的计算公式我们可以更换为： (n-1) & hash。
- 为什么不用 key % 数组大小，而是需要用 key 的 hash 值 % 数组大小。
如果 key 是数字，直接用 key % 数组大小是完全没有问题的，但我们的 key 还有可能是字符串，是复杂对象，这时候用 字符串或复杂对象 % 数组大小是不行的，所以需要先计算出 key 的 hash 值
- 计算 hash 值时，为什么需要右移 16 位？
hash 算法是 h ^ (h >>> 16)，为了使计算出的 hash 值更分散，所以选择先将 h 无符号右移 16 位，然后再于 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，减少了碰撞的可能性。
- 为什么把取模操作换成了 & 操作？
key.hashCode() 算出来的 hash 值还不是数组的索引下标，为了随机的计算出索引的下表位置，我们还会用 hash 值和数组大小进行取模，这样子计算出来的索引下标比较均匀分布。
取模操作处理器计算比较慢，处理器对 & 操作就比较擅长，换成了 & 操作，是有数学上证明的支撑，为了提高了处理器处理的速度。
- 为什么提倡数组大小是 2 的幂次方？
因为只有大小是 2 的幂次方时，才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。
- 怎么解诀hash冲突
- 使用 hash 算法，(h = key.hashCode()) ^ (h >>> 16)求哈希值;
- 自动扩容，当数组大小快满的时候，采取自动扩容，可以减少 hash 冲突;
- hash 冲突发生时，采用链表来解决;
- hash 冲突严重时，链表会自动转化成红黑树，提高遍历速度。
- HashMap 是如何扩容的？
扩容的时机
- put 时，发现数组为空，进行初始化扩容，默认扩容大小为 16;
- put 成功后，发现现有数组大小大于扩容的门阀值时，进行扩容，扩容为老数组大小的 2 倍;
扩容条件
- 扩容的门阀是 threshold，每次扩容时 threshold 都会被重新计算，门阀值等于数组的大小 * 影响因子（0.75）。当超过门阀值便会扩容
-
hash 冲突解决方法
hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况。如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；如果桶中元素已经是链表，并且链表个数大于等于 8 时，此时有两种情况：
- 如果此时数组大小小于 64，数组再次扩容，链表不会转化成红黑树。
- 如果数组大小大于 64 时，链表就会转化成红黑树。
- 不仅仅判断链表个数大于等于 8，还判断了数组大小，数组容量小于 64 没有立即转化的原因，主要是因为红黑树占用的空间比链表大很多，转化也比较耗时，所以数组容量小的情况下冲突严重，可以先尝试扩容，看看能否通过扩容来解决冲突的问题。
-
为什么链表个数大于等于 8 时，链表要转化成红黑树了？
当链表个数太多了，遍历可能比较耗时，时间复杂度O(n)，转化成红黑树，可以使遍历的时间复杂度降低，但转化成红黑树，有空间和转化耗时的成本，但是正常情况下，根据柏松分布链表个数出现 8 的概念不到千万分之一，所以说正常情况下，链表都不会转化成红黑树，这样设计的目的，是为了防止非正常情况下，比如 hash 算法出了问题时，导致链表个数轻易大于等于 8 时，仍然能够快速遍历，时间复杂度为O(logn)。
-
红黑树什么时候变成链表
当节点的个数小于等于 6 时，红黑树会自动转化成链表，主要还是考虑红黑树的空间成本问题，当节点个数小于等于 6 时，遍历链表也很快，所以红黑树会重新变成链表。
-
HashMap 在 put 时，如果数组中已经有了这个 key，但是不想把 value 覆盖怎么办？取值时，如果得到的 value 是空时，想返回默认值怎么办？
- 如果数组有了 key，但不想覆盖 value ，可以选择 putIfAbsent 方法，这个方法有个内置变量 onlyIfAbsent，内置是 true ，就不会覆盖，我们平时使用的 put 方法，内置 onlyIfAbsent 为 false，是允许覆盖的。
- 取值时，如果为空，想返回默认值，可以使用 getOrDefault 方法，方法第一参数为 key，第二个参数为你想返回的默认值，如 map.getOrDefault(“2”,“0”)，当 map 中没有 key 为 2 的值时，会默认返回 0，而不是空。
-
LinkedHashMap 中的 LRU 是如何实现的。
LRU ，英文全称：Least recently used，中文叫做最近最少访问，在 LinkedHashMap 中，也叫做最少访问删除策略，可以通过 removeEldestEntry 方法设定一定的策略，使最少被访问的元素，在适当的时机被删除，原理是在 put 方法执行的最后，LinkedHashMap 会去检查这种策略，如果满足策略，就删除头节点，保证头节点就是最少访问的元素的原理是：LinkedHashMap 在 get 的时候，都会把当前访问的节点，移动到链表的尾部，慢慢的，就会使头部的节点都是最少被访问的元素。
-
为什么 TreeMap 的元素最好都实现 Comparable 接口，但 key 是 String 的时候，我们却没有额外的工作呢？
因为 TreeMap 的底层就是通过排序来比较两个 key 的大小的，所以推荐 key 实现 Comparable 接口，是为了往你希望的排序顺序上发展， 而 String 本身已经实现了 Comparable 接口，所以使用 String 时，我们不需要额外的工作，不仅仅是 String ，其他包装类型也都实现了 Comparable 接口，如 Long、Double、Short 等等。
底层是个数组，只不过 CopyOnWriteArrayList 在对数组进行操作的时候，基本会分四步走：
- 加锁；
- 从原数组中拷贝出新数组；
- 在新数组上进行操作，并把新数组赋值给数组容器；
- 解锁。
除了加锁之外，CopyOnWriteArrayList 的底层数组还被 volatile 关键字修饰，一旦数组被修改，其它线程立马能够感知到，整体上来说，CopyOnWriteArrayList 就是利用锁 + 数组拷贝 + volatile 关键字保证了 List 的线程安全
新增数据有多种情况，如：新增到数组尾部、新增到数组某一个索引位置、批量新增等等。
1:添加元素到数组尾部
public boolean add(E e) {
final ReentrantLock lock = this.lock;
// 加锁
lock.lock();
try {
// 得到所有的原数组
Object[] elements = getArray();
int len = elements.length;
// 拷贝到新数组里面，新数组的长度是 + 1 的，因为新增会多一个元素
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 在新数组中进行赋值，新元素直接放在数组的尾部
newElements[len] = e;
// 替换掉原来的数组
setArray(newElements);
return true;
// finally 里面释放锁，保证即使 try 发生了异常，仍然能够释放锁
} finally {
lock.unlock();
}
}从源码中看出整个 add 过程都是在持有锁的状态下进行的，通过加锁，来保证同一时刻只能有一个线程能够对同一个数组进行 add 操作。除了加锁之外，还会从老数组中创建出一个新数组，然后把老数组的值拷贝到新数组上。
- 为什么需要拷贝数组，而不是在原来数组上面进行操作呢
- volatile 关键字修饰的是数组，如果我们简单的在原来数组上修改其中某几个元素的值，是无法触发可见性的，我们必须通过修改数组的内存地址才行，也就说要对数组进行重新赋值才行
- 在新的数组上进行拷贝，对老数组没有任何影响，只有新数组完全拷贝完成之后，外部才能访问到，降低了在赋值过程中，老数组数据变动的影响
2:指定位置添加数组元素
// len：数组的长度、index：插入的位置
int numMoved = len - index;
// 如果要插入的位置正好等于数组的末尾，直接拷贝数组即可
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
else {
// 如果要插入的位置在数组的中间，就需要拷贝 2 次
// 第一次从 0 拷贝到 index。
// 第二次从 index+1 拷贝到末尾。
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
// index 索引位置的值是空的，直接赋值即可。
newElements[index] = element;
// 把新数组的值赋值给数组的容器中
setArray(newElements);可以看到，当插入的位置正好处于末尾时，只需要拷贝一次，当插入的位置处于中间时，此时我们会把原数组一分为二，进行两次拷贝操作。
3:批量添加数组元素
public boolean addAll(Collection<? extends E> c) {
//c为要批量添加的数据集合
Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
//如果c长度为0，直接返回
if (cs.length == 0)
return false;
final ReentrantLock lock = this.lock;
//上锁
lock.lock();
try {
//返回还没添加元素的数组
Object[] elements = getArray();
int len = elements.length;
//如果CopyOnWriteArrayList本来没元素，则直接把新数组的值赋值给数组的容器中
if (len == 0 && cs.getClass() == Object[].class)
setArray(cs);
else {
//创建一个len + cs.length长度的数组，并且把elements元素复制到newElements
Object[] newElements = Arrays.copyOf(elements, len + cs.length);
//把cs数组元素复制到newElements，复制元素个数为cs.length
System.arraycopy(cs, 0, newElements, len, cs.length);
//把新数组的值赋值给数组的容器中
setArray(newElements);
}
return true;
} finally {
lock.unlock();
}
}可以看到，批量添加元素，当数组容器里面没有元素的时候，直接把新数组的值赋值给数组的容器中。而当数组容器里面有元素的时候，要进行两次拷贝操作。
1:根据指定数组索引位置删除的源码：
// 删除某个索引位置的数据
public E remove(int index) {
final ReentrantLock lock = this.lock;
// 加锁
lock.lock();
try {
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 {
// 如果删除的数据在数组的中间，分三步走
// 1. 设置新数组的长度减一，因为是减少一个元素
// 2. 从 0 拷贝到数组新位置
// 3. 从新位置拷贝到数组尾部
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}步骤分为三步
- 加锁；
- 判断删除索引的位置，从而进行不同策略的拷贝；
- 解锁
数组进行了两次拷贝
2:批量删除
// 批量删除包含在 c 中的元素
public boolean removeAll(Collection<?> c) {
if (c == null) throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
// 说明数组有值，数组无值直接返回 false
if (len != 0) {
// newlen 表示新数组的索引位置，新数组中存在不包含在 c 中的元素
int newlen = 0;
Object[] temp = new Object[len];
// 循环，把不包含在 c 里面的元素，放到新数组中
for (int i = 0; i < len; ++i) {
Object element = elements[i];
// 不包含在 c 中的元素，从 0 开始放到新数组中
if (!c.contains(element))
temp[newlen++] = element;
}
// 拷贝新数组，变相的删除了不包含在 c 中的元素
if (newlen != len) {
setArray(Arrays.copyOf(temp, newlen));
return true;
}
}
return false;
} finally {
lock.unlock();
}
}批量删除并不会直接对数组中的元素进行挨个删除，而是先对数组中的值进行循环判断，把不需要删除的数据放到临时数组中，最后临时数组中的数据就是不需要删除的数据
1:indexOf方法
// o：需要搜索的元素
// elements：搜索的目标数组
// index：搜索的开始位置
// fence：搜索的结束位置
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
// 支持对 null 的搜索
if (o == null) {
for (int i = index; i < fence; i++)
// 找到第一个 null 值，返回下标索引的位置
if (elements[i] == null)
return i;
} else {
// 通过 equals 方法来判断元素是否相等
// 如果相等，返回元素的下标位置
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}indexOf 方法的主要用处是查找元素在数组中的下标位置，如果元素存在就返回元素的下标位置，元素不存在的话返回 -1，不但支持 null 值的搜索，还支持正向和反向的查找。indexOf 方法CopyOnWriteArrayList 内部使用也比较广泛，比如在判断元素是否存在时（contains），在删除元素方法中校验元素是否存在时，都会使用到 indexOf 方法，indexOf 方法通过一次 for 循环来查找元素，在调用此方法时，需要注意如果找不到元素时，返回的是 -1。