数组与集合区别

数组固定长度，集合动态改变

数组可以包含基本数据类型，集合只能包含对象

数组可以直接访问元素，集合需要通过迭代器或其他方法访问

集合族谱

在这些集合中，仅有 vector 和 hashtable 是线程安全的，其内部方法基本都有 synchronized 修饰。

ArrayList

底层采用 Object 数组实现，实现了 RandomAccess 接口因此支持随机访问。插入删除操作效率慢。

ArrayList 需要一份连续的内存空间。

ArrayList 扩容机制

ArrayList 添加元素时，若达到了内部数组指定的数量上限，会自动进行扩容：

1. 计算新容量，一般是原容量的 1.5 倍（1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数）
2. 根据新容量创建新数组
3. 把原来的数据拷贝到新数组中
4. 更新 ArrayList 内部指向原数组的引用，指向新数组

ArrayList 哪里不安全  

首先，对 arraylist 添加一个元素，分为 3 步

• 判断数组是否需要扩容，如果需要就调用 grow 方法扩容；

• 将数组的 size 位置设置值（因为数组的下标是从 0 开始的）；

• 将当前集合的大小+1

多线程插入删除下，ArrayList 会暴露三个问题：

• 出现 null 值：
  假设 arraylist 容量为 10，线程 1 检查当前 size=4，不需要扩容，于是在 index=4 进行插入，但是还没有 size++，线程 2 又来进行插入，检查不需要扩容且 size=4，于是也在 index=4 执行插入，然后两个线程同时执行 size++，就导致实际 size=6，两次插入都在 index=4，而 index=5 的地方并没有插入数据。
• 索引越界异常
  还是上述例子，假设线程 1 检查 size=9，没有到 10，无需扩容，于是在 index=9 的地方插入，但还没有 size++，线程 2 来检查 size=9，也在 index=9 的地方插入，然后两个线程同时++，导致 size=11。
• 集合的 size()和实际 add 数量不符
  size++不是原子操作，分为三步，获取 size 值、size+1、新 size 覆盖老 size，如果两个线程拿到一样的 size 同时覆盖，那么就导致有一次没加上。

为什么需要 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 标识未初始化的状态

• 确保第一次添加元素时数组的容量扩展：
  ArrayList 在没有明确指定容量时，会使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来标识该 ArrayList 尚未添加任何元素。这意味着，当创建一个空的 ArrayList 时，它的内部数组并不会立即分配实际的空间，而是会指向一个空的数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）。这节省了内存开销。
  当第一次往这个 ArrayList 中添加元素时，内部数组的大小就需要扩展。因为 ArrayList 的默认初始容量是 10，所以一旦添加元素，数组就会重新分配一个合适的大小（10）来存放这些元素。

• 避免不必要的内存分配：
  如果没有 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这种标识，ArrayList 每次创建时都会为空的实例分配一个固定大小的数组（比如长度为 10）占用内存。
  通过使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，ArrayList 会在初始化时使用一个空数组来表示尚未使用的状态，只有在第一次添加元素时，才会根据需要分配和扩展内部数组。这样可以节省内存开销。

• 区分“空的”实例和“已初始化但无元素”实例：

  DEFAULTCAPACITY_EMPTY_ELEMENTDATA 有一个特别的用途，就是帮助 ArrayList 区分两种不同的状态：

  • 空实例：=ArrayList  没有被初始化为一个非空的数组，只是一个空的实例。ArrayList list = new ArrayList<>();
  • 已初始化但无元素：ArrayList  已经分配了一个默认大小的数组，但当前还没有元素。ArrayList list = new ArrayList<>(10);

LinkedList

HashMap

• HashMap 可以存储 null 的 key 和 value,但 null 作为键（key 的哈希值为 0）只能有一个，null 作为值可以有多个。
• JDK1.8 之前 hashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)，如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是 O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。
• JDK1.8 后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于 8 并且数组长度大于等于 64 时，将链表转化为红黑树**，以减少搜索时间 O（logn），**但是在数量较少时，即数量小于 6 时，会将红黑树变回链表。
• HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且 HashMap 总是使用 2 的幂作为哈希表的大小。
• 解决哈希冲突的方法： _ 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。 _ 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。 _ 再哈希法：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存诸键值对。 _ 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap 哪里线程不安全

• JDK1.7 HashMap 采用数组+链表的数据结构，多线程背景下，HashMap 使用头插法插入元素，可能出现环形链表造成Entry 链死循环，多线程同时执行 put 操作，可能造成前一个 key 被后一个 key 覆盖，存在数据丢失问题。
• JDK1.8 HashMap 采用数组+链表+红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了 Entry 链死循环。但是多线程背景下，put 方法仍存在数据覆盖的问题。
  • Entry 死循环：扩容时存在在原数组和新数组之间的指针切换，如果没有正确地处理链表节点的 next 指针，就可能导致某些节点指向自己，从而形成死循环。
  • 数据丢失：扩容时HashMap 的元素会被重新散列并放入新的数组桶中。如果在处理过程中存在指针的错误（例如链表 next 指针没有正确地更新），就可能发生丢失元素的情况，某些元素可能无法在新的数组中找到正确的位置，导致这些元素丢失。
• 如果要保证线程安全，可以通过这些方法来保证：
  多线程环境可以使用Collections.synchronizedMap( )同步加锁的方式，但是这种方法是全局锁 synchronized，很影响性能，不如使用 ConurrentHashMap 的分段锁，更适合高并发场景使用。

HashMap 的 put 流程（jdk8）

1. 根据要添加的键的哈希码（hashcode 方法）得出在数组中的位置，即找到桶
2. 检查该位置是否为空（即没有键值对存在）
3. 若该位置已经存在其他键值对，检查该位置的键值对的键（equals 方法）是否与要添加的键值对相同，若相同则新值覆盖旧值。put 结束
4. 若和键值对的键不相同，则再遍历链表或红黑树（遍历桶）来查找是否有相同的键和值，若有，则新值覆盖旧值，若无，则新值加到链表或红黑树中。
5. 检查链表长度是否达到 8 且 HashMap 的数组长度是否大于等于 64，是则将链表转换为红黑树。
6. 检查负载因子是否超过阈值（默认为 0.75），若键值对的数量（size）与数组长度（初始 16）的比值大于阈值，则需要进行扩容操作。
7. 扩容操作：创建一个新的两倍大小的数组。将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。更新 HashMap 的数组引用和阈值参数。

HashMap 的 get 方法哪里不安全

• 空指针异常：在 HashMap 没有被初始化时如果尝试用 null 作为键调用 get 方法会抛出空指针异常。如果 HashMap 已经初始化，使用 null 作为键是允许的，因为 HashMap 支持 null 键。
• 线程安全：HashMap 本身不是线程安全的。例如在一个线程中调用 get 方法而另一个线程同时增加或删除元素，可能会导致读取操作得到错误的结果或抛出 ConcurrentModificationException。如果需要在多线程环境中使用类以 HashMap 的数据结构，可以考虑使用 ConcurrentHashMap。

HashMap 为啥用 String 作为 key

String 对象是不可变的，一旦创建就不能被修改，这确保了 Key 的稳定性。如果 Key 是可变的，可能会导致 hashCode 和 equals 方法的不一致，进而影响 HashMap 的正确性。

为什么 HashMap 要用红黑树而不是平衡二叉树

平衡二叉树追求的是一种**“完全平衡**”状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
红黑树不追求这种完全平衡状态，而是追求一种“弱平衡”状态：整个树最长路径不会超过最短路径的 2 倍，不会像平衡二叉树一样频繁左右旋，也就是栖牲了一部分查找的性能效率来换取一部分维持树平衡状态的成本。

HashTable

内部方法基本都经过 synchronized 修饰，不可以有 null 的 key 和 value。默认初始容量为 11，每次扩容变为原来的 2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap。

HashSet

底层由 HashMap 实现，key 就是 hashset 的值，所有的 key 的 value 相同，是一个名为 PRESENT 的 Object 类型常量。

LinkedHashSet

底层由 LinkedHashMap 实现，继承了 HashSet 类，使用双向链表维护元素插入顺序。

TreeSet 

底层由 TreeMap 实现（红黑树），添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序（自然顺序，比如插入 1，3，2，输出出来是 1，2，3）