Java集合

阅读提示

建议先看题目目录，再按“概念 -> 原理 -> 场景 -> 优化”顺序复习。
每题先讲结论，再补关键机制和项目实践，回答会更稳。

回答提示：是一种比较通俗的解释，比较好理解，如果‘参考答案’不太好记住，可以直接复习回答提示也可以。

1、Java中的集合类有哪些？如何分类的？(此问题基本不会被问到，但是要大体理解整个集合的内容，如果能记住此问题（灵活记住），面试集合的基础问题基本都可以回答)

回答提示：

• List（列表）：List接口及其实现类用于存储一组有序的元素。元素可以重复，且可以通过索引访问。常见的List实现类有ArrayList、LinkedList等。ArrayList基于动态数组实现，访问元素速度快；LinkedList基于双向链表实现，插入和删除操作效率高。
• Set（集合）：Set接口及其实现类用于存储一组无序且唯一的元素。Set不允许出现重复元素，因此常用于去重操作。常见的Set实现类有HashSet、TreeSet等。HashSet基于哈希表实现，元素存储无序；TreeSet基于红黑树实现，元素会按照自然顺序或者自定义顺序排序。
• Queue（队列）：Queue接口及其实现类用于在元素之间定义一种先进先出（FIFO）的排序方式。常见的Queue实现类有LinkedList（也实现了List接口）、PriorityQueue等。LinkedList可以用作双端队列；PriorityQueue是一个基于优先级堆的无界队列，元素的排序方式可以通过比较器来定义。
• Map（映射）：Map接口及其实现类用于存储键值对。键是唯一的，每个键都映射到一个值。常见的Map实现类有HashMap、TreeMap等。HashMap基于哈希表实现，键值对存储无序；TreeMap基于红黑树实现，键会按照自然顺序或者自定义顺序排序。

参考回答：

• 集合类存放于 Java.util 包中，主要有 3 种：set(集）、list(列表包含 Queue）和 map(映射)。
• Collection：Collection 是集合 List、Set、Queue 的最基本的接口。
• Iterator：迭代器，可以通过迭代器遍历集合中的数据
• Map：是映射表的基础接口

img

• 一定要牢牢记住这张图，大多比较浅的面试题都是从这上面问的。 arrayList的扩容机制认为是1.5倍就可以了

2、那些集合是线程安全的？

参考回答：

1. Vector：一个线程安全的List实现，它的大部分方法都是同步的，因此可以在多线程环境中使用。不过，由于同步操作会带来性能开销，所以在不需要线程安全的场合，建议使用ArrayList。
2. Hashtable：一个线程安全的Map实现，它同样是同步的，可以在多线程环境中使用。与HashMap相比，Hashtable的性能可能稍差一些，因为同步操作会增加额外的开销。
3. Stack：一个线程安全的栈实现，它也是同步的，可以在多线程环境中使用。不过，由于栈这种数据结构的使用场景相对较少，所以在实际开发中可能会更少用到Stack。
4. ConcurrentHashMap：一个线程安全的 HashMap 实现。早期版本（JDK 1.7 及以前）使用分段锁（Segment Locking）技术来提升并发性能，JDK 1.8 以后则使用了更加细粒度的锁，如链表或红黑树节点上的 synchronized 和 CAS 操作。在多线程环境下，ConcurrentHashMap 的并发性能通常优于 Hashtable 以及通过 Collections.synchronizedMap(new HashMap<>()) 包装得到的同步 HashMap，因为后两者都是对整个 map 加锁，从而限制了并发能力，而 ConcurrentHashMap 则支持更高的并发访问。
5. CopyOnWriteArrayList：一个线程安全的List实现，它通过在写操作时复制整个数组来实现线程安全。这种策略适用于读多写少的场景，因为写操作会涉及到复制整个数组，所以性能开销较大。

3、ArrayList的扩容机制是什么？

回答提示：

• 初始容量：ArrayList在创建时默认有一个初始容量，通常是10（但在某些版本或实现中可能有所不同）。
• 扩容触发：当向ArrayList中添加元素，且当前元素数量达到容量上限时，就会触发扩容操作。
• 扩容策略：ArrayList的扩容策略是增长大约50%的容量。
• 数组复制：扩容过程中，ArrayList会创建一个新的、更大容量的数组，并将原有数组中的所有元素复制到新数组中。

参考回答：

• ArrayList的扩容机制是这样的：当向ArrayList中添加元素，而当前数组容量不足以容纳更多元素时，ArrayList会自动进行扩容。具体来说，它会创建一个新的数组，新数组的长度通常是当前数组长度的1.5倍（也就是增长50%，但这个值不是固定的，不同的JVM实现可能有所不同，有的是直接扩容为原来的两倍）。然后，ArrayList会将当前数组中的所有元素复制到新数组中，并将新数组设置为当前数组。这样，ArrayList就拥有了更大的容量，可以继续添加更多元素。

4、ArrayList和linkedList的区别？

回答提示：

• 内部实现：ArrayList是基于动态数组实现的，元素在内存中连续存储；而LinkedList则是基于双向链表实现，元素通过指针相互连接。
• 随机访问：ArrayList支持快速随机访问，时间复杂度为O(1)；LinkedList则需要遍历，时间复杂度为O(n)。
• 内存占用：LinkedList每个节点除了存储数据外，还需要存储指向前一个和后一个节点的指针，因此比ArrayList更占内存。
• 使用场景：ArrayList适用于需要频繁进行随机访问的场景；而LinkedList则更适用于需要频繁进行插入和删除操作的场景。

参考回答：

• ArrayList：基于动态数组，连续内存存储，适合下标访问（随机访问），扩容机制：因为数组长度固定，超出长度存数据时需要新建数组，然后将老数组的数据拷贝到新数组，如果不是尾部插入数据还会涉及到元素的移动（往后复制一份，插入新元素），使用尾插法并指定初始容量可以极大提升性能、甚至超过linkedList（需要创建大量的node对象）
• LinkedList：基于链表，可以存储在分散的内存中，适合做数据插入及删除操作，不适合查询：需要逐一遍历
• 遍历LinkedList必须使用iterator不能使用for循环，因为每次for循环体内通过get(i)取得某一元素时都需要对list重新进行遍历，性能消耗极大。另外不要试图使用indexOf等返回元素索引，并利用其进行遍历，使用indexlOf对list进行了遍历，当结果为空时会遍历整个列表。

5、HashMap和HashTable有什么区别？

回答提示：

• 线程安全性：HashMap是非线程安全的，而HashTable是线程安全的。HashTable通过synchronized关键字实现同步，但可能导致性能下降。
• null值处理：HashMap允许null作为键和值，而HashTable不允许。
• 性能：由于HashMap不需要考虑线程同步，通常性能更高。

参考回答：

区别 ：

线程安全性

• HashMap方法没有synchronized修饰，线程非安全，HashTable线程安全；

空键和空值：

• HashMap允许key和value为null，而HashTable不允许

历史遗留：（了解）

• Hashtable 是 Java 1.0 中的遗留类，虽然仍然可以使用，但通常建议使用 HashMap，并结合 java.util.concurrent 包中的现代并发类来处理多线程问题。
• HashMap 是在 Java 2 中引入的，设计更现代化，使用也更加灵活。

迭代器：(了解)

• HashMap 使用的是快速失败（fail-fast）的迭代器，如果在创建迭代器后对集合进行了结构上的修改（除了使用迭代器自身的 remove 方法外），迭代器会抛出 ConcurrentModificationException。
• Hashtable 使用的是枚举（Enumeration），不是快速失败的迭代器。

性能：（了解）

• 在没有线程安全需求的场景中，HashMap 通常比 Hashtable 性能更高，因为它没有同步的开销。