在Java编程语言中，集合（Collection）指的是存储一组对象的容器。Java提供了一套丰富的集合框架，以及包含在Java标准库中的集合类。这些集合类提供了各种功能和操作，可以方便地对一组对象进行管理和操作。
目录
一、集合框架
二、集合的特点
三、集合与数组的区别
四、集合框架的优点
五、常用的集合类
六、List、Set 和 Map 三者的区别
七、Arraylist底层数据结构
八、Vector底层数据结构
九、LinkedList底层数据结构
十、HashSet底层数据结构
十一、LinkedHashSet底层数据结构
十二、TreeSet底层数据结构
十三、HashMap底层数据结构
十四、LinkedHashMap底层数据结构
十五、HashTable底层数据结构
十六、线程安全的集合类
十七、确保集合不被修改
十八、Iterator有什么特点？如何使用
十九、边遍历边移除Collection 中的元素
二十、Iterator 和 Listlterator 的区别
二十一、遍历List有几种方式
二十二、for循环遍历List原理
二十三、增强型 for 循环遍历List原理
二十四、Iterator遍历List原理
二十五、ListIterator遍历List原理
二十六、ArrayList优缺点
二十七、数组与List转换
二十八、ArrayList 和 LinkedList区别
二十九、ArrayList 和Vector 区别
三十、ArrayList、LinkedList、Vector插入数据哪个快
三十一、多线程场景下如何使用ArrayList
三十二、ArrayList的 elementData加上 transient修饰
三十三、List 和 Set 的区别
三十四、HashSet的实现原理
三十五、HashSet如何检查重复元素
三十六、HashSet是如何保证数据不可重复
三十七、hashCode()与equals()
三十八、HashSet与 HashMap的区别
三十九、Hash算法
四十、链表
四十一、HashMap的实现原理
四十二、HashMap 在jdk1.7和jdk1.8的不同
四十三、红黑树
四十四、HashMap的 put方法的具体流程
四十五、HashMap扩容
一、集合框架
Java集合框架是Java编程语言中用于存储、操作和处理数据集合的一组类和接口的集合。它提供了一种灵活、高效的方式来组织和操作数据，适用于各种开发场景。Java集合框架位于java.util包中，核心的接口和类包括：
Collection接口：是所有集合类的根接口，定义了集合类的基本行为，如添加、删除、迭代等操作。它衍生出List、Set和Queue等子接口。
List接口：表示有序的集合，允许重复元素。常见的实现类包括ArrayList、LinkedList和Vector。
Set接口：表示不允许重复元素的集合。常见的实现类包括HashSet、TreeSet和LinkedHashSet。
Map接口：表示键值对的集合。常见的实现类包括HashMap、TreeMap和LinkedHashMap。
Java集合框架支持泛型，因此能够安全、方便地存储各种类型的对象。它还提供了丰富的算法和工具类，用于对集合进行常见的操作，如排序、搜索和转换等。此外，Java集合框架还在Java 8中引入了Stream API，使得对集合进行函数式操作变得更加简单和灵活。
总的来说，Java集合框架为开发人员提供了丰富的工具和接口，可以满足各种数据处理需求，是Java编程中不可或缺的一部分。
二、集合的特点
Java集合框架具有以下特点：
统一的接口和类：Java集合框架定义了一组一致的接口和类，使得不同类型的集合可以使用相同的方式进行操作和管理。这种统一性使得代码更具可读性和可维护性。
动态可变大小：Java集合框架中的集合可以根据需要自动扩展或缩小大小，无需手动管理容量。这使得集合能够适应不同数据量的存储需求。
泛型支持：Java集合框架支持泛型，可以在集合中存储指定类型的对象，并在编译时进行类型安全检查。这有助于避免运行时出现类型错误。
多样化的集合类型：Java集合框架提供了多种类型的集合，包括List、Set、Map等，以满足不同的需求。每种类型都具有不同的特征和适用场景，开发者可以根据具体需求选择合适的集合类型。
简化的操作和算法：Java集合框架提供了丰富的操作和算法，如遍历、排序、搜索等，以方便地对集合进行常见操作。这些操作和算法被封装在集合类中，可以直接调用，避免了手动实现复杂的操作。
高性能和效率：Java集合框架经过优化，提供了高性能和高效的数据存储和检索能力。例如，ArrayList在随机访问时效率较高，而LinkedList在插入和删除时更快。
线程安全性：Java集合框架中的某些实现类，如Vector和Hashtable，具有线程安全的特性。此外，还可以通过使用Java.util.concurrent包下的并发集合类来实现线程安全的集合操作。
总的来说，Java集合框架提供了一套功能丰富、方便使用的工具和接口，使得数据的存储、操作和处理变得更加简单和高效。
三、集合与数组的区别
Java集合与数组在以下几个方面有区别：
动态性：数组在创建时需要指定固定的大小，之后无法改变。而集合框架中的集合类具有动态可变大小的特性，可以根据需要自动扩展或缩小大小。
类型灵活性：数组可以保存同一类型的元素，如int、String等，但类型必须相同。而集合框架支持泛型，可以存储不同类型的对象，提供了更大的灵活性。
功能和操作：集合框架提供了丰富的操作和算法，如添加、删除、搜索、排序等，更方便地对集合进行操作。而数组的操作相对简单且有限，需要手动实现一些功能，如迭代、扩展等。
扩展性：集合框架提供了多种类型的集合，如List、Set、Map等，每种类型都有不同的特性和适用场景，能够满足不同的需求。而数组的功能相对有限，只能保存一维或多维的元素。
容量管理：数组在创建时需要指定固定的容量，并且无法自动扩展。而集合框架中的集合类可以根据需要动态调整容量，无需手动管理。
集合类的封装和功能扩展：集合框架中的集合类具有更高层次的封装和抽象，隐藏了底层数据结构和算法的细节，提供了更多的功能和操作。而数组需要手动实现相关的功能和算法。
总的来说，集合框架相比数组具有更多的功能、更大的灵活性和更高的扩展性，适用于各种复杂的数据存储和操作需求。而数组更适合简单的、固定大小的元素存储和操作。在实际开发中，根据具体需求选择使用数组还是集合框架来存储和操作数据。
四、集合框架的优点
使用Java集合框架有以下优点：
功能丰富：Java集合框架提供了多种类型的集合类，如List、Set、Map等，每种类型都有不同的特性和适用场景。它还包含了丰富的操作和算法，如排序、搜索、迭代等，大大简化了开发过程。
高度可扩展：Java集合框架支持泛型，可以存储不同类型的对象，且具有动态可变大小的特性，可以根据需要自动扩展或缩小大小。这使得集合框架非常适合处理各种复杂的数据结构和需求。
类型安全性：使用Java集合框架能够在编译时进行类型检查，确保存储和访问的是正确的数据类型，减少运行时错误的可能性。
线程安全性：Java集合框架中的某些实现类，如Vector和Hashtable，具有线程安全的特性。此外，还可以使用java.util.concurrent包下的并发集合类，实现线程安全的集合操作。
效率和性能：Java集合框架经过优化，提供高效的数据存储和检索能力。例如，ArrayList在随机访问时效率较高，而LinkedList在插入和删除时更快。
代码简洁性和可读性：Java集合框架的接口和类具有统一的命名和使用方式，使得代码更加简洁和易读。开发人员无需手动实现基本的数据结构和操作，只需调用集合框架提供的方法即可。
广泛支持和社区支持：Java集合框架是Java标准库中的一部分，被广泛使用，有许多开源库和工具都依赖于集合框架。这也意味着在使用集合框架时可以获得社区的支持和各种优秀的第三方库。
总的来说，Java集合框架提供了功能丰富、高效、类型安全和可扩展的数据结构和操作，极大地简化了开发过程，提高了代码的可读性和可维护性，是Java开发中不可或缺的重要组成部分。
五、常用的集合类
Java集合框架提供了丰富的集合类，以下是常用的一些集合类：
ArrayList：基于数组实现的动态数组，可以存储任意类型的对象，支持快速随机访问。
LinkedList：基于链表实现的双向链表，可以高效地进行插入和删除操作，但访问速度较慢。
HashSet：基于哈希表实现的集合，不允许重复元素，并且无序。
TreeSet：基于红黑树实现的有序集合，元素按照自然顺序或自定义比较器进行排序。
HashMap：基于哈希表实现的键值对集合，使用键来进行快速查找和存储。
TreeMap：基于红黑树实现的有序键值对集合，键按照自然顺序或自定义比较器进行排序。
LinkedHashMap：基于哈希表和双向链表实现的有序键值对集合，保持插入顺序或访问顺序。
HashSet和HashMap的并发安全版本有LinkedHashSet和ConcurrentHashMap。
Stack：基于数组或向量实现的栈，遵循后进先出（LIFO）原则。
Queue：队列的接口，常用实现类有LinkedList实现的Queue和PriorityQueue。
PriorityQueue：基于堆实现的优先级队列，按照元素的优先级进行排序。
Hashtable：废弃的哈希表实现的键值对集合，与HashMap类似但是线程安全。
上述是一些常见的Java集合类，每种类别都有特定的用途和适用场景。开发者可以根据实际需求选择合适的集合类来存储和操作数据。
六、List、Set 和 Map 三者的区别
LIst：
List 是一个有序集合，可以包含重复元素。它继承自 Collection 接口，允许根据索引位置访问元素，提供了一系列与位置相关的操作方法，如添加、删除、获取指定位置的元素等。
常见的 List 实现类有 ArrayList、LinkedList 和 Vector 等。Set：
Set 是一个不允许包含重复元素的集合，不保证元素的顺序。它继承自 Collection 接口，主要用于存储不重复的对象。
常见的 Set 实现类有 HashSet、LinkedHashSet（保持插入顺序）和 TreeSet（有序集合）等。- Map：
Map 是一种键值对的集合，每个键对应一个值，键不允许重复，但值可以重复。Map 不继承自 Collection 接口。它提供了根据键来查找值的功能。
常见的 Map 实现类有 HashMap、LinkedHashMap（保持插入顺序）和 TreeMap（按照键的自然顺序或自定义比较器排序）等。总的来说，List 是有序集合，可以包含重复元素；Set 是不允许包含重复元素的集合，不保证顺序；Map 是键值对的集合，键不允许重复，值可以重复。在实际开发中，根据数据存储和操作的需求，可以选择合适的集合类型来实现相应的功能。
七、Arraylist底层数据结构
ArrayList 的底层数据结构是数组，具体来说是一个 Object 类型的数组。在 ArrayList 内部，它通过数组来存储元素，数组的长度是可变的。空具有以下特点：
动态增长：ArrayList 的大小是动态增长的，当添加元素超出当前容量时，其容量会自动增加。这使得它适用于需要动态管理数据集的情况。
随机访问效率高：由于 ArrayList 基于数组实现，所以支持按索引进行快速随机访问。对于获取元素和修改元素来说，ArrayList 的性能非常高，时间复杂度为 O(1)。
非线程安全：ArrayList 不是线程安全的，如果多个线程同时访问同一个 ArrayList 实例并且其中至少有一个线程会修改列表的结构（增加或删除元素），那么必须在外部进行同步。
可以存储重复元素和 null：ArrayList 中允许存储重复的元素，也允许存储 null 值。
插入和删除效率较低：由于 ArrayList 是基于数组实现的，当需要在中间或起始位置插入或删除元素时，需要对元素进行位移操作，因此插入和删除操作的效率较低，时间复杂度为 O(n)。
当我们向 ArrayList 中添加元素时，它会将元素存储在数组中，并根据需要自动扩展数组的大小。默认情况下，ArrayList 会初始化一个大小为 10 的数组，当元素数量超过当前数组大小时，它会创建一个新的更大的数组，并将所有元素从旧数组复制到新数组中。这个过程被称为扩容。
ArrayList底层使用一个Object数组来存储元素，数组的大小可以动态调整。当需要添加
需要注意的是，由于 ArrayList 的底层是数组，它在插入或删除元素时会导致一些元素的移动，时间复杂度为O(n)，其中n为数组的大小，这可能会带来性能开销。因此，在需要频繁执行插入或删除操作的情况下，可能选择其他数据结构，如 LinkedList。LinkedList 是基于链表实现的，插入和删除操作的性能更高，但随机访问的性能较差。
ArrayList 的底层数据结构是一个可变大小的数组，它在处理随机访问元素时效率较高，但在插入和删除操作时可能会有性能开销。
八、Vector底层数据结构
Vector的底层数据结构是动态数组。与ArrayList类似，Vector也实现了动态数组的功能，但其实现方式略有不同。它具有以下特点：
线程安全性：Vector 是线程安全的，这意味着它的方法都是同步的，多个线程可以安全地同时访问一个 Vector 实例。这种线程安全性是通过在每个方法上使用 synchronized 关键字来实现的。
动态增长：与数组不同，Vector 的容量是动态增长的。当向 Vector 中添加元素时，如果其容量不足，它的容量会自动增加，这样就不需要手动管理容量。
遗留类：由于其线程安全性和动态增长的特性，Vector 在早期的 Java 版本中被广泛使用。然而，随着 Java 集合框架的引入，通常推荐使用更现代的集合实现，如 ArrayList 或 LinkedList。
性能：由于 Vector 的方法都是同步的，它的性能通常比 ArrayList 要差。在单线程环境中，推荐使用 ArrayList 而不是 Vector。
Vector底层使用一个Object数组来存储元素，数组的大小也可以动态调整。当需要添加元素时，Vector会自动扩展数组的大小，并在数组中添加新元素。当需要删除元素时，Vector会自动缩小数组的大小。
与ArrayList相比，Vector提供了更多的同步机制，可以在多线程环境下安全地使用。当多个线程同时访问Vector时，Vector会自动进行同步处理，以保护数据的一致性。
由于Vector底层使用动态数组，因此它的插入、删除等操作的时间复杂度也为O(n)，其中n为数组的大小。但是，由于其支持动态调整大小，因此在添加和删除元素时，Vector的性能通常优于静态数组。
九、LinkedList底层数据结构
LinkedList的底层数据结构是双向链表。它具有以下特点：
动态性：LinkedList 是一种动态数据结构，它能够根据需要动态地增加或删除元素。与静态数据结构相比，如数组，LinkedList 不需要提前指定容量大小，可以根据实际需求进行扩展或收缩。
链式结构：LinkedList 使用链式结构来存储和组织元素。每个节点包含了存储的元素和指向下一个节点的引用。由于每个节点都包含了指向下一个节点的引用，LinkedList 支持高效的插入和删除操作。
插入和删除操作效率高：相较于 ArrayList，LinkedList 在插入和删除元素时更高效。因为 LinkedList 的插入和删除操作只需要修改相邻节点的引用即可完成，而不需要像数组一样移动元素。当需要频繁地执行插入和删除操作时，LinkedList 是一个更好的选择。
随机访问效率较低：由于 LinkedList 是通过节点间的引用链接进行存储的，所以要访问列表中的任意位置元素时，需要从头节点开始遍历直到目标位置。因此，LinkedList 的随机访问效率较低，时间复杂度为 O(n)，其中 n 是要访问的元素的索引。
占用额外内存：LinkedList 在存储每个元素时需要为其分配一个节点对象，并且还需要维护节点间的引用关系，因此相对于基于数组的数据结构来说，LinkedList 会占用更多的内存空间。
双向链表是一种链式数据结构，每个节点包含数据域和两个指针域。一个指针指向下一个节点，另一个指针指向前一个节点。通过这两个指针，可以方便地在链表中任意位置插入或删除节点。
LinkedList实现了Deque接口，支持在链表头部和尾部进行插入和删除操作，因此在需要频繁进行头部和尾部操作的情况下，LinkedList的性能通常优于单向链表。
此外，LinkedList还提供了其他的操作，如添加元素、删除元素、获取元素等，这些操作的时间复杂度均为O(1)。
LinkedList底层数据结构是双向链表，支持在链表头部和尾部进行插入和删除操作，并提供其他相关操作。
十、HashSet底层数据结构
HashSet的底层数据结构是哈希表。它具有以下特点：
唯一性：HashSet 不允许存储重复的元素。当尝试将重复元素添加到 HashSet 中时，添加操作将被忽略。
无序性：HashSet 不保留元素的插入顺序或排序顺序。当你迭代 HashSet 中的元素时，元素的顺序是不确定的，因为它是根据元素的哈希值存储在内部哈希表中的。
高效性：HashSet 的查找、插入和删除操作的时间复杂度是固定的 O(1)。它是通过哈希表实现的，使用哈希算法将元素散列到桶中，从而实现快速的元素查找和插入操作。
不允许存储空值：HashSet 不允许存储 null 值。你可以存储其他类型的 null 引用，但只能有一个 null 元素。
哈希表是一种通过哈希函数将键映射到桶中的数据结构，它使用哈希算法将键转换为数组的索引。在HashSet中，每个元素都存储在一个哈希表中，以便能够快速地进行添加、删除和查找操作。
哈希表主要由数组和链表组成。数组是哈希表的基本存储结构，每个数组元素可以存储一个链表的头节点。当发生哈希冲突时，即两个不同的键被映射到同一个索引上时，哈希表会在该索引处创建一个链表，并将冲突的元素添加到链表中。
在Java中，HashSet底层使用HashMap实现，HashMap的键即为HashSet中的元素，而值则为一个默认的静态的Object对象常量(PRESENT)。由于HashSet不允许存储重复元素，因此在添加元素时，HashSet会通过哈希函数计算元素的哈希码，并使用该哈希码在哈希表中查找元素是否存在。如果存在则不进行添加，否则将元素添加到链表的头部。在删除元素时，HashSet同样会根据元素的哈希码在哈希表中查找元素，并将找到的元素从链表中删除。
HashSet底层数据结构是哈希表，它使用哈希算法将键映射到数组的索引上，并在发生哈希冲突时使用链表解决冲突。这种数据结构能够快速地进行添加、删除和查找操作。
十一、LinkedHashSet底层数据结构
LinkedHashSet底层数据结构是哈希表和双向链表。它具有以下特点：
有序性：LinkedHashSet 保持插入顺序，因此元素被迭代的顺序与它们被插入的顺序相同。这是通过维护一个双向链表实现的，链表中的每个节点都保存了前一个节点和后一个节点的引用。
唯一性：LinkedHashSet 和 HashSet 一样，不允许存储重复的元素。当尝试将重复元素添加到 LinkedHashSet 中时，添加操作将被忽略。
高效性：LinkedHashSet 的查找、插入和删除操作的时间复杂度是固定的 O(1)。它是利用哈希表和双向链表相结合的数据结构实现的，哈希表用于实现快速的哈希查找和插入操作，而双向链表用于保持元素的顺序。
继承性：LinkedHashSet 继承自 HashSet，因此它拥有 HashSet 具备的所有特性，比如快速的元素查找和删除，以及通过哈希算法来确定元素的存储位置等。
哈希表用于快速查找元素，而双向链表则用于维护元素的插入顺序。
当向LinkedHashSet中添加元素时，首先会通过哈希函数计算元素的哈希码，并使用该哈希码在哈希表中查找元素是否存在。如果存在则不进行添加，否则将元素添加到双向链表的头部。在删除元素时，同样会根据元素的哈希码在哈希表中查找元素，并将找到的元素从双向链表中删除。
由于LinkedHashSet维护了元素的插入顺序，因此可以通过遍历链表来按照插入顺序访问元素。此外，由于哈希表的存在，LinkedHashSet的插入、删除和查找操作的时间复杂度均为O(1)。
总的来说，LinkedHashSet底层数据结构是哈希表和双向链表的结合，它结合了哈希表的快速查找和双向链表的插入顺序维护功能。
十二、TreeSet底层数据结构
TreeSet 的底层数据结构是基于红黑树（Red-Black Tree）实现的。红黑树是一种自平衡的二叉搜索树，它具有以下特性：
- 每个节点都有一个颜色，红色或黑色。
- 根节点是黑色的。
- 所有叶子节点（NIL 节点）都是黑色的。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的。
- 对于每个节点，从该节点到其子孙节点的所有简单路径上，包含相同数目的黑色节点。
通过使用红黑树作为底层数据结构，TreeSet 可以实现有序的插入、删除和查找操作。红黑树的自平衡性质使得树的高度始终保持在 O(log N) 的范围内，因此这些操作的时间复杂度也是 O(log N)。
当我们将元素添加到 TreeSet 中时，它会根据元素的自然顺序或者提供的 Comparator 接口来进行排序，并将元素插入到红黑树的正确位置上。
需要注意的是，由于 TreeSet 是基于红黑树实现的，所以元素需要是可比较的或者提供自定义的比较器，以便确定元素的顺序。TreeSet 的底层数据结构是红黑树，这使得它能够提供高效的有序插入、删除和查找操作。
十三、HashMap底层数据结构
HashMap 的底层数据结构是哈希表（Hash Table）。它具有以下特点：
高效的存储和检索：HashMap 使用哈希表作为底层数据结构，通过键的哈希值来确定存储和检索的位置，因此在大多数情况下，插入、删除和获取元素的时间复杂度接近于 O(1)。
支持存储 null 值和 null 键：HashMap 允许存储 null 值作为键和值。通过判断键是否为 null 来确定桶的位置，并将 null 值存储在特殊的桶中。
不保证元素的顺序：HashMap 不保证元素的存储顺序，当对 HashMap 进行遍历时，所得到的元素顺序往往是不确定的。如果需要有序的遍历，可以考虑使用 LinkedHashMap。
非线程安全：HashMap 是非线程安全的，如果在多个线程中同时访问和修改 HashMap 实例，可能会导致数据不一致或出现其他问题。如果需要在多线程环境中使用，可以考虑使用 ConcurrentHashMap。
动态扩容：当 HashMap 中的元素数量超过负载因子（默认为 0.75）与当前容量的乘积时，HashMap 会自动进行扩容，将容量增加一倍，并重新计算元素的位置，以保持较低的哈希冲突率。
哈希表是一种根据键（Key）直接访问值（Value）的数据结构，它通过哈希函数将键映射到一个索引位置上，然后将值存储在该索引位置上。HashMap 内部使用数组来实现哈希表，数组的每个元素都是链表或红黑树的头节点，每个节点都包含一个键值对。
当需要添加或获取一个键值对时，HashMap 首先根据键的哈希值计算出数组索引位置，然后在该位置上进行操作。若索引位置上没有元素，则直接添加键值对；若有元素，则遍历链表或红黑树进行查找、更新或插入操作。为了提高性能，当链表上的节点数量过多（默认阈值为 8），链表会自动转换为红黑树结构，以提高查找效率。
哈希表的优势在于，通过哈希函数，可以快速定位和访问元素，使得插入、删除和查找键值对的时间复杂度近似为 O(1)。然而，如果哈希函数设计不当，或者哈希冲突发生较多，会导致链表过长，影响操作效率和性能。为了减少冲突，HashMap 会在数组长度达到一定阈值（默认为 0.75）时进行扩容操作，扩大数组的容量，重新计算元素的位置，以降低冲突的概率。
HashMap 底层使用哈希表实现，通过哈希函数将键映射到数组的索引位置上，然后使用链表或红黑树处理哈希冲突。哈希表的特点是高效的插入、删除和查找操作，但哈希冲突会影响性能。
十四、LinkedHashMap底层数据结构
LinkedHashMap 是 Java 中的一种特殊 Map 实现，它基于哈希表与双向链表组合而成。
LinkedHashMap 的底层数据结构由一个哈希表和一个双向链表组成。哈希表用于快速定位元素，而双向链表用于维护元素的插入顺序或者访问顺序，这取决于创建 LinkedHashMap 时使用的构造函数。它具有以下特点：
保持插入顺序或访问顺序：LinkedHashMap 可以通过构造函数指定保持插入顺序或按照访问顺序进行遍历。在保持插入顺序的情况下，遍历 LinkedHashMap 时将按照插入顺序进行。在按访问顺序的情况下，遍历 LinkedHashMap 时将按照元素的访问顺序进行，每次访问一个元素，该元素会被移动到链表的尾部。
额外的链表结构：LinkedHashMap 中通过双向链表来维护元素的顺序，这使得它相比于普通的 HashMap 多了一个维护顺序的开销，但也提供了按顺序遍历的便利性。
高效的存储和检索：与 HashMap 类似，LinkedHashMap 仍然使用哈希表来实现快速的存储和检索操作，因此在大多数情况下，插入、删除和获取元素的时间复杂度接近于 O(1)。
非线程安全：与 HashMap 相同，LinkedHashMap 也是非线程安全的。如果在多个线程中同时访问和修改 LinkedHashMap 实例，可能会导致数据不一致或出现其他问题。
LinkedHashMap 使用哈希表与双向链表组合而成，能够保持插入顺序或访问顺序，并提供了高效的存储和检索操作。然而，需要注意的是它也不是线程安全的。
十五、HashTable底层数据结构
HashTable 是 Java 中用于存储键值对的数据结构，底层数据结构是基于哈希表实现的。
底层数据结构：底层数据结构主要是由一个数组和链表构成。在 HashTable 的实现中，使用了一个数组存储元素，当发生哈希冲突时，会使用链地址法（Separate Chaining）来解决，即在数组的每个位置上都存储一个链表，用于存储具有相同哈希值的元素。它有以下特点：
线程安全：HashTable 是线程安全的，这是与 HashMap 的一个重要区别，通过在方法级别加锁来实现线程安全，但由于锁的存在，其在并发环境下的性能通常不如 ConcurrentHashMap。
不允许 null 键和 null 值：与 HashMap 不同，HashTable 不允许 null 键和 null 值的存在，存储 null 键或值时会抛出 NullPointerException。
遍历顺序不确定：与 LinkedHashMap 不同，HashTable 不保证元素的顺序，其内部结构并不维护元素的插入顺序或访问顺序。
初始容量和装载因子：类似于 HashMap，HashTable 也有初始容量和装载因子的概念。当 HashTable 中的元素数量超过装载因子与当前容量的乘积时，HashTable 会自动进行扩容操作，将容量增加一倍，并重新计算元素的位置，以保持较低的哈希冲突率。
HashTable 使用基于哈希表的数据结构实现了键值对的存储，是线程安全的，并且不允许存储 null 键和 null 值。然而，由于其在方法级别加锁，可能导致并发性能不佳。HashTable 的遍历顺序是不确定的，且在容量不足时会自动进行扩容。
十六、线程安全的集合类
以下有一些集合类是线程安全的，它们可以在多线程环境下安全地使用，而不需要额外的同步措施。以下是一些常见的线程安全的集合类：
ConcurrentHashMap：ConcurrentHashMap 是线程安全的哈希表实现，它通过分段锁（Segment）来实现线程安全，能够在高并发情况下提供较好的性能。
CopyOnWriteArrayList：CopyOnWriteArrayList 是一个线程安全的动态数组，它在对集合进行修改（添加、删除、更新）时，并不直接修改原始数组，而是对一个新的数组进行操作，因此适合于读操作远远多于写操作的场景。
CopyOnWriteArraySet：CopyOnWriteArraySet 是线程安全的集合类，内部使用 CopyOnWriteArrayList 来实现线程安全。
ConcurrentSkipListMap 和 ConcurrentSkipListSet：这两个类分别是基于跳表（SkipList）实现的线程安全的有序映射和有序集合。
ConcurrentLinkedQueue 和 ConcurrentLinkedDeque：这两个类是线程安全的基于链表实现的队列和双端队列。
BlockingQueue 的实现类（比如 ArrayBlockingQueue、LinkedBlockingQueue 等）：BlockingQueue 表示一个阻塞队列，其实现类通常是线程安全的，并且会提供在队列为空或者满时进行阻塞的功能。
这些线程安全的集合类提供了在多线程环境下使用的方便和安全性，但在使用时仍需注意具体的使用场景和线程安全特性，以充分发挥其优势并避免潜在的问题。
十七、确保集合不被修改
想确保集合不被修改，可以采取以下几种方法：
使用不可变集合：使用不可变集合（Immutable Collection）是最简单也是最安全的方法。不可变集合在创建后不能被修改，任何修改操作都会返回一个新的集合。Java中提供了一些不可变集合的实现类，如
Collections.unmodifiableList(),Collections.unmodifiableSet(),Collections.unmodifiableMap()等。这样，当你需要确保集合不被修改时，可以使用这些不可变集合。使用只读迭代器：如果你有一个可变的集合，并且不想让其他地方修改它，可以使用只读迭代器。只读迭代器通过
iterator()方法返回，它可以遍历集合，但不能执行修改操作。在这种情况下，其他代码将无法通过迭代器修改集合。使用同步措施：如果你无法使用不可变集合或只读迭代器，你可以在多线程环境下使用同步措施来保护集合的访问和修改操作。在Java中，可以使用
synchronized关键字或ReentrantLock等同步机制来确保多个线程安全地访问和修改集合。通过在修改集合的临界区代码上添加同步措施，可以防止并发修改导致的不一致性或抛出异常。需要注意的是，不可变集合和只读迭代器只适用于一些特定的场景，如果你需要频繁地修改集合，或者需要在多个线程之间修改集合，使用同步措施是更合适的选择。但请注意，使用同步措施可能会引入性能开销，并且需要额外的注意力来确保正确使用，以避免潜在的死锁和竞态条件问题。
确保集合不被修改可以使用不可变集合、只读迭代器或者同步措施。选择适合场景的方法能够提供集合的安全性和一致性。
十八、Iterator有什么特点？如何使用
Iterator 是 Java 集合框架中用于遍历集合元素的接口。它具有以下特点：
单向遍历：Iterator 仅支持单向遍历，即只能按照前向方向进行遍历，不支持逆向遍历。
只读访问：Iterator 接口只提供了读取元素的方法，不支持对集合进行修改。如果需要修改集合，需要使用集合特定的方法（如 add、remove 等）。
快速失败机制：Iterator 通过快速失败机制（fail-fast）来检测集合在遍历过程中是否被修改。如果在遍历过程中集合被并发修改，会抛出 ConcurrentModificationException 异常。
示例：
调用集合对象的
iterator()方法获取 Iterator 实例。例如：List<Integer> list = new ArrayList<>(); Iterator<Integer> iterator = list.iterator();使用
hasNext()方法检查是否还有下一个元素。这是一个布尔类型的方法，用于判断是否还有元素可以获取。例如：while (iterator.hasNext()) { // 遍历操作 }调用
next()方法获取下一个元素并进行处理。例如：Integer element = iterator.next(); // 对 element 进行操作如果需要，可以使用
remove()方法从集合中删除刚刚遍历过的元素。例如：iterator.remove();需要注意的是，在使用 Iterator 进行集合遍历时，如果在遍历过程中修改了集合（通过集合自身的方法进行修改），会触发快速失败机制，抛出 ConcurrentModificationException 异常。因此，如果需要在遍历过程中修改集合，应该使用集合特定的方法而非 Iterator 的方法。
Iterator 是用于遍历集合元素的接口，具有单向遍历、只读访问和快速失败机制的特点。使用 Iterator 进行集合遍历的步骤包括获取 Iterator 实例、使用
hasNext()判断是否还有下一个元素、使用next()获取下一个元素并处理，以及可选的使用remove()删除元素。注意在遍历过程中避免修改集合，否则会触发快速失败机制。
十九、边遍历边移除Collection 中的元素
边遍历边移除 Collection 中的元素是一个比较棘手的问题，因为在使用 Iterator 进行遍历时，直接使用 Collection 的 remove 方法会导致 ConcurrentModificationException 异常。这是由于 Iterator 在遍历过程中会进行快速失败机制的检测，一旦集合被修改，就会抛出异常。
为了边遍历边移除元素，可以使用 Iterator 的 remove 方法来删除元素。它是 Iterator 接口提供的支持安全删除元素的方法，可以避免 ConcurrentModificationException 异常的发生。下面是一种常见的使用方式：
Iterator<Integer> iterator = collection.iterator(); while(iterator.hasNext()) { Integer element = iterator.next(); if(condition) { iterator.remove(); // 使用 Iterator 的 remove 方法删除当前元素 } }在上述示例中，我们使用了 Iterator 的 remove 方法来删除满足特定条件的元素。这样可以确保元素的删除操作与集合的遍历过程是安全和兼容的。
需要注意的是，边遍历边移除的过程中，应该使用 Iterator 的 remove 方法来操作删除，而不要直接使用集合自身的 remove 方法。直接使用集合自身的 remove 方法可能会导致并发修改异常。
为了边遍历边移除 Collection 中的元素，可以使用 Iterator 的 remove 方法来删除元素。这样能够避免 ConcurrentModificationException 异常的发生，并确保删除操作与集合的遍历过程兼容和安全。
二十、Iterator 和 Listlterator 的区别
Iterator 和 ListIterator 都是 Java 集合框架中用于遍历集合元素的接口，但它们有以下几点区别：
遍历方向：Iterator 仅支持单向遍历，即只能按照前向方向进行遍历。而 ListIterator 支持双向遍历，既可以向前遍历也可以向后遍历。
元素访问能力：Iterator 接口只提供了读取元素的方法，即通过
next()来获取下一个元素。而 ListIterator 可以在遍历的同时修改 List 中的元素，包括添加、删除和修改元素。索引访问：ListIterator 具有额外的索引访问能力，可以通过
nextIndex()和previousIndex()获取当前元素的索引位置。这使得 ListIterator 在遍历和访问具有顺序的 List 集合时更加方便。集合类型限定：Iterator 接口可以用于任何集合类型的遍历，包括 List、Set 和 Map 等。而 ListIterator 接口仅适用于实现了 List 接口的集合类，如 ArrayList、LinkedList 等。
使用 Iterator 进行集合遍历的常见步骤如下：
Iterator<Integer> iterator = collection.iterator(); while(iterator.hasNext()) { Integer element = iterator.next(); // 处理元素逻辑 }使用 ListIterator 进行集合遍历的常见步骤如下：
ListIterator<String> listIterator = list.listIterator(); while(listIterator.hasNext()) { String element = listIterator.next(); // 处理元素逻辑 }Iterator 和 ListIterator 是用于遍历集合元素的接口，它们的区别在于遍历方向、元素访问能力、索引访问和适用的集合类型。Iterator 仅支持单向遍历和读取元素，适用于任何集合类型；而 ListIterator 支持双向遍历、元素的添加、删除和修改，并且仅适用于实现了 List 接口的集合类。根据使用场景和需求，可以选择适合的遍历接口来操作集合元素。
二十一、遍历List有几种方式
遍历 List 集合有多种方式，包括以下几种：
使用 for 循环：使用传统的 for 循环可以依次遍历 List 的每个元素。例如：
for (int i = 0; i < list.size(); i++) { Object element = list.get(i); // 处理元素逻辑 }使用增强型 for 循环（foreach 循环）：使用增强型 for 循环可以方便地遍历 List 的每个元素，无需担心索引的处理。例如：
for (Object element : list) { // 处理元素逻辑 }使用迭代器（Iterator）：使用 Iterator 可以遍历 List 的每个元素，而且在遍历过程中可以对元素进行删除操作。例如：
Iterator<Object> iterator = list.iterator(); while (iterator.hasNext()) { Object element = iterator.next(); // 处理元素逻辑 }使用 ListIterator：ListIterator 是 Iterator 的子接口，支持双向遍历，并可以在遍历过程中进行添加、删除和修改操作。例如：
ListIterator<Object> iterator = list.listIterator(); while (iterator.hasNext()) { Object element = iterator.next(); // 处理元素逻辑 }需要根据具体的需求和场景，选择合适的遍历方式。如果只需要简单地遍历 List 的元素，可以使用增强型 for 循环。如果需要在遍历过程中对元素进行删除操作，可以使用迭代器或 ListIterator。如果需要双向遍历并支持对元素的修改操作，可以使用 ListIterator。
二十二、for循环遍历List原理
当使用 for 循环遍历 List 时，实际上是利用 List 的索引来依次获取其中的元素进行遍历。下面我会解释一下 for 循环遍历 List 的原理：
获取 List 的大小：for 循环首先通过调用 List 的 size() 方法来获取集合的大小，即其中元素的个数。
使用索引遍历：for 循环使用一个整型的索引变量（通常命名为 i）从 0 开始递增，到 List 的大小减 1 结束（因为 List 的索引是从 0 开始的），每次循环都通过调用 get(i) 方法来获取索引对应位置的元素。
循环过程：每次循环，for 循环都会获取 List 中当前索引位置的元素，然后执行循环体内的逻辑处理，直到索引变量超出了集合的大小范围。
下面是一个简单的示例代码，演示了使用 for 循环遍历 List 的过程：
List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); for (int i = 0; i < list.size(); i++) { String element = list.get(i); System.out.println(element); }在上述示例中，通过调用 list.size() 方法获取 List 的大小，然后利用索引变量 i 循环遍历 List，每次循环获取索引对应位置的元素并进行处理。
for 循环遍历 List 的原理是通过获取集合的大小，然后利用索引变量从 0 开始递增，通过调用 get 方法来获取对应位置的元素，从而实现对 List 元素的遍历操作。这种遍历方式相对简单和直观，适用于大部分遍历场景。
二十三、增强型 for 循环遍历List原理
增强型 for 循环，也被称为 for-each 循环，是一种简化遍历集合（如 List、Set、Map等）或数组的方式。相比传统的 for 循环，增强型 for 循环语法更简洁，更易读。
增强型 for 循环的语法格式如下：
for (元素的数据类型 变量名 : 要遍历的集合或数组) { // 在此处使用变量进行操作 }当使用增强型 for 循环遍历一个集合或数组时，循环会按照顺序在每个元素上迭代。每一次迭代中，元素的值都会被赋给指定的变量，然后可以在循环体中使用这个变量进行操作。
具体原理如下：
- 获取要遍历的集合或数组的迭代器或长度。
- 判断集合或数组是否还有下一个元素。
- 如果有下一个元素，则将当前元素赋值给指定的变量。
- 执行循环体中的代码，使用变量进行操作。
- 重复步骤 2-4，直到没有下一个元素为止。
需要注意的是，在增强型 for 循环中，不能直接对集合或数组进行添加、删除等修改操作，因为循环的过程中是无法知道集合或数组的结构发生了变化。如果需要修改集合或数组，建议使用传统的 for 循环。
总的来说，增强型 for 循环是一种方便、简洁的遍历集合或数组的方式，它通过简化语法，使代码更易读、更易理解。
二十四、Iterator遍历List原理
Iterator 遍历 List 时，实际上是通过 Iterator 接口提供的方法来依次访问集合中的元素。下面是 Iterator 遍历 List 的原理：
获取 Iterator 对象：首先，通过调用 List 的 iterator() 方法获取一个 Iterator 对象，该对象将用于遍历 List。
使用 hasNext() 判断是否还有下一个元素：在循环开始之前，通过调用 Iterator 对象的 hasNext() 方法来判断是否还有下一个元素。
使用 next() 获取下一个元素：如果 hasNext() 返回 true，则调用 Iterator 对象的 next() 方法来获取下一个元素。
循环过程：在循环体内，进行对当前元素的逻辑处理，然后再次判断是否还有下一个元素，如此反复直到遍历结束。
下面是一个简单的示例代码，演示了使用 Iterator 遍历 List 的过程：
List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { String element = iterator.next(); System.out.println(element); }在上述示例中，通过调用 list.iterator() 方法获取一个 Iterator 对象，然后使用 while 循环判断是否还有下一个元素，如果有，则调用 iterator.next() 方法获取下一个元素并进行处理。
Iterator 遍历 List 的原理是通过获取 List 对象的一个 Iterator 对象，并通过调用 hasNext() 方法判断是否还有下一个元素，再通过调用 next() 方法获取下一个元素。这种遍历方式相对灵活，适用于需要在遍历过程中进行删除操作或对元素进行修改的场景。
二十五、ListIterator遍历List原理
使用 ListIterator 遍历 List 时，可以实现双向遍历，并且在遍历过程中可以进行元素的添加、删除和修改操作。下面是 ListIterator 遍历 List 的原理：
获取 ListIterator 对象：首先，通过调用 List 的 listIterator() 方法获取一个 ListIterator 对象，该对象将用于遍历 List。
使用 hasNext() 判断是否还有下一个元素：在循环开始之前，通过调用 ListIterator 对象的 hasNext() 方法来判断是否还有下一个元素。
使用 next() 获取下一个元素：如果 hasNext() 返回 true，则调用 ListIterator 对象的 next() 方法来获取下一个元素。
使用 hasPrevious() 判断是否还有上一个元素：在循环体内，可以通过调用 ListIterator 对象的 hasPrevious() 方法判断是否还有上一个元素。
使用 previous() 获取上一个元素：如果 hasPrevious() 返回 true，则调用 ListIterator 对象的 previous() 方法来获取上一个元素。
循环过程：在循环体内，进行对当前元素的逻辑处理，然后再次判断是否还有下一个或上一个元素，如此反复直到遍历结束。
下面是一个简单的示例代码，演示了使用 ListIterator 遍历 List 的过程：
List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); ListIterator<String> iterator = list.listIterator(); while (iterator.hasNext()) { String element = iterator.next(); System.out.println(element); } // 遍历过程中在指定位置添加元素 iterator.add("D"); while (iterator.hasPrevious()) { String element = iterator.previous(); System.out.println(element); }在上述示例中，通过调用 list.listIterator() 方法获取一个 ListIterator 对象，然后使用 while 循环判断是否还有下一个元素，如果有，则调用 iterator.next() 方法获取下一个元素并进行处理。在循环过程中还可以通过调用 iterator.add() 方法在指定位置添加元素。然后使用 while 循环判断是否还有上一个元素，如果有，则调用 iterator.previous() 方法获取上一个元素并进行处理。
ListIterator 遍历 List 的原理是通过获取 List 对象的一个 ListIterator 对象，并通过调用 hasNext()、next()、hasPrevious()、previous() 方法来获取下一个或上一个元素，实现双向遍历，并且可以在遍历过程中进行元素的添加、删除和修改操作。这种遍历方式比较灵活且功能强大，适用于需要在遍历过程中修改集合元素或进行特定操作的场景。
二十六、ArrayList优缺点
ArrayList 是 Java 中常用的动态数组实现，下面是 ArrayList 的一些优点和缺点：
优点：
随机访问快速：由于 ArrayList 基于数组实现，可以通过索引快速进行随机访问，时间复杂度为 O(1)。
易于添加和删除末尾元素：在末尾添加或删除元素的时间复杂度为 O(1)。
支持动态扩容：当元素数量超出当前容量时，ArrayList 会自动进行扩容，无需手动管理容量。
实现了 java.util.List 接口：作为 List 接口的实现，提供了丰富的操作方法，能够方便地进行元素的增删改查操作。
缺点：
频繁的插入和删除操作效率低：在中间或开头位置插入或删除元素时，需要移动元素，时间复杂度为 O(n)。
扩容时会带来性能损耗：当 ArrayList 容量不足时会触发扩容操作，需要重新分配内存并拷贝元素，造成一定的性能开销。
不适合大规模删除操作：由于删除元素后需要移动后续元素，大规模删除操作性能较差。
不支持基本数据类型：ArrayList 只能存储对象，不能直接存储基本数据类型，需要使用对应的包装类。
ArrayList 适合读取频繁、插入删除较少的场景，特别适合作为动态数组进行随机访问。但在需要频繁插入、删除或批量操作的场景下，可能会存在一些性能上的不足。
二十七、数组与List转换
可以通过以下方式实现数组与 List 的转换：
- 数组转换为 List：可以使用 Arrays 类的 asList() 方法将数组转换为 List。
String[] array = {"A", "B", "C"}; List<String> list = Arrays.asList(array); // 示例中的 list 是一个固定大小的 List，不能执行添加和删除操作
- List 转换为数组：可以使用 List 的 toArray() 方法将 List 转换为数组。
List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); String[] array = list.toArray(new String[0]); // 示例中通过传入一个空数组，toArray() 方法会根据 List 的大小自动创建相应类型的数组需要注意的是，利用 Arrays.asList() 方法将数组转换为 List 时，在转换后的 List 中无法执行添加和删除操作，因为底层仍然是一个固定大小的数组。如果需要对 List 进行修改操作，可以将转换后的 List 再进一步构造为 ArrayList，例如：
String[] array = {"A", "B", "C"}; List<String> list = new ArrayList<>(Arrays.asList(array)); // 现在可以通过 list 对象执行添加和删除操作另外，可以使用 Collections 类的静态方法将 List 转换为数组。这种方法更加灵活，可以转换任何类型的 List：
List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); String[] array = list.toArray(new String[list.size()]); // 示例中通过传入一个具有合适大小的数组，toArray() 方法会将元素复制到新创建的数组中通过 Arrays 类的 asList() 方法可以将数组转换为 List，而 List 的 toArray() 方法可以将 List 转换为数组。需要注意的是，通过 asList() 方法转换得到的 List 是一个固定大小的 List，不能进行添加和删除操作。如果需要对转换后的 List 进行修改操作，可以将其再进一步构造为 ArrayList。
二十八、ArrayList 和 LinkedList区别
ArrayList 和 LinkedList 是 Java 中常用的两种 List 实现，它们之间有以下区别：
1.内部数据结构：
- ArrayList 是基于数组实现的动态数组，支持随机访问，但在插入和删除操作时需要移动元素。
- LinkedList 是基于双向链表实现的，插入和删除操作效率较高，但随机访问效率较低。
2.随机访问性能：
- ArrayList 支持通过索引进行快速的随机访问，时间复杂度为 O(1)。
- LinkedList 不支持直接随机访问，需要通过遍历链表来访问特定位置的元素，时间复杂度为 O(n)。
3.插入和删除操作：
- ArrayList 在中间或开头插入/删除元素时需要移动其他元素，时间复杂度为 O(n)。
- LinkedList 在插入和删除操作时效率较高，时间复杂度为 O(1)。
4.内存占用：
- ArrayList 在不必要的预留空间情况下可能会浪费一定的内存空间。
- LinkedList 每个元素需要额外的空间用于存储指向前后元素的引用，可能占用的内存相对较多。
5.迭代性能：
- ArrayList 通过迭代器进行遍历时性能较好，因为数据在内存中是连续存储的。
- LinkedList 在迭代过程中需要频繁地跳转节点，迭代性能相对较低。
6.适用场景：
- ArrayList 适合于需要频繁随机访问的场景，对索引访问要求较高的情况。
- LinkedList 适合于需要频繁插入、删除操作以及在两端进行操作的场景。
通常情况下可以根据具体需求来选择使用 ArrayList 还是 LinkedList。如果需要频繁随机访问和操作索引位置的场景，可以选择 ArrayList；如果需要频繁进行插入、删除操作或者两端操作的场景，可以选择 LinkedList。
二十九、ArrayList 和Vector 区别
ArrayList 和 Vector 都是 Java 中用于存储和操作对象的动态数组实现，它们之间的区别主要在以下几个方面：
1.线程安全性：
- ArrayList 不是线程安全的，如果多个线程同时访问一个 ArrayList 的实例，并且至少有一个线程在结构上修改了列表，那么它必须保持外部同步。
- Vector 是线程安全的，它的所有方法都经过同步或加锁处理，因此多个线程可以安全地同时访问一个 Vector 的实例。
2.性能：
- 在单线程环境下，ArrayList 的性能比 Vector 更好，因为 ArrayList 不需要进行额外的同步操作。
- 在多线程环境下，由于 Vector 的同步操作会带来一定的性能开销，所以在性能上可能比 ArrayList 要差。
3.扩容机制：
- ArrayList 和 Vector 都是动态数组，当元素数量超出当前容量时，会自动进行扩容。不同的是，ArrayList 的扩容因子为 1.5 倍，而 Vector 的扩容因子为 2 倍。
4.初始容量增长方式：
- ArrayList 可以在初始化时指定一个初始容量，如果不指定，默认为 10。如果需要动态增长，它会以 1.5 倍的速度进行增长。
- Vector 在初始化时也可以指定初始容量，如果不指定，默认为 10。它的初始容量增长方式也是以 2 倍的速度进行增长。
5.迭代器的使用：
- ArrayList 使用迭代器进行遍历时不需要考虑同步问题，在单线程环境下迭代器操作更为高效。
- Vector 在迭代器遍历时需要考虑同步，因为 Vector 的方法都是同步的，会在多线程环境下引起额外的开销。
ArrayList 是非线程安全的，性能较好，在单线程环境下使用较为合适；而 Vector 是线程安全的，但在多线程环境下性能可能会受到一定影响。在选择使用时，可以根据实际需求来考虑是否需要线程安全性以及对性能的要求。在单线程环境下，通常优先选择 ArrayList，而在多线程环境下或对线程安全性要求较高时可以考虑使用 Vector。
三十、ArrayList、LinkedList、Vector插入数据哪个快
ArrayList、LinkedList和Vector在插入数据时，它们的性能略有不同。具体哪个更快取决于插入数据的位置和数据的大小。
1.ArrayList:
- 插入数据到指定位置：O(n) 操作，因为需要移动插入位置之后的所有元素。
- 插入数据到头部或尾部：O(1) 操作，因为可以直接在头部或尾部添加元素。
2.LinkedList:
- 插入数据到指定位置：O(1) 操作，因为链表提供了在任意位置插入和删除元素的高效操作。
- 插入数据到头部或尾部：O(1) 操作，因为可以直接在头部或尾部添加元素。
3.Vector:
- 插入数据到指定位置：O(n) 操作，因为需要移动插入位置之后的所有元素。
- 插入数据到头部或尾部：O(1) 操作，因为可以直接在头部或尾部添加元素。
如果你需要频繁地在指定位置插入数据，LinkedList 是最快的选择。如果你需要频繁地在头部或尾部插入数据，那么ArrayList 和 Vector 都很快（因为它们都支持 O(1) 时间复杂度的操作）。在其他情况下，LinkedList 的性能通常优于 ArrayList 和 Vector。
三十一、多线程场景下如何使用ArrayList
在多线程场景下，ArrayList 并不是线程安全的，因此在多线程环境下需要采取措施来保证线程安全性。以下是一些常见的方法来在多线程场景下使用 ArrayList：
使用 Collections 工具类的 synchronizedList 方法：
List<Object> synchronizedList = Collections.synchronizedList(new ArrayList<>());这种方法通过
Collections.synchronizedList方法创建了一个线程安全的 ArrayList 对象，它会对所有访问列表的方法加上同步锁，从而使得多个线程可以安全地访问该列表。然而，需要注意的是，即使使用这种方式，仍然需要小心地处理迭代和其他复合操作，以避免出现并发修改异常。使用并发集合类：
Java 提供了一些并发集合类，比如CopyOnWriteArrayList，它是一个线程安全的动态数组实现，适用于读多写少的场景。通过使用这些并发集合类，可以避免手动处理同步和锁的问题。显式加锁：
如果没有适合的并发集合类，也可以通过显式地加锁来保证多线程环境下的访问安全，例如使用ReentrantLock。在多线程环境下，处理并发访问问题是非常重要的，需要根据具体的应用场景选择合适的方案来保证线程安全性。
三十二、ArrayList的 elementData加上 transient修饰
可以通过使用
transient关键字来修饰类的成员变量，表示该变量不参与序列化过程。对于 ArrayList 类而言，如果将elementData数组声明为transient，则在对象被序列化时，该数组的内容将被排除在序列化之外，不会被持久化到序列化数据流中。示例代码如下所示：
import java.io.Serializable; import java.util.ArrayList; public class MySerializableList implements Serializable { private transient Object[] elementData; // 声明为transient的数组 public MySerializableList(int initialCapacity) { this.elementData = new Object[initialCapacity]; } // 其他成员和方法 }需要注意的是，将
elementData声明为transient可能会导致序列化和反序列化后，该数组恢复为null，因为在反序列化时，不会从输入流中读取该字段的值。因此，在实际使用中，需要确保在需要序列化和反序列化时，对elementData进行正确的处理，以保证其在反序列化后能够正确地恢复其状态。通过将
elementData声明为transient，可以控制其在序列化过程中的行为，但需要谨慎处理在反序列化后的恢复逻辑。
三十三、List 和 Set 的区别
List和Set都是Java集合框架中常用的接口，用于存储和操作一组元素。它们的主要区别可以总结如下：
1.重复元素：
- List允许存储重复的元素，即可以包含相同的元素。
- Set不允许存储重复的元素，即不能包含相同的元素。
2.元素顺序：
- List是有序的集合，即元素按照插入顺序进行存储，并且可以通过索引访问和操作集合中的元素。
- Set是无序的集合，元素的存储顺序是不确定的，不支持通过索引访问和操作集合中的元素。
3.底层实现：
- List通常使用数组或链表等数据结构来实现，比如ArrayList、LinkedList等。
- Set通常使用哈希表或树等数据结构来实现，比如HashSet、TreeSet等。
4.性能特点：
- List在插入和删除元素时，如果涉及到移动元素（如在列表的中间位置插入或删除元素），性能较差，因为需要重新分配和移动元素。而对于末尾的插入和删除操作，性能较好。
- Set在插入和删除元素时，通常比List性能更好，因为不涉及元素的移动。
根据具体的需求和使用场景，选择合适的集合类型。如果需要按照元素的顺序存储且允许重复元素，则选择List；如果需要存储唯一的元素且不关心元素的顺序，则选择Set。
三十四、HashSet的实现原理
HashSet 的实现原理主要基于哈希表，它是基于 HashMap 实现的。下面是 HashSet 的主要实现原理：
基于哈希表： HashSet 内部通过一个 HashMap 对象来存储元素，实际上只使用了 HashMap 中的 key 集合来存储元素，而 value 则统一使用了同一个 Object 对象。这也是由于 HashMap 的 key 不允许重复，正符合了 Set 的特性。
哈希算法： 当向 HashSet 中添加元素时，其实质是将元素作为 key 存储到 HashMap 中。为了尽可能快地查找元素，需要一个能够将元素转换为索引位置的哈希算法。具体来说，元素的
hashCode()方法用于获取元素的哈希码，然后通过哈希算法得到存储位置。处理哈希冲突： 虽然哈希算法可以将元素映射到唯一的索引位置，但不同的元素可能映射到相同的位置，这就是所谓的哈希冲突。在 HashMap 中，使用链表或红黑树来处理哈希冲突，确保不同的元素可以共享同一个索引位置。
性能特点： HashSet 的添加、删除和查找操作都具有很好的性能，平均时间复杂度为 O(1)。这是因为通过哈希表的索引定位，可以快速找到对应的存储位置，而不需要像数组一样进行线性查找。
HashSet 通过利用哈希表的快速查找特性来实现对元素的存储和访问，可以高效地判断元素是否存在，具有良好的性能，并且不允许存储重复的元素。
三十五、HashSet如何检查重复元素
HashSet 在检查重复元素时是通过两个步骤进行的：
哈希码比较： 当向 HashSet 添加元素时，它会首先调用元素的
hashCode()方法获取元素的哈希码。HashSet 会将每个元素存储在对应的哈希桶中，哈希桶是一个数组，里面的每个元素也是一个桶，可以存储多个元素。HashSet 会根据元素的哈希码来确定应该放入哪个哈希桶中。equals() 比较： 如果元素的哈希码相同，HashSet 会继续调用元素的
equals()方法来比较这些元素是否相等。这是为了处理哈希冲突，因为不同元素可能会映射到同一个哈希桶中。如果两个元素的哈希码相同且通过equals()方法比较也相等，则 HashSet 认为这两个元素重复，新元素将不会被添加到集合中。需要注意的是，在使用 HashSet 存储自定义类的对象时，需要确保正确实现
hashCode()和equals()方法，以便 HashSet 能够正确地检查重复元素。具体要求如下：
- 相等的对象必须具有相等的哈希码。
- 如果两个对象的哈希码不同，则这两个对象不相等。
- 如果两个对象的哈希码相同，但通过
equals()方法比较也不相等，则这两个对象不相等。- 如果两个对象的哈希码相同，并且通过
equals()方法比较也相等，则这两个对象相等，HashSet 将视其为重复元素，只存储其中的一个。HashSet 使用哈希码和
equals()方法来检查重复元素，这是在底层的哈希表结构中实现的。
三十六、HashSet是如何保证数据不可重复
HashSet 通过使用哈希表来确保数据的不可重复性。哈希表是一种基于哈希算法的数据结构，它基于键（即元素对象）的哈希码来存储和检索元素。
在 HashSet 中，当添加元素时，首先会计算元素的哈希码（通过元素的
hashCode()方法），然后根据哈希码找到对应的哈希桶（数组中的一个位置）。如果该位置没有其他元素，那么就直接将该元素放入该位置。如果该位置已经有其他元素，就需要判断该元素与已存在的元素是否相等。HashSet 通过元素的哈希码和
equals()方法来确定两个元素是否相等。具体的判断逻辑如下：
- 如果两个元素的哈希码不同，说明它们一定不相等，HashSet 将会将新元素插入到哈希桶中。
- 如果两个元素的哈希码相同，HashSet 会继续调用元素的
equals()方法来比较它们是否相等。如果equals()方法返回 true，说明这两个元素相等，HashSet 将认为新元素是重复的，不会将其插入到哈希桶中；如果equals()方法返回 false，说明这两个元素不相等，HashSet 将会将新元素插入到哈希桶中。通过上述的处理逻辑，HashSet 能够确保在集合中不会存储重复的元素。当我们需要使用 HashSet 存储自定义类的对象时，需要确保正确实现
hashCode()和equals()方法，以便 HashSet 能够正常地判断元素的相等性。
三十七、hashCode()与equals()
hashCode() 和 equals() 是 Java 中 Object 类的两个重要方法，它们在用于对象的哈希表存储和相等性比较中起着关键作用。以下是关于 hashCode() 和 equals() 的相关规定：
hashCode() 规定：
1. hashCode() 的返回值是 int 类型的哈希码，用于确定对象在哈希表中的存储位置。
2. 如果两个对象通过 equals() 方法比较相等，那么它们的 hashCode() 必须返回相同的值。也就是说，如果 a.equals(b) 返回 true，则 a.hashCode() 和 b.hashCode() 必须返回相同的值。
3. 反过来，如果两个对象的 hashCode() 返回值相同，它们并不一定相等，即 equals() 方法应当再次进行比较。
equals() 规定：
1.equals() 用于比较两个对象是否相等。它是判断对象的内容是否相同的方法。
2.equals() 方法具有以下特性：
- 自反性：对于任何非 null 对象 a，a.equals(a) 必须返回 true。
- 对称性：对于任何非 null 对象 a 和 b，如果 a.equals(b) 返回 true，则 b.equals(a) 也必须返回 true。
- 传递性：对于任何非 null 对象 a、b 和 c，如果 a.equals(b) 返回 true，并且 b.equals© 也返回 true，那么 a.equals© 必须返回 true。
- 一致性：对于任何非 null 对象 a 和 b，在对象内容没有改变的情况下，多次调用 a.equals(b) 应该返回相同的结果。
- 对于任何非 null 对象 a，a.equals(null) 必须返回 false。
需要注意的是，当重新定义自定义类的 equals() 方法时，也应当重写 hashCode() 方法，以确保 hashCode() 和 equals() 保持一致。尤其是在使用哈希表结构（如 HashSet、HashMap）存储对象时，不遵守这些规定可能导致无法正确操作哈希表，出现元素无法找到或重复等问题。
三十八、HashSet与 HashMap的区别
HashSet 和 HashMap 是 Java 中两个不同的集合类，它们之间有以下几个主要区别：
用途区别： HashSet 是无序且不重复的集合，它基于哈希表实现；HashMap 则是键值对的集合，它也基于哈希表实现。
存储内容区别： HashSet 存储的是唯一的元素对象，不允许重复；HashMap 存储的是键值对，其中键是唯一的，但值可以重复。
底层数据结构区别： HashSet 的底层数据结构是哈希表，是一种数组和链表的组合；HashMap 的底层数据结构也是哈希表，但它将键值对作为存储的单位。
存取方式区别： 在 HashSet 中，元素对象作为键进行存储；在 HashMap 中，使用键值对进行存储。存取元素时，HashSet 使用元素对象作为键来进行查找，而 HashMap 可以根据键快速查找对应的值。
迭代顺序区别： HashSet 中的元素没有顺序，无法保证遍历时的顺序；HashMap 中的键值对是无序的，遍历时也无法保证顺序，但可以通过键来获取对应的值。
需要注意的是，HashSet 和 HashMap 的实现机制都依赖于对象的 hashCode() 和 equals() 方法。在使用自定义类作为元素或键时，需要正确重写这些方法，以确保集合类能够正确存储和检索元素。此外，HashSet 和 HashMap 的性能和适用场景也略有不同，根据具体需求选择合适的集合类。
三十九、Hash算法
哈希算法（Hash Algorithm）是一种通过将输入数据转换为固定长度的哈希值（hash value）的算法。这种算法会将不同长度的输入数据转换为固定长度的输出，通常用作数据的唯一标识，也称为哈希码、摘要或指纹。哈希算法具有以下特点：
固定长度输出： 无论输入数据的长度是多少，哈希算法的输出始终保持固定的长度。
唯一性： 不同的输入数据经过哈希算法计算后得到的哈希值不同。理想情况下，不同的输入应该对应不同的哈希值，但由于哈希值长度有限，不同的输入也可能产生相同的哈希值，这种情况称为哈希冲突。
不可逆性： 哈希算法是一种单向运算，即从哈希值无法反推出原始数据。这意味着无法通过哈希值还原出原始数据，因此哈希算法也被用于加密算法中。
高效性： 哈希算法需要尽可能快地计算出哈希值，以便在实际应用中快速处理大量数据。
常见的哈希算法包括MD5（Message Digest Algorithm 5）、SHA-1（Secure Hash Algorithm 1）、SHA-256 等，它们在数据完整性校验、加密存储、密码学等领域得到广泛应用。
在计算中，哈希算法的输入可以是任意长度的数据，可能是消息、文件、密码等，输出是固定长度的哈希值。在实际应用中，哈希算法被广泛应用于数据校验、密码存储、区块链等领域。
四十、链表
链表（Linked List）是一种常见的数据结构，它可以用来存储和操作一系列的元素。链表中的每个元素被称为节点（Node），每个节点包含两部分：数据（通常是数据的值）和指向下一个节点的指针。
与数组不同，链表中的节点并不是连续存储的，而是通过指针连接在一起的。每个节点存储了自己的数据以及指向下一个节点的指针，从而形成了一个链式结构。
链表有多种类型，其中最常见的两种是单向链表和双向链表：
单向链表（Singly Linked List）： 单向链表中的每个节点包含一个指向下一个节点的指针。最后一个节点的指针通常为 null，表示链表的结尾。
双向链表（Doubly Linked List）： 双向链表中的每个节点包含两个指针，一个指向下一个节点，一个指向上一个节点。双向链表可以在两个方向上遍历，相比于单向链表，它可以更方便地进行插入和删除操作。
链表具有一些特点：
灵活的大小： 链表的大小可以根据需要动态增长或缩小，不像数组需要预先分配固定的内存空间。
插入和删除高效： 在链表中插入或删除节点的操作相对高效，只需修改指针，不需要移动整个链表。
随机访问性能较差： 链表中的节点不是连续存储的，因此无法通过索引直接访问特定位置的元素。需要从头节点开始遍历链表，直到找到目标位置。
链表的应用场景包括但不限于：实现栈（Stack）、队列（Queue）、图（Graph）、操作系统的进程管理等。然而，由于链表需要额外的指针开销和顺序访问的局限性，对于需要频繁随机访问和大量元素存储的情况，数组通常更为适合。
四十一、HashMap的实现原理
HashMap 是 Java 中常用的集合类之一，它基于哈希表（Hash Table）实现。下面是 HashMap的基本实现原理：
数据结构： HashMap 内部使用一个数组来存储元素，这个数组被称为哈希桶数组（bucket array）。每个数组元素的类型是链表或红黑树，用来解决哈希冲突。
哈希函数： 当向 HashMap 中插入一个键值对时，首先会根据键的哈希值计算出在哈希桶数组中的位置。Java 中使用的是
(h = key.hashCode()) ^ (h >>> 16)这样的位运算来计算哈希值。解决哈希冲突： 当不同的键经过哈希函数计算得到相同的位置时，就发生了哈希冲突。HashMap 使用链表法（Separate Chaining）或者红黑树来解决冲突，即将相同位置的键值对存储在同一个位置上，并通过链表或者树结构来存储和查找相同位置的元素。
链表法（JDK 7 及之前）： 当冲突发生时，相同位置的键值对会以链表的形式存储在数组中，新元素会被添加到链表的末尾。
红黑树（JDK 8 及之后）： 当链表的长度超过一定阈值（默认为 8），JDK 8 引入了红黑树来优化性能。当冲突过多时，链表会被转换成红黑树，以提高查找、插入和删除操作的效率。
扩容和重新哈希： 当 HashMap 中的键值对数量达到容量的 75% 时，会触发扩容操作。这时哈希桶数组会变大一倍，并且原有的键值对需要重新计算哈希值，分布到新的更大的桶数组中。
HashMap 的实现原理保证了在常规情况下，插入、删除和查找操作的时间复杂度为 O(1)。然而，当哈希冲突较多时，链表过长甚至退化成红黑树的情况下，时间复杂度可能上升到 O(log n)。因此，在实际使用中，保持适当的负载因子是很重要的，以避免性能下降。
四十二、HashMap 在jdk1.7和jdk1.8的不同
在 JDK 1.7 和 JDK 1.8 中，HashMap 在内部实现上发生了较大的变化，主要集中在解决哈希冲突的方式和对性能的优化上。以下是 JDK 1.7 和 JDK 1.8 中 HashMap 的主要不同之处：
1.存储结构：
JDK 1.7： 在 JDK 1.7 中，HashMap 在解决哈希冲突时使用的是链表法，即相同位置的键值对会以链表的形式存储。这意味着当哈希冲突发生时，元素会依次存储在同一个位置的链表中。
JDK 1.8： 在 JDK 1.8 中，HashMap 对解决哈希冲突的方式进行了优化。当链表长度超过一定阈值（默认为 8）时，JDK 8 引入了红黑树来替代链表，以提高查找、插入和删除操作的效率。这主要是为了解决在极端情况下链表过长导致性能下降的问题。
2.引入红黑树：
JDK 1.7： 在 JDK 1.7 中，并没有引入红黑树，解决哈希冲突时仅使用链表来存储冲突的键值对。
JDK 1.8： 在 JDK 1.8 中，引入了红黑树来优化HashMap。当链表长度过长时，会将链表转换为红黑树，以提高在冲突较多时的性能，因为红黑树的查找、插入和删除等操作的时间复杂度是 O(log n)。
3.性能优化：
- JDK 1.8： 在 JDK 1.8 中，对 HashMap 的性能做了一系列优化，包括针对哈希算法、哈希冲突处理和红黑树的操作进行了优化，以提高 HashMap 在大规模数据操作时的性能表现。
JDK 1.8 的 HashMap 在解决哈希冲突的方式上引入了红黑树，并对性能进行了优化，使得在处理大规模数据时性能更佳。这些改进使得 JDK 1.8 中的 HashMap 在性能上相对于 JDK 1.7 有了较大的提升。
四十三、红黑树
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树（Binary Search Tree）。它在普通的二叉搜索树的基础上增加了一些特性，以保持树的平衡性。
红黑树具有以下特点：
节点颜色： 每个节点被标记为红色或黑色。
根节点和叶子节点： 根节点是黑色的，叶子节点（也称为空节点或空叶子）是黑色的。注意，这里的叶子节点并非真正的空节点，而是表示空子节点的特殊节点。
红色节点限制： 红色节点的子节点都必须是黑色的。
黑色节点计数： 从任意节点到其每个叶子节点的路径上，经过的黑色节点数量必须相同。这个特性确保了树的平衡性。
红黑树通过自己的特性来维护和调整平衡性，以保证插入、删除和查找等操作的时间复杂度为 O(log n)，其中 n 是树中节点的数量。
红黑树在很多数据结构和算法中广泛应用，尤其是在编程语言的集合实现中，如 Java 中的 HashMap 和 TreeMap。
红黑树的自平衡性和复杂的调整规则使其相对于普通的二叉搜索树更复杂，因此实现和维护红黑树需要更多的代码和计算量。但是，红黑树的平衡性保证了较好的性能，使得在大规模数据处理和高效查找等场景下具有很好的表现。
四十四、HashMap的 put方法的具体流程
HashMap 的 put 方法主要包括以下几个步骤，是一个常见的键值对插入操作：
1.计算哈希值： 首先根据键的哈希值确定这个键值对在哈希表中的位置。
2.定位桶： 根据哈希值确定键值对在哈希桶数组中的位置，即确定放置该键值对的桶（bucket）索引。
3.判断是否需要初始化哈希桶： 确定桶的位置后，需要判断该位置是否已经有其他键值对。如果没有，则需要初始化该位置的桶。
3.处理哈希冲突： 如果在相同位置处存在已有的键值对，那么就会发生哈希冲突。这时会根据具体的实现方法进行处理：
- JDK 1.7 及之前： 在 JDK 1.7 及之前的版本中，会使用链表法来处理冲突，新的键值对会被添加到链表的末尾。
- JDK 1.8 及之后： 在 JDK 1.8 及之后的版本中，当链表长度超过一定阈值（默认为 8）时，会将链表转换为红黑树，以提高查找、插入和删除操作的效率。
4.插入或替换键值对： 根据哈希冲突的处理结果，将新的键值对插入到位置对应的桶中。如果已经存在相同键的键值对，则会将新的值替换旧的值。
5.检查容量： 在插入完成后，会检查当前 HashMap 中的键值对数量是否达到容量的 75%。如果达到或超过这个阈值，会触发扩容操作。
6.扩容和重新哈希： 如果需要扩容，HashMap 会将哈希桶数组扩大一倍，并且重新计算已有键值对的哈希值，将它们分布到新的更大的桶数组中。这个过程叫做重新哈希。
HashMap 的 put 方法的流程包括了根据哈希值定位插入位置、处理哈希冲突、插入或替换键值对，以及在必要时进行扩容和重新哈希等步骤。
putVal方法直接流程图：
putVal源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 实现Map.put和相关方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1: tab为空则创建
// table未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2: 计算index，并对null处理
// （n - 1）& hash确定元素存放在哪个桶中，桶为空，新生成结点放入桶中（此时这个结点是放在数组中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 3: 节点key 存在，直接覆盖 value
// 比较桶中第一个元素（数组中的结点）的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给 e，用e 来记录
e = p;
// 4: 判断该链为红黑树
// hash值不相乖，即 key 不相等，为红黑树结节
// 如果当前元素类型为 TreeNode，表示红黑树，putTreeVal返回待存放的 node，e 可能为null
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 5: 该链为链表
// 为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部
// 判断该链表尾部指针是不是空的
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
// 判断链表的长度是否达到转化红黑树的临界值，临界值为8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表结构转树形结构
treeifyBin(tab, hash);
// 跳循环
break;
}
// 判断链表中结点的 key值与插入的元素的key 值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的 e = p.next组合，可以遍历链表
p = e;
}
}
// 判断当前的key 已经存在的情况下，再来一个相同的hash值，key值时，返回新来的value这个值
if (e != null) { // existing mapping for key
// 记录e 的value
V oldValue = e.value;
// onlyIfAbsent为false 或者旧值为null
if (!onlyIfAbsent || oldValue == null)
// 用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 6: 超过最大容量就扩容
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}- 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
- 根据键值key 计算 hash值得到插入的数组索引 i，如果 table[i] == null ，直接新建节点添加，转为 6，如果 table[i] 不为空，转为 3 。
- 判断 table[i] 的首个元素是否 和 key 一样，如果相同直接覆盖 value，否则转向 4，这里的相同指的是 hashCode 以及 equals；
- 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向 5 。
- 遍历 table[i] ,判断链表长度是否大于 8，大于8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则万里长城链表的插入操作； 遍历过程中若发现 key 已经存在直接覆盖 value 即可；
- 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。
四十五、HashMap扩容
HashMap 的扩容操作是通过将哈希桶数组的容量扩大一倍来实现的。
- 在 jdk1.8 中，resize 方法是在 hashmap中的键值对大于阈值时 或者 初始化时，就调用 resize 方法进行扩容；
- 每次扩展的时候，都是扩展 2 倍；
- 扩容后 Node 对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
在putVal()中，我们看到在这个函数里面使用到了 2 次 resize() 方法，resize() 方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大于大于其jtlr值（第一次为12），这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是jdk1.8 版本的一个优化的地方，在 1.7 中，扩容之后需要重新去计算其 hash 值，根据 hash 值对其进行分发，但在 1.8 版本中，则是根据在同一个桶的位置中进行判断（e.hash & oldCap）是否为 0，重新进行 hash 分配后，该元素的位置要么停留在原始位置，要么移动到原始位置 + 增加的数组大小位置上
扩容源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果 oldCap 不为空的话，就是hash 桶数组为空
if (oldCap > 0) {
// 如果大于最大容量了，就赋值为整数最大的阈值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
// 返回
return oldTab;
// 如果当前 hash 桶数组的长度在扩容后仍然小于最大容量并且 oldCap 大于默认值 16
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// double threshold 双倍扩容阈值 threshold
newThr = oldThr << 1; // double threshold
}
// 旧的容量为 0，但threshold大于零，代表有参构造有 cap 传入，threshold已经被初始化成最小 2 的n 次幂
// 直接将该值赋给新的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 无参构造健的 map，给出默认容量和 threshold 16，16 * 0.75
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的 threshold = 新的 cap * 0.75
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 计算出新的数组长度后赋给当前成员亦是 table
@SuppressWarnings({"rawtypes","unchecked"})
// 新建 hash 桶数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将新数组的值复制给旧的 hash 桶数组
table = newTab;
// 如果原先的数组没有初始化，那么 resize 的初始化工作到此结，否则进入扩容元素重排逻辑，使其均匀的分散
if (oldTab != null) {
// 遍历新数组的所有桶下标
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 旧数组的桶下标赋值临时亦是e，并且解除旧数组中的引用，否则就数组无法被GC回收
oldTab[j] = null;
// 如果 e.next == null，代表桶中就一个元素，不存在链表或者红黑树
if (e.next == null)
// 用同样的 hash 映射算法把该元素加入新的数组
newTab[e.hash & (newCap - 1)] = e;
// 如果e 是 TreeNode 并且 e.next != null，那么处理树中元素的重排
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// e 是链表的头并且 e.next != null，那么处理链表中元素重排
else { // preserve order
// loHead，loTail 代表扩容后不用变换下标，见注 1
Node<K,V> loHead = null, loTail = null;
// hiHead, hiTail 代表扩容后变换下标，见注 1
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 初始化 head 指几链表当前元素 e, e 不一定是链表的第一个元素，初始化后 loHead
// 代表下标保持不变的链表的头元素
loHead = e;
else
// loTail.next 指向当前 e
loTail.next = e;
// loTail 指向当前的元素 e
// 初始化后，loTail 和 loHead 指向相同的内存，所以当 loTail.next 指向下一个元素时，
// 底层数组中的元素的 next 引用也相应发生变化，造成 lowHead.next.next
// 跟随 toTail 同步，使得 lowHead 可以链接到所有属于该链表的元素
loTail = e;
}
else {
if (hiTail == null)
// 初始化 head 指向链表当前元素 e,初始化后 hiHead代表下标更改的链表头元素
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 遍历结束，将 tail 指向 null，并把链表头放入新数组的相应下标，形成新的映射。
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
![[ACM学习] 进制转换](https://img-blog.csdnimg.cn/direct/e20f57219fba4eb6a23e04e0657d81fc.png)
