Java 集合也叫作容器，就是专门用来存放对象的；也就是说，没有办法存放基础数据类型 int，必须要存放包装类 Integer。
Java 集合主要是由两大接口派生而来：一个是 Collecton 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。
对于 Collection 接口，下面又有三个主要的子接口：List 、 Set 和 Queue，如下图：
集合与数组的区别：
- 数组的长度是固定的，集合的长度不固定。
- 数组可以存储基本类型和引用类型，集合只能存储引用类型。
ArrayList
ArrayList 就是一个 非线程安全 的动态数组，并且允许元素为 null。
ArrayList 底层就是使用数组实现的，所以通过下标访问或修改快，尾部追加要看是不是需要扩容，需要扩容的话就慢。
1.数组用来做队列合适么？
ArrayList 不适合做队列，但是数组是非常合适的。比如 ArrayBlockingQueue 内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。
2.ArrayList 和 Vector 的区别？
主要区别就是 ArrayList 是非线程安全的，Vector 是线程安全的；它们的实现都是差不多的，都是使用 Object[] 数组存储元素，而且都可以返回 ListIterator<E> 迭代器。这两个集合都适用于查询比较多，增删比较少的情况。
下面是 ArrayList 的继承和实现：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
继承和实现图：
扩容逻辑
先来说说扩容，我个人将 ArrayList 的扩容方式分为两种：主动扩容和被动扩容：
- 主动扩容：调用 ensureCapacity(int) 方法
- 被动扩容：是调用 add、addAll、readObject 方法时，会判断需不需要扩容
但是扩容逻辑都是一样的，目标大小 - 集合长度 > 0 就说明需要扩容：
- 按照当前集合长度 * 1.5 算出一个新的集合长度，假设当前集合长度为 10，10 * 1.5 = 15。
- 在创建一个新数组，然后调用 System.arraycopy 方法，将旧数组中的元素拷贝到新数组中。
添加元素
- 使用 boolean add(E) 方法在尾部追加元素：先判断需不需要扩容，然后再把元素添加到
size + 1的下标位置。 - 使用 add(int, E) 在指定下标中插入元素：先判断需不需要扩容，然后从要插入的下标开始，使用 System.arraycopy 将原来的元素整体后移，最后将要插入的元素赋值给要插入的下标。
插入元素不一定比 LinkedList 慢，要看需不需要扩容。
移除元素
-
根据 E remove(int) 下标删除元素：从要删除的下标 + 1开始，使用 System.arraycopy 将原来的元素整体前移，最后将最后一个元素设置为 null。
-
根据 boolean remove(Object) 对象删除元素：通过 for 循环找到要删除的实例下标，然后从要删除的下标 + 1开始，使用 System.arraycopy 将原来的元素整体前移，最后将最后一个元素设置为 null。
删除集合中所有 null 元素
Java 8 方式：
List<Integer> listWithoutNulls = Lists.newArrayList(null, 1, 2, null, 3, null);
listWithoutNulls.removeIf(Objects::isNull);
LinkedList
LinkedList 使用 双向链表 的形式存放数据，非线程安全的，增删比较快，但是查询慢，因为要使用 for 循环遍历。
LinkedList 中有两个属性：
- first：头节点
- last：尾节点
每个节点也有两个属性：
- next：下一个节点
- prev：上一个节点
添加节点
-
在尾部追加元素：
添加第一个元素头尾节点都指向节点 1，节点 1 的上一个和下一个节点都为 null。
当添加节点2的时候，尾节点指向节点 2，节点 1 的下一个节点指向节点 2，节点 2 的上一个节点指向节点1。
-
在指定位置插入元素：假设链表中有两个节点，要在下标 1 的位置插入新节点 3
先通过 for 循环，获取出下标 1 的节点 2，然后节点 1 的下一个节点指向节点 3，节点 3 的上一个节点指向节点 1，下一个节点指向节点 2，然后节点 2 的上一个节点指向节点 3。
下面这张图是最终的执行结果图，节点 2 就是新节点，节点 3 就是上图的节点 2：
移除节点
-
通过下标移除元素：和在指定位置插入元素的操作相反。
-
通过对象移除元素：通过 for 循环从前面找到元素，修改左右两边元素的 next 和 prev。
获取节点
通过 get(int index) 方式获取节点时，先将集合大小（size）除以 2，如果参数 index 小于 除以 2 以后的值，就会从前向后迭代；否则就会从后向前迭代。
链表不能向数组一样可以随机访问，只能通过 foreach 循环或 Iterator 的方式获取。
ArrayList 与 LinkedList 区别？
1.ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。
2.ArrayList 底层适用数组，LinkedList 底层适用双向链表。
3.LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象（对应于 get(int) 方法）。
4.ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响；LinkedList 采用链表存储，所以如果是在头尾插入或者删除元素不受元素位置的影响。
ConcurrentHashMap
ConcurrentHashMap 就是一个线程安全的 HashMap，在 JDK 1.8 中取消了分段锁，而采用 Node + CAS + Synchronized 来保证线程安全。
HashTable 是在方法上使用 synchronized 关键字；HashMap 可以使用 Collections.synchronizedMap 进行包装，包装后也是使用 synchronized 关键字。
ConcurrentHashMap 的数据结构
在 JDK1.8 中，ConcurrentHashMap 采用数组+链表+红黑树的方式来实现数据存储，如下图：
在 JDK 1.8 中 ConcurrentHashMap 的数据结构和 HashMap 的数据结构是一样的，区别就是 HashMap 是非线程安全的。
在 JDK 1.7 中的数据结构是 数组+链表。
扩容还是转化为红黑树
当链表长度大于或者等于 8 时，ConcurrentHashMap 认为链表已经有点长了，需要考虑优化，有两种方式：
- 当数组长度大于等于 64，并且链表长度也大于等于 8 的时候，就会把链表转化为红黑树；当不满足的时候还会再转换为链表。
- 当数组长度小于 64，并且链表长度大于等于 8 的时候，会对数组进行扩容。
使用红黑树代替链表是为了加快，查找、插入和删除操作。
如何解决冲突
插入数据的时候会先获取 Key 的 hash 值，再计算出数组的下标。
- 没有哈希冲突，就直接放到数组中。
- 有哈希冲突，就会将下标对应的位置转换为链表，并追加到这个链表的后面。
因为 hashCode 相同，但是值不一定是相等（equals 方法比较）。
为什么负载因子是 0.75
负载因子决定了 HashMap 什么时候进行扩容，默认情况下是存储了 12（16 * 0.75 = 12）个元素后，就会自动扩容，扩容为原来容量的两倍。
ConcurrentHashMap 的负载因子不允许修改。
0.75 就是为了平衡空间利用率和时间效率：
-
就是说数组长度越长，发生哈希冲突的几率就越小，就导致了元素都分布在数组上，会提高查询、添加、删除的效率；但是有可能导致数组没有被占满，也就是浪费了一些内存。
假设负载因子为 0.25，当存储了 4 个元素的时候就会进行扩容。 -
相反的，数组越短，发生哈希冲突的几率就越大，就会导致链表过长，会降低查询、添加、删除的效率；但是不会浪费内存。
假设负载因子为 1，当存储了 16 个元素的时候才会进行扩容。