-
前言
集合常见问题，其中 HashMap 很重要❗表示必掌握，❔表示基本不会问 -
更新
1 | 24.06.01 初始记录 |
Java 集合
集合分为单列集合 （collection） 和双列集合 （map）。单列集合又包括 List（可重复） 和 Set（不可重复），List 分为 ArrayList 和 LinkedList
单列集合是实现 Iterable 接口产成的对象，支持迭代器和增强 for。
迭代器 nkedList，Set 分为 HashSet 和 TreeSet。双列集合 Map 分为 TreeMap 和 HashMap
基础
所有的单列集合都可以使用迭代器，因为他们都继承了 Iterable 接口，这个接口里的 Iterator 方法可以返回一个 Iterator 对象，这个 Iterator 对象就是迭代器对象，底层针对不同类型的集合都写了不同的实现类，所以集合可以直接使用迭代器进行遍历查询。这种只需要提供一种方法（iterator 方法）访问一个容器对象中各个元素，而又不暴露该对象的内部细节的方式就是迭代器设计模式。
迭代器倒序
List 集合可以使用迭代器倒着遍历，ListIterator 有 previous() 方法和 hasprevious() 方法，可以自动指向并取出上一个元素。Set 集合不能用迭代器倒着遍历，但可以根据它的大小顺序倒着取出。
使用 foreach、iterator、for 有什么区别？效率上哪个更高？
区别上：
普通 for 循环一般用来处理比较简单的有序的，可预知大小的集合或数组.
foreach 可用于遍历任何集合或数组，而且操作简单易懂，唯一的不好就是需要了解集合内部类型，它的底层有函数式编程注解 @FunctionalInterface，也就是说它可以进行 Lamda 形式简写。
iterator 是最强大的，他可以随时修改或者删除集合内部的元素，并且是在不需要知道元素和集合的类型的情况下进行的，当你需要对不同的容器实现同样的遍历方式时，迭代器是最好的选择！
至于增强 for 和 iterator 其实是一样的，增强 for 编译后的.class 文件中，就是 iterator，所以二者除了写法是用第三方参数来表示，效率上没有任何区别。
效率上：
这个需要多方考虑，比如普通 for 循环用在数组是遍历最快的，它是直接获取数据，但普通 for 不能用在不知道长度的集合中，这就需要用 iterator 或者 foreach，相对来说，iterator 效率会高于 foreach，因为 foreach 在访问过程中产生一个额外的 Enumerator 对象，这个对象会进行版本检查处理，所以它是线安全的。
对于 ArrayList 来说，它是通过一个数组实现的，可以随机存取；但是 LinkedList 是通过链表实现的，当要遍历依个取出时，for 循环时要取的每个元素都必须从头开始遍历，而 iterator 遍历则从头开始，边遍历边取，取完只需要一次遍历，所以 for 循环需要的时间远远超过 foreach 循环。 对于数组来说，for 和 foreach 循环效率差不多，但是对于链表来说，for 循环效率明显比 foreach 低。
ArrayList 和 LinkedList 的底层原理
首先，List 集合是有序集合，即存取有序，List 集合的特点是存取顺序一致，存储元素可重复，都有索引。
ArrayList 的底层是数组，一个索引对应一个元素，所以查询速度快；但是在增删时，需要调整整组数据的移动，所以增删较慢。
而 LinkedList 的底层是双向链表，每次查询时都要从两头开始查询（离头近就从头查，离尾近就从尾查），所以查询较慢；但是增删时，只需要将链表头结点和尾结点指向新插入的结点即可，所以增删速度较快。
但如果是新增的数据量较大的情况下，ArrayList 的新增效率反面比 LinkedList 的效率更高。因为 ArrayListr 底层数组的扩容是 1.5 倍，数据量越大，扩容的速度就越快，而链表仍需一个个断开链接和重续新链接。
最后，jdk8 版还对 ArrayList 做了懒加载优化，在之前是构造 ArrayList 时就默认开辟 10 个空间，jdk8 之后变成了只有放入第 1 个元素时，才会开辟 10 个空间。
❗❗数组的起始长度是 0，在向数组中添加第一个元素时，数组容量扩为 10。 后续扩容因子为 1.5 倍。每次扩容都是复制到新的数组。
分别讲一下 Set 集合和 Tree 这种数据结构
Set 集合的特点是必须排序，没有索引，不可重复。Set 集合分为 HashSet 和 TreeSet，HashSet 底层使用的是哈希表，它的排序规则是按照底 Hash 函数决定的，无法人为设置；而 TreeSet 的底层则是使用红黑树，可以使用自然排序（自定义类中实现 Comparable 接口，重写 CompareTo 方法）或比较器排序（在创建 TreeSet 对象创建一个 Comparator 的匿名内部类，并重写 Compare 方法），扩容时通过结点链接。
TreeSet 使用 Iterator 遍历的过程是怎么样的？
因为 TreeSet 是按大小排序的，所以会根据从左往右，从下往上的顺序打印。
List 集合是线程不安全的，你是怎么使用 List 集合的呢？
使用 Collections 集合工具类，对集合进行同步处理：
1
2
3
List<String> list = Collections.synchronizedList(new ArrayList<>());
但是在多线程开发中，对其进行遍历，需要添加 synchronized 关键字，因为 List 的 add、index 等方法中都是带有 synchronized 关键字，但是在 iterator 中没有 synchronized 关键字。
HashMap
❗HashMap 底层的数据结构
数组 + 最简单 Hash 的原理。
对存入的 key 进行 hash 计算，根据计算出的 hash 值，对数组长度进行取模，获取到要存入的位置。
JDK8 以前，Hash 表的底层是【数组】+【链表】
JDK8 及之后，变成了【数组】+【链表】+【红黑树】
❗JDK 1.8 中对 hash 算法和寻址算法是如何优化的？
hash 算法：hash 值与 hash 值右移 16 位进行异或计算。得到结果位高 16 位 + 高 16 位与低 16 位的异或值。（这一步主要为了低 16 位在下一步寻址的时候，使低 16 位保留高 16 位的特征，减少哈希冲突）
寻址：(n - 1)&hash 算出数组内的一个位置。
为什么使用&运算不使用取模运算？
取模运算性能比较差，而且 (n - 1)&hash 的效果和 hash 对 n 取模，效果是一样的。
为什么效果是一样的？因为数组的长度一直是 2 的 n 次方，只要他保持数组长度是 2 的 n 次方，那么效果就是一样的。
❗HashMap 如何解决 hash 碰撞？
hash 冲突，链表 + 红黑树，O(n) 和 O(logn)
❗HashMap 如何进行扩容？
2 倍扩容。
扩容之后要进行 rehash。即 hash 值与新数组长度 (n - 1) 进行与操作。如果值与原来不一样，新的 index 就是 旧index + oldCap，通过这个方式，避免了 rehash 的时候，进行取模（效率不高）。
Hash 表中数组的初始化分手动初始化和自动初始化，自动初始化会在第一次插入元素时开辟空间，默认长度为 16，扩容因子为 0.75，每次扩容量为自身的 2 倍长度，扩容之后存入数组的新索引位置就会改变。手动初始化的话，可以在创建对象时自定义初始数组长度，但 HashMap 不一定会按自主设置的数值初始化数组，而按 2 的 n 次方创建。
HashMap1.7 版本的的扩容时是先判断是否达到阈值，达到先扩容，再添加元素，并且采用的是头插法，也就是旧元素挂在新元素下。而 HashMap1.8 的扩容时是先添加元素，然后判断是否达到阈值，达到阈值直接扩容，且使用的是尾插法，即新元素挂在旧元素下面。
初始化后，当存入新的键值对时，会先判断数组长度是否大于 64，再判断链表元素是否大于等于 8 ，如果两者都成立，链表会自动转换成红黑树，如果数组小于 64，会从第 9 个开始先扩容，直到数组长度大于等于 64 时，链表长度再增加，就会转为红黑树。
❔为什么要转为红黑树呢？
链表取一个数需要遍历链表，而红黑树相对效率要高。
❔为什么不直接使用红黑树呢？
HashMap 源码中有相关描述： “因为树节点的大小是链表节点大小的两倍，所以只有在容器中包含足够的节点保证使用时才用它”，显然尽管转为树使得查找的速度更快，但是在节点数比较小的时候，此时对于红黑树来说内存上的劣势会超过查找等操作的优势，自然使用链表更加好，但是在节点数比较多的时候，综合考虑，红黑树比链表要好。
❔为什么转为红黑树的条件是 8 而不是第 9 第 10 个呢？
源码中有对这个进行计算，正常的随机哈希码下，哈希冲突多到超过 8 个的概率不到千万分之一，几乎可以忽略不计了，再往后调整并没有很大意义。
如果哈希冲突有那么多，说明极大可能是人为设置，故意制造哈希冲突导致，这时候就转为化红黑树，来保证查询效率。
❔那什么时候退出红黑树呢？
当哈希冲突个数从第 8 个变到第 6 个时，红黑树转化为链表。
❔6 与 8 之间的第 7 个冲突时，会是什么状态？
分情况看。8 退 6，是红黑树转链表，6 进 8，是链表转红黑树，中间的 7 是防止频繁变动做的一个预留位，如果是 8 退 6，中间的 7 就是红黑树；如果是 6 进 8，中间的 7 就是链表。
为什么 1.7 是头插法，1.8 是尾插法？
1.7 版本使用头插法是因为头插法是操作速度最快的，找到数组位置就直接找到插入位置了，但这样插入方法在并发场景下会因为多个线程同时扩容出现循环列表，也就是 Hashmap 的死锁问题。（详细解释：[https://segmentfault.com/a/1190000024510131][https://segmentfault.com/a/1190000024510131]）
1.8 版本加入了红黑树来优化哈希桶中的遍历效率，相比头插法而言，尾插法在操作额外的遍历消耗（指遍历哈希桶）已经小很多，也可以避免之前的循环列表问题，同时如果已经变成红黑树了，也不能再用头插法了，而是按红黑树自己的规则排列了。
❗多线程下的 HashMap 线程安全吗？为什么？
HashMap 本身就是线程不安全的，多线程下，在添加元素时容易出现数据覆盖情况，而丢失数据，也可能在扩容时迁移数据出现数据覆盖情况，而丢失数据。
❗ConcurrentHashMap 实现线程安全的底层原理
JDK1.8 以前，多个数组，分段加锁，一个数组一个锁。他将一个大的 ConcurrentHashMap 分成 16 个小的 Segment。也就是说可以同时承受 16 个线程的并发。
JDK1.8 以后，数组里每个元素进行 put 操作，都是有一个不同的锁，对当个位置进行 put 操作时，采取的是 CAS 的策略。如果 CAS 操作失败，就使用 synchronized 对这个位置的对象进行锁定，然后基于链表或红黑树，对数组元素进行写入。