Java集合（个人整理笔记）

目录

1. 常见的集合有哪些？

2. 线程安全的集合有哪些？线程不安全的呢？

3. Arraylist与 LinkedList 异同点？

4. ArrayList 与 Vector 区别？

5. Array 和 ArrayList 有什么区别？什么时候该应 Array而不是 ArrayList 呢？

6. HashMap的底层数据结构是什么？

7. 解决hash冲突的办法有哪些？HashMap用的哪种？

8. HashMap 中 key 的存储索引是怎么计算的？

9. HashMap 的put方法流程？

10. 一般用什么作为HashMap的key?

11. 为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

12. HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？

13. ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？

14. Iterator 和 ListIterator 有什么区别？

15. Collection框架中实现比较要怎么做？

16. 为什么推荐使用更高效的ConcurrentHashMap类来替代HashTable

17. Java中ArrayList集合底层是怎么进行扩容的

18. CurrentHashMap

19. Java 容器都有哪些？

20. Collection 和 Collections 有什么区别？

21. List、Set、Map 之间的区别是什么？

22. HashMap 和 Hashtable 有什么区别？

23. 如何决定使用 HashMap 还是 TreeMap？

24. 说一下 HashMap 的实现原理？

25. 说一下 HashSet 的实现原理？

26. ArrayList 和 LinkedList 的区别是什么？

27. 如何实现数组和 List 之间的转换？

28. ArrayList 和Vector 的区别是什么？

29. Array 和 ArrayList 有何区别？

30. 在 Queue 中 poll()和 remove()有什么区别？

31. 哪些集合类是线程安全的？

32. 迭代器 Iterator 是什么？

a. 迭代器可以遍历Map集合吗

33. Iterator 怎么使用？有什么特点？

34. Iterator 和 ListIterator 有什么区别？

35. 怎么确保一个集合不能被修改？

1. 常见的集合有哪些？

Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue（Java5新增的队列），因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。
注意：Collection是一个接口，Collections是一个工具类，Map不是Collection的子接口。

2. 线程安全的集合有哪些？线程不安全的呢？

线程安全的：
Hashtable：比HashMap多了个线程安全。
ConcurrentHashMap:是一种高效但是线程安全的集合。
Vector：比Arraylist多了个同步化机制。
Stack：栈，也是线程安全的，继承于Vector。
线性不安全的：
HashMap
Arraylist
LinkedList
HashSet
TreeSet
TreeMap

3. Arraylist与 LinkedList 异同点？

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表
插入和删除是否受元素位置的影响： ArrayList 采用数组存储，所以插入和删除元素的时间
复杂度受元素位置的影响。 比如：执行 add(E e) 方法的时候， ArrayList 会默认在将指定的元
素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而ArrayList 实现了
RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。
内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而
LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

4. ArrayList 与 Vector 区别？

Vector是线程安全的，ArrayList不是线程安全的。其中，Vector在关键性的方法前面都加了synchronized关键字，来保证线程的安全性。如果有多个线程会访问到集合，那最好是使用Vector，因为不需要我们自己再去考虑和编写线程安全的代码。
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍，这样ArrayList就有利于节约内存空间。

5. Array 和 ArrayList 有什么区别？什么时候该应 Array而不是 ArrayList 呢？

Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
Array 大小是固定的，ArrayList 的大小是动态变化的。
ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。

6. HashMap的底层数据结构是什么？

在JDK1.7 和JDK1.8 中有所差别： 在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在 的。 在JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索 时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红 黑树，链表和红黑树在达到一定条件会进行转换： 当链表超过 8 且数组长度超过 64 才会转红黑树。 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不 是转换为红黑树，以减少搜索时间。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。

7. 解决hash冲突的办法有哪些？HashMap用的哪种？

解决Hash冲突方法有:开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。HashMap中采用的是 链地址法 。
开放定址法也称为 再散列法 ，基本思想就是，如果 p=H(key) 出现冲突时，则以 p 为基础，再次hash， p1=H(p) ,如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址 pi 。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以 只能在删除的节点上做标记，而不能真正删除节点。
再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当 R1=H1(key1) 发生冲突时，再计算 R2=H2(key1) ，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。
链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

8. HashMap 中 key 的存储索引是怎么计算的？

1. 首先，HashMap会调用key对象的hashCode()方法来获取一个哈希码（hash code）。哈希码是一个整数值，一般是根据key对象的内容计算得出的。
2. 然后，HashMap会对哈希码进行一系列的运算，以确定key在HashMap中的存储位置。其中，一个关键的操作是对哈希码进行取模运算，将其映射到HashMap的桶数组（bucket array）中。
3. 桶数组是HashMap内部用于存储键值对的数组结构。每个桶（bucket）实际上是一个链表或者红黑树，用于处理哈希冲突（即不同的key计算得到相同的哈希码）。
4. 最终，HashMap根据取模运算的结果，将key存储在相应的桶中。

9. HashMap 的put方法流程？

以JDK1.8为例，简要流程如下：

首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；

如果数组是空的，则调用 resize 进行初始化；

如果没有哈希冲突直接放在对应的数组下标里；

如果冲突了，且 key 已经存在，就覆盖掉 value；

如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；

如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；

如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。

10. 一般用什么作为HashMap的key?

一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。
因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是HashMap 中的键往往都使用字符串的原因。
因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了 hashCode() 以及 equals() 方法。

11. 为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

12. HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是 HashMap所能容纳键值对的最大值。threshold = length * Load factor。也就是说，在数组定义好长度 之后，负载因子越大，所能容纳的键值对个数越多。 默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空间比较特殊的情况下 ：

如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值 。

相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值,这个值可以大1。

13. ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？

ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线程安全。而ConcurrentHashMap 的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8 中采用 CAS+Synchronized 实现线程安全。

1. Java 7：Java 7中的ConcurrentHashMap使用了分段锁（Segment Locking）机制。它将整个哈希表分为多个段（Segments），每个段都有自己的锁。这样可以在多线程访问时，同一时间允许多个线程在不同的段上进行并发的读写操作。这种机制在降低锁竞争的同时，提高了并发性能。
2. Java 8：Java 8对ConcurrentHashMap进行了进一步的改进，引入了基于CAS（Compare and Swap）操作的无锁更新机制。在Java 8中，ConcurrentHashMap使用了一种叫做"锁条目"（Lock Striping）的机制。它将整个哈希表分为多个较小的桶（Buckets），每个桶都可以独立进行并发的读写操作，每个桶内部使用CAS操作和volatile变量来进行同步，避免了锁的开销，并提高了并发性能。
3. Java 9：Java 9在ConcurrentHashMap的锁机制上进行了一些改进。它引入了一种叫做"分层锁"（Hierarchy of Locks）的机制，通过将对锁的竞争限制在特定的层级上来提高并发性能。该机制为并发的读取和写入操作提供了更好的扩展性和吞吐量。

14. Iterator 和 ListIterator 有什么区别？

遍历。使用Iterator，可以遍历所有集合，如Map，List，Set；但只能在向前方向上遍历集合中的元素。
使用ListIterator，只能遍历List实现的对象，但可以向前和向后遍历集合中的元素。
添加元素。Iterator无法向集合中添加元素；而，ListIteror可以向集合添加元素。
修改元素。Iterator无法修改集合中的元素；而，ListIterator可以使用set()修改集合中的元素。
索引。Iterator无法获取集合中元素的索引；而，使用ListIterator，可以获取集合中元素的索引。

15. Collection框架中实现比较要怎么做？

第一种，实体类实现Comparable接口，并实现 compareTo(T t) 方法，称为内部比较器。
第二种，创建一个外部比较器，这个外部比较器要实现Comparator接口的 compare(T t1, T t2)方法

16. 为什么推荐使用更高效的ConcurrentHashMap类来替代HashTable

1. 性能：ConcurrentHashMap相对于HashTable在多线程环境下具有更好的性能。ConcurrentHashMap实现了细粒度的锁机制，通过将数据分割为多个段（Segment）来实现并发访问。这样可以使多个线程在访问不同的段时并行进行，减少了线程之间的竞争，提高了并发性能。而HashTable则使用了全局的锁，当一个线程访问HashTable时，其他线程需要等待，导致并发性能相对较低。
2. 扩展性：ConcurrentHashMap允许多个线程同时读取和修改数据，而不会阻塞其他线程的访问。这使得ConcurrentHashMap在高并发场景下能够更好地扩展，提供更好的吞吐量和响应性。
3. 功能：ConcurrentHashMap提供了更多的功能和灵活性。例如，可以使用Iterator来遍历ConcurrentHashMap的结果，在遍历过程中允许其他线程对Map进行修改。此外，ConcurrentHashMap还提供了更多的操作方法，如putIfAbsent()、replace()等等，使得更复杂的并发操作变得更加方便。

17. Java中ArrayList集合底层是怎么进行扩容的

1. 初始化容量：当创建一个 ArrayList 对象时，会为其分配一个初始容量。默认情况下，初始容量是 10，但也可以使用指定初始容量的构造函数来创建 ArrayList。
2. 添加元素：当向 ArrayList 中添加元素时，如果当前元素个数（size）达到了容量（capacity），即数组已满，就需要进行扩容。
3. 计算新容量：扩容时，ArrayList 会计算新的容量大小。一般情况下，新容量是原容量的 1.5 倍。例如，当前容量为 10，那么新容量就是 15。
4. 创建新数组：根据计算得到的新容量，ArrayList 会创建一个新的数组。
5. 复制元素：接下来，ArrayList 使用系统提供的 System.arraycopy() 方法，将原数组中的元素逐个复制到新的数组中，保持元素的顺序和索引不变。这个过程会遍历原数组，然后将元素逐个拷贝到新数组的相同位置。
6. 更新引用：复制完成后，ArrayList 会更新内部的数组引用，指向新的数组。
7. 扩容完成：现在，ArrayList 的底层数组已经扩容成功，并可以接受新的元素添加。

18. CurrentHashMap

基本结构：

分布策略： 数组长度始终保持为2的次幂，讲哈希值的高位参与运算，通过为与操作来等价取模操作

动态扩容：

1.7版本：采用分段锁，维护了一个Segment数组，数组的元素是HashEntry数组

数组中的数据就依赖同一把锁，不同HashEntry数组的读写数据互不干扰，就形成了分段锁

put方法

19. Java 容器都有哪些？

1. ArrayList: 动态数组，可以根据需要调整大小。
2. LinkedList: 双向链表，适合插入和删除操作。
3. HashSet: 无序集合，使用哈希表实现，不允许重复元素。
4. TreeSet: 有序集合，基于红黑树实现，可以自动排序元素。
5. LinkedHashSet: 有序集合，使用哈希表和链表维护元素的插入顺序。
6. HashMap: 无序键值对集合，使用哈希表实现，键和值都可以为null。
7. TreeMap: 有序键值对集合，基于红黑树实现，按键进行排序。
8. LinkedHashMap: 有序键值对集合，使用哈希表和链表维护插入顺序。
9. Stack: 堆栈，遵循先进后出的原则。
10. Queue: 队列，遵循先进先出的原则。
11. PriorityQueue: 优先级队列，按照元素的优先级进行排序。

除了上述常见的容器类型之外，Java还提供了其他特定用途的容器，例如：

1. Hashtable: 类似于HashMap，但是是线程安全的。
2. Vector: 动态数组，类似于ArrayList，但是是线程安全的。
3. ConcurrentHashMap: 与HashMap类似，但是是线程安全的。
4. ConcurrentLinkedQueue: 无界队列，线程安全。

20. Collection 和 Collections 有什么区别？

1. Collection：Collection 是 Java 中定义集合类的接口。它是所有集合类的父接口，定义了集合类的基本操作和行为。Collection 接口继承自 Iterable 接口，提供了对集合元素的基本操作，如添加、删除、遍历等。一些常见的实现类包括 List、Set 和 Queue。
2. Collections：Collections 是 Java 中的一个工具类，提供了一系列静态方法，用于操作集合类的工具方法。它包含了一些静态方法，用于对集合进行排序、搜索、同步等操作。这些方法可以用于操作任何实现了 Collection 接口的集合，如 List、Set 等。Collections 类中的方法是通过静态调用的方式来使用的，常用的一些方法包括 sort()、binarySearch()、synchronizedCollection() 等。

21. List、Set、Map 之间的区别是什么？

List、Set和Map是Java集合框架中三种常用的接口，它们具有不同的特点和用途：

1. List（列表）：

• 允许重复元素。
• 保留了元素的插入顺序。
• 可以根据索引访问元素。
• 常见的实现类有ArrayList（基于数组实现），LinkedList（基于链表实现）。

1. Set（集合）：

• 不允许重复元素，保证元素的唯一性。
• 不保留元素的插入顺序。
• 不提供根据索引访问元素的方式。
• 常见的实现类有HashSet（基于哈希表实现），TreeSet（基于红黑树实现）。

1. Map（映射）：

• 存储键值对（Key-Value）的集合。
• 不允许重复的键，但允许值的重复。
• 键是唯一的，通过键可以获取对应的值。
• 常见的实现类有HashMap（基于哈希表实现），TreeMap（基于红黑树实现），LinkedHashMap（基于链表和哈希表实现）。

总结：

• List适合需要按照插入顺序存储和访问元素的场景，允许重复元素。
• Set适合需要确保元素唯一性的场景，不关心元素的顺序。
• Map适合需要存储键值对，并且需要通过唯一键快速查找对应值的场景，键是唯一的，值可以重复。

22. HashMap 和 Hashtable 有什么区别？

HashMap和Hashtable是Java中两种常用的键值对存储容器，它们具有一些区别和不同的特点：

1. 线程安全性：

• HashMap是非线程安全的，不对多线程并发操作进行同步处理。如果在多线程环境下使用HashMap，需要自行处理线程安全问题。
• Hashtable是线程安全的，对多线程并发进行同步处理。它的方法都是同步的，适合在多线程环境下使用。

1. 允许键或值为null：

• HashMap允许键和值为null，即可以使用null作为键或值进行存储。
• Hashtable不允许键或值为null，如果尝试使用null，将会抛出NullPointerException。

1. 继承关系：

• HashMap继承自AbstractMap类，实现了Map接口。
• Hashtable继承自Dictionary类，实现了Map接口。Dictionary类是一个已经过时的类，不推荐使用。

1. 迭代器：

• HashMap的迭代器（Iterator）是fail-fast的，在迭代过程中如果其他线程对HashMap进行了修改，将会抛出ConcurrentModificationException异常。
• Hashtable的迭代器是不fail-fast的，在迭代过程中如果其他线程对Hashtable进行修改，不会抛出异常，但可能会导致迭代结果不确定。

1. 性能：

• 由于Hashtable在多线程环境下加锁同步，会引入一定的性能开销。
• HashMap不进行同步，较Hashtable在多线程环境下通常具有更好的性能。

需要注意的是，从Java 1.2版本开始，推荐使用HashMap而不是Hashtable，因为HashMap在大多数情况下具有更好的性能和灵活性。对于线程安全的需求，可以使用ConcurrentHashMap等并发集合类来替代Hashtable。

"Fail-fast"是一种软件开发中的设计理念和编程模式，用于在程序出现并发修改异常时尽早地检测并抛出异常ConcurrentModificationException，以避免潜在的不一致状态。它主要应用于迭代器和集合类的设计中。

23. 如何决定使用 HashMap 还是 TreeMap？

1. 排序需求：TreeMap是基于红黑树实现的，可以保持键的有序性，按键的自然顺序或自定义比较器进行排序。如果需要按照键的有序性进行遍历或检索，可以选择TreeMap。HashMap则不保证键的有序性。
2. 插入和查找频率：HashMap在插入和查找操作上的性能通常优于TreeMap。HashMap使用哈希表实现，具有常数时间复杂度的查找和插入操作。而TreeMap的插入和查找操作的时间复杂度为O(log N)，其中N是元素的数量。如果对于插入和查找的性能要求较高且不关心元素顺序，可以选择HashMap。
3. 键的唯一性：HashMap允许键为null，并允许键的重复。而TreeMap要求键不能为null，并且会根据键的自然顺序（或自定义比较器）来确保键的唯一性。如果需要保持键的唯一性，可以选择TreeMap。
4. 内存占用：TreeMap相对于HashMap更加复杂，需要额外的红黑树结构来维护键的有序性，可能会导致更高的内存占用。如果对于内存占用有限制，可以选择HashMap。

综上所述，一般情况下如果只需要快速的插入、查找或删除操作，并且不关心元素顺序，HashMap是更好的选择。而如果需要基于键的顺序进行遍历、范围查找或者保持键的唯一性，可以选择TreeMap

24. 说一下 HashMap 的实现原理？

HashMap 是 Java 中最常用的数据结构之一，它基于哈希表（Hash Table）实现。以下是 HashMap 的主要实现原理：

1. 数据结构：HashMap 内部使用数组和链表（或红黑树，Java 8+）来存储数据。

数组默认长度为16，负载因子为0.75

1. 哈希函数：当调用 put(key, value) 方法时，HashMap 首先会根据 key 的哈希码（通过 key 的 hashCode() 方法获取）计算出桶索引。依靠哈希函数，尽可能均匀地将键值对分布到桶中。
2. 解决哈希碰撞：由于不同的 key 可能产生相同的哈希码，所以可能出现哈希碰撞（多个键值对存储在同一个桶中）。为了解决哈希碰撞，HashMap 采用链表或红黑树来存储相同哈希码的键值对。在 Java 8+ 版本中，当链表中的元素数量大于一定阈值时，链表会转换为红黑树，提高查询效率。
3. 查找元素：当调用 get(key) 方法时，HashMap 根据 key 的哈希码定位到对应的桶，然后在该桶中遍历链表或红黑树，根据 key 的 equals() 方法找到目标键值对，并返回对应的值。
4. 扩容：当 HashMap 中的键值对数量超过负载因子（默认为 0.75）与桶数组容量的乘积时，会触发扩容操作。扩容会创建一个更大容量的新数组，并重新计算键值对的哈希码，然后重新分配至新的桶中，以提高散列性能。
5. 迭代顺序：HashMap 中的元素是无序的，遍历的顺序并不是插入的顺序。如果需要有序遍历，可以使用 LinkedHashMap。

需要注意的是，HashMap 是非线程安全的，如果在多线程环境下使用，建议使用线程安全的 ConcurrentHashMap 或进行适当的同步操作。

put() 首先会创建一个Entry对象，用来存储键和值，根据键的哈希值计算在数组中的位置，如果位置为null，则直接添加进去，如果不为null，调用equals通过遍历链表比较键是否相等，如果相等，则覆盖元素，如果不等，则会在链表后面添加节点，1.8开始当链表长度超过8，且数组长度大于64，会转换成红黑树。

如果存储的是自定义对象，需要重写equals和hashcode方法

LinkedHashMap 有序，因为底层维护了一个双向链表

25. 说一下 HashSet 的实现原理？

HashSet 是 Java 中常用的集合类，它实现了 Set 接口，并基于 HashMap 进行实现。HashSet 的实现原理如下：

1. 内部使用 HashMap：HashSet 内部使用 HashMap 来存储元素。HashMap 的键值对中，键表示 HashSet 中的元素，值固定为一个常量对象。
2. 数据结构：HashSet 由 HashMap 实现，实际上是一个 HashMap 的封装。HashSet 内部维护了一个 HashMap 对象，所有的元素都存储为 HashMap 中的键，而值对象则是一个随意选择的常量。
3. 不允许重复元素：HashSet 是基于HashMap 的键唯一性特性实现的。当向 HashSet 中添加元素时，它会调用 HashMap 的 put() 方法，并使用该元素作为键来添加到 HashMap 中。由于 HashMap 的键是唯一的，所以实现了元素在 HashSet 中的唯一性。
4. 哈希码和 equals 比较：当调用 HashSet 的 add() 方法时，HashSet 会获取元素的哈希码（通过元素的 hashCode() 方法）并计算桶索引。然后，它会在对应桶位置上的链表或红黑树中查找是否存在相同哈希码的元素。如果存在，则通过元素的 equals() 方法进行值比较，如果相等则不添加到集合中。
5. 允许空元素：HashSet 允许存储 null 元素。在 HashMap 的实现中，可以将 null 作为键存储在 HashMap 中。
6. 迭代顺序：HashSet 中的元素是无序的，遍历的顺序并不是插入的顺序。如果需要有序遍历，可以考虑使用 LinkedHashSet。

需要注意的是，HashSet 是非线程安全的，如果在多线程环境下使用，建议使用线程安全的集合类，如 ConcurrentHashSet 或进行适当的同步操作。

HashSet 的实现原理使得它具有了快速的元素查找和插入的特性，同时具备自动去重的功能。在平均情况下，HashSet 的插入和查找操作的时间复杂度都近似于 O(1)。

26. ArrayList 和 LinkedList 的区别是什么？

1. 内部数据结构：

• • ArrayList：内部使用动态数组（数组长度可变）来存储元素。它按索引进行访问和修改元素效率较高，但在插入和删除元素时需要移动其他元素。
  • LinkedList：内部使用双向链表来存储元素。每个元素包含存储的值和指向前一个和后一个元素的指针。在插入和删除元素时，仅需调整相邻元素的指针，效率较高，但随机访问元素效率较低。

1. 访问效率：

• • ArrayList：由于使用连续的内存空间存储元素，支持根据索引访问元素，所以在随机访问时效率较高，时间复杂度为O(1)。但在插入和删除元素时，需要移动其他元素，时间复杂度为O(n)。
  • LinkedList：由于使用链表存储元素，访问元素时需要从头节点或尾节点开始遍历链表，时间复杂度为O(n)。但在插入和删除元素时，仅需调整相邻节点的指针，时间复杂度为O(1)。

1. 内存消耗：

• • ArrayList：由于使用动态数组，每个元素连续存放在内存中，不需要额外的指针存储，因此相对节省内存空间。
  • LinkedList：由于使用链表，每个元素需要额外的指针来存储前后关系，因此相对消耗更多的内存空间。

1. 适用场景：

• • ArrayList：适用于需要频繁通过索引进行访问和修改元素的场景，例如按索引查找、更新、删除等操作。
  • LinkedList：适用于频繁进行插入、删除或只需要在链表的首尾进行操作的场景，例如队列、栈等。

27. 如何实现数组和 List 之间的转换？

要实现数组和List之间的转换，可以使用Java中提供的相应方法和构造函数进行转换。下面我将展示如何从数组转换为List以及如何从List转换为数组。

1. 从数组转换为List：

• • 使用Arrays类的.asList()方法可以将数组转换为List。这种转换操作是基于底层数组的，因此对数组或转换后的List的修改会相互影响。
  • 示例代码如下：

// 假设有一个整型数组
int[] array = {1, 2, 3, 4, 5};// 将数组转换为List
List<Integer> list = Arrays.asList(array);

1. 从List转换为数组：

• • 使用ArrayList的toArray()方法可以将List转换为数组。
  • 示例代码如下：

// 假设有一个整型List
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);// 将List转换为数组
Integer[] array = list.toArray(new Integer[list.size()]);

注意，在将List转换为数组时，需要使用toArray()方法，并传入一个具有相同类型的数组作为参数。如果不传入参数，toArray()方法将返回一个Object类型的数组。

另外，需要注意的是，通过上述转换方法得到的List或数组是固定长度的，无法进行添加或删除元素的操作。如果需要对List进行修改操作，可以创建一个新的ArrayList，并将转换后的List的元素添加到新的ArrayList中。

28. ArrayList 和Vector 的区别是什么？

ArrayList和Vector是Java集合框架中的两个常见的List实现类，它们在以下几个方面有一些区别：

1. 线程安全性：

• • ArrayList：ArrayList是非线程安全的，在多线程环境下使用时需要手动进行同步或使用其他线程安全的技术进行保护。
  • Vector：Vector是线程安全的，它的方法都使用了synchronized关键字进行同步。这意味着Vector适用于多线程环境下的并发访问。

1. 扩容机制：

• • ArrayList：ArrayList在扩容时会自动增加容量。当容量不足时，会创建一个更大的数组，并将原数组的元素复制到新数组中，扩容的增长因子是1.5。这可能会引起一定的性能损耗。
  • Vector：Vector在扩容时也会自动增加容量。当容量不足时，会创建一个更大的数组，并将原数组的元素复制到新数组中，扩容的增长因子是2。与ArrayList不同，Vector的扩容机制相对比较保守。

1. 初始容量增长：

• • ArrayList：ArrayList的默认初始容量为10，当添加元素时，如果容量不足，会进行自动扩容。
  • Vector：Vector的默认初始容量也为10，当添加元素时，如果容量不足，会进行自动扩容。

1. 效率：

• • ArrayList：由于ArrayList不进行线程同步处理，相比Vector的效率要高一些。因此，如果在单线程环境下使用，ArrayList是更好的选择。
  • Vector：由于Vector使用了同步机制，导致额外的开销，因此在单线程环境下，Vector的效率相对较低。

总的来说，ArrayList和Vector在功能上是相似的，都实现了List接口，但Vector是线程安全的并具有较为保守的扩容机制，适用于多线程的并发环境。而在单线程环境下，ArrayList由于没有同步的开销，可能会有更好的性能。根据具体的需求以及程序的并发情况，可以选择合适的集合类来使用。

29. Array 和 ArrayList 有何区别？

Array和ArrayList是Java中用于存储和操作一组元素的两种不同的数据结构，它们具有以下区别：

1. 大小固定性：

• • Array：数组的大小是固定的，一旦创建后，大小就不能改变。
  • ArrayList：ArrayList的大小是可变的，可以根据需要动态地添加或删除元素。

1. 类型：

• • Array：数组可以存储基本数据类型（如int，char等）和对象类型（如String，自定义类等）的元素。
  • ArrayList：ArrayList只能存储对象类型（Object）的元素，不能直接存储基本数据类型，需要使用对应的包装类（如Integer，Character等）。

1. 功能：

• • Array：数组提供了与索引直接关联的快速访问元素的能力，可以根据索引进行读取、修改和删除元素。但没有提供内置的支持添加和删除元素的方法，需要手动调整数组的大小和元素的位置。
  • ArrayList：ArrayList提供了丰富的方法来添加、删除和修改元素，而且内部自动处理元素的增长和缩减。可以通过索引访问元素，也可以使用诸如add()、remove()、set()等方法进行操作。

1. 内存管理：

• • Array：数组在内存中是连续存储的，占用一块固定大小的内存空间。
  • ArrayList：ArrayList在内存中使用动态数组实现，根据需要可以自动调整内部数组的大小，适时扩容或缩减。因此，ArrayList可以根据元素数量的变化来使用有效的内存。

综上所述，Array是一种固定大小的数组，支持快速访问元素，但不提供动态添加和删除元素的方法。ArrayList是一个动态大小的数组，提供了丰富的方法来操作元素，适用于需要动态调整大小并进行增删操作的场景。选择使用哪种数据结构取决于具体的需求和操作模式

30. 在 Queue 中 poll()和 remove()有什么区别？

在Queue接口中，poll()和remove()都是用于移除队列中的元素的方法，它们在移除失败时的行为稍有不同：

1. poll()方法：

• • 如果队列为空，poll()方法返回null。
  • 如果队列不为空，poll()方法会移除并返回队列头部的元素。

1. remove()方法：

• • 如果队列为空，remove()方法会抛出NoSuchElementException异常。
  • 如果队列不为空，remove()方法会移除并返回队列头部的元素。

因此，主要区别在于当队列为空时的行为不同。

使用poll()方法可以在队列为空时返回null，而不会抛出异常。这种情况下，我们可以根据返回值是否为null来判断是否成功移除了元素。

使用remove()方法则需要注意，如果队列为空，调用remove()方法会抛出NoSuchElementException异常。因此，在使用remove()方法时，通常需要先检查队列是否为空，以避免异常的抛出。

一般来说，如果你不确定队列是否为空，并希望在移除元素时得到一个特定的返回值来表示操作结果，可以使用poll()方法。如果你确定队列不为空，并且希望在队列为空时抛出异常，可以使用remove()方法。

总的来说，poll()方法在移除空队列时返回null，而remove()方法则会抛出异常。根据具体的需求和处理方式，选择适合的方法进行元素的移除操作。

31. 哪些集合类是线程安全的？

1. Vector：Vector是线程安全的，它的方法都使用了synchronized关键字进行同步，适合在多线程环境中使用。
2. Hashtable：Hashtable也是线程安全的，它的方法也使用了synchronized关键字进行同步，适合在多线程环境中使用。然而，Hashtable已经在Java 1.2中被更现代化的HashMap取代，因为HashMap提供了更好的性能和扩展性。
3. ConcurrentHashMap：ConcurrentHashMap是Java 5引入的高度并发的线程安全哈希表实现。它使用细粒度的锁机制，使得多个线程可以同时读取而不会阻塞，从而提高了并发性能。
4. CopyOnWriteArrayList：CopyOnWriteArrayList是一个线程安全的列表实现，它通过对每次写操作都创建一个新的副本来实现线程安全。这意味着写操作会比较耗时，但读操作不会阻塞。
5. ConcurrentLinkedQueue：ConcurrentLinkedQueue是一个线程安全的无界队列实现，它使用非阻塞算法，适用于多线程的生产者-消费者模式。

32. 迭代器 Iterator 是什么？

迭代器（Iterator）是Java集合框架中常用的一种设计模式，它提供了一种便捷的方式来遍历并访问集合中的元素，而不需要暴露集合内部的结构细节。

迭代器模式通过抽象出共同的遍历行为，使得不同类型的集合类都可以用相同的方式进行遍历操作。迭代器提供了一种统一的访问集合元素的方式，无论集合是数组、链表还是其他数据结构，都可以通过迭代器按照一定的顺序逐个访问元素。

在Java中，迭代器是通过Iterator接口实现的。该接口定义了一些基本的方法，包括hasNext()用于判断是否还有下一个元素，next()用于获取下一个元素，remove()用于从集合中删除当前迭代过程中访问的元素（可选操作）。

• boolean hasNext(): 检查迭代器是否还有下一个元素。
• E next(): 返回迭代器的下一个元素，并将指针移动到下一个位置。
• void remove(): 从集合中移除迭代器最后访问的元素（可选操作）。

迭代器模式的优点在于它提供了一种与集合的具体实现解耦的方式，使得集合类可以独立变化而不影响使用迭代器的代码。同时，迭代器还提供了一种安全的方式来遍历集合，避免了在遍历过程中修改集合结构导致的并发修改异常。

迭代器是集合的一个抽象表示，它提供了一个统一的界面来访问集合中的元素，而不暴露底层的数据结构和实现细节。

当我们使用迭代器进行遍历时，迭代器会维护一个内部状态来跟踪当前遍历的位置。在遍历过程中，如果集合发生了变化（比如添加、删除元素），迭代器会注意到这个变化，并且在下一次检索元素时，确保返回的元素是基于最新的集合状态。

这样一来，即使在遍历过程中修改了集合的结构，例如删除或添加元素，也不会出现并发修改异常（ConcurrentModificationException）或非法状态异常（IllegalStateException）。迭代器会提供一个一致的、安全的遍历方式，确保我们能够正确地访问集合中的元素。

需要注意的是，迭代器只能单向遍历集合，即从前往后逐个访问元素。如果需要逆向遍历，可以考虑使用ListIterator接口，它是Iterator的子接口，提供了向前和向后遍历的功能

a. 迭代器可以遍历Map集合吗

是的，迭代器可以用于遍历Map集合。Map是一种键值对的集合，可以使用Entry对象来表示每个键值对。Map接口中的内部Entry接口提供了getKey()和getValue()方法，可以用于获取键和值。

在Java中，可以通过Map的entrySet()方法获取包含所有键值对的Set集合，然后使用迭代器来遍历这个集合。以下是一个示例：吧

Map<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
Iterator<Map.Entry<String, Integer>> iterator = entrySet.iterator();while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();String key = entry.getKey();Integer value = entry.getValue();System.out.println("Key: " + key + ", Value: " + value);
}

33. Iterator 怎么使用？有什么特点？

1. 获取集合的迭代器对象：通过调用集合类的iterator()方法来获取该集合的迭代器对象。例如：

List<String> myList = new ArrayList<>();
// 添加元素到集合
Iterator<String> iterator = myList.iterator();

1. 遍历集合元素：通过迭代器对象调用hasNext()方法来检查是否还有下一个元素，然后通过next()方法获取该元素。可以使用循环结构（如while或for）来遍历集合中的所有元素。例如：

while (iterator.hasNext()) {String element = iterator.next();// 对元素进行操作System.out.println(element);
}

1. 可选操作：如果需要，在遍历过程中可以调用迭代器的remove()方法删除当前迭代过程中访问的元素。例如：

iterator.remove();

迭代器的特点如下：

• 迭代器提供了一种统一的访问集合元素的方式，无论集合的具体实现是数组、链表或其他数据结构，我们都可以使用相同的代码来进行遍历操作。
• 迭代器实现了在遍历过程中逐个获取元素的功能，允许我们按照一定的顺序遍历一个集合。
• 迭代器是单向的，只能从前往后遍历集合元素。如果需要逆向遍历元素，可以考虑使用ListIterator接口。
• 迭代器提供了一种安全的遍历方式，避免了在遍历过程中修改集合结构导致的并发修改异常。

34. Iterator 和 ListIterator 有什么区别？

Iterator和ListIterator都是Java集合框架中的迭代器接口，用于遍历集合元素。它们之间的区别如下：

1. 遍历方向：

• • Iterator只能单向遍历集合元素，从前往后。
  • ListIterator可以双向遍历集合元素，既可以从前往后，也可以从后往前。

1. 定位能力：

• • Iterator只能通过hasNext()和next()方法获取下一个元素，并不能获得当前元素的索引位置。
  • ListIterator在Iterator的基础上增加了previous()和hasPrevious()方法，使其能够向前遍历并获取前一个元素，同时还提供了nextIndex()和previousIndex()方法来获取当前元素的索引位置。

1. 修改集合：

• • Iterator提供了remove()方法，允许在遍历过程中删除当前迭代的元素。
  • ListIterator在Iterator的基础上增加了add()和set()方法，可以在遍历过程中添加新元素或修改当前迭代的元素。

1. 支持的集合类型：

• • Iterator可用于遍历大部分Java集合框架中的集合，如List、Set、Queue等。
  • ListIterator主要用于遍历List接口的实现类，如ArrayList、LinkedList等，因为List才具备向前遍历和修改操作的能力。

35. 怎么确保一个集合不能被修改？

要确保一个集合不能被修改，可以采取以下几种方法：

1. 使用不可变集合：在Java中，有一些集合类是不可变的，即它们在创建后不能被修改。例如，Collections类提供了unmodifiableXXX()方法来创建不可变的集合，如unmodifiableList()、unmodifiableSet()和unmodifiableMap()等。通过使用这些方法，我们可以将可变的集合转换为不可变的集合，从而防止对集合进行修改。

List<String> mutableList = new ArrayList<>();
mutableList.add("元素1");
mutableList.add("元素2");List<String> immutableList = Collections.unmodifiableList(mutableList);
immutableList.add("元素3"); // 会抛出UnsupportedOperationException异常

需要注意的是，虽然不可变集合本身不可修改，但如果集合中包含的元素是可变对象，那么这些元素的状态可能是可以被修改的。

1. 使用只读接口引用：将集合的可变引用限制为只读接口，而不是具体的可修改接口。例如，将可变的List引用声明为List接口，而不是ArrayList类。

List<String> mutableList = new ArrayList<>(); // 可变的引用
List<String> readOnlyList = mutableList; // 只读的引用
readOnlyList.add("元素1"); // 会抛出UnsupportedOperationException异常

这样做可以防止通过只读接口进行修改操作，但如果有其他对可变引用的引用，还是可以对集合进行修改。

1. 自定义不可修改的集合类：自定义一个集合类，重写修改集合的方法，并抛出UnsupportedOperationException异常来阻止修改操作。

public class ImmutableCollection<E> implements Collection<E> {// 省略实现，重写修改集合的方法，抛出UnsupportedOperationException异常
}

这种方法可以创建一个完全不可修改的集合类，无论是通过接口方法还是直接修改底层数据结构，都无法修改集合。

无论采用哪种方法，都需要注意的是，如果集合中的元素是可变对象，那么这些对象的状态可能仍然可以被修改。要确保集合中的元素也是不可变的，需要采取相应的措施来保证元素的不可变性。

另外，需要注意的是，以上方法只能防止直接修改集合本身的操作，对于集合中对象的属性修改是无法控制的。如果需要完全保证集合及其元素的不可变性，可以考虑使用不可变对象或进行深度拷贝来防止任何修改。