集合的框架体系

一、集合概述

主要分为两大类：Collection接口体系和Map接口体系。

（一）Collection接口体系

Collection是集合框架中的顶层接口，它又分为List、Set和Queue（队列）三种主要的子接口。

（二）Map接口体系

Map接口用于存储键值对，键是唯一的，通过键可以快速检索对应的值。

二、List接口及其实现类

List是一个有序的集合，允许重复的元素。实现类有ArrayList、LinkedList和Vector。

（一）ArrayList

• 特点：基于动态数组实现，随机访问效率高（时间复杂度为O(1)），但插入和删除元素效率较低（平均时间复杂度为O(n)），因为可能需要移动大量元素。
• 线程安全性：非线程安全，如果需要在多线程环境中使用，可以通过Collections.synchronizedList方法进行包装。
• 适用场景：适用于频繁访问元素，而插入和删除操作较少的场景。

（二）LinkedList

• 特点：基于双向链表实现，插入和删除元素效率高（时间复杂度为O(1)），但随机访问效率较低（时间复杂度为O(n)）。它还提供了额外的addFirst、addLast、removeFirst、removeLast等方法，方便操作链表的头部和尾部。
• 线程安全性：非线程安全，同样可以通过Collections.synchronizedList方法进行包装。
• 适用场景：适用于频繁进行插入和删除操作，且对随机访问要求不高的场景。

（三）Vector

• 特点：与ArrayList类似，也是基于动态数组实现，但它是线程安全的。内部通过synchronized方法来保证线程安全，不过这也导致了它的性能相对较低。
• 适用场景：在单线程环境下，一般不推荐使用Vector，而是使用ArrayList，并通过其他方式来保证线程安全（如使用Collections.synchronizedList或CopyOnWriteArrayList等）。

三、Set接口及其实现类

Set是一个不允许重复元素的集合，实现类有HashSet、LinkedHashSet和TreeSet。

（一）HashSet

• 特点：基于哈希表实现，元素的添加、删除和查找效率都很高（平均时间复杂度为O(1)），但不保证元素的顺序。它不允许存储null键，但可以存储null值。
• 线程安全性：非线程安全，可以通过Collections.synchronizedSet方法进行包装。
• 适用场景：适用于需要快速判断元素是否存在，且不需要保证元素顺序的场景。

（二）LinkedHashSet

• 特点：是HashSet的子类，它在HashSet的基础上增加了链表来记录元素的添加顺序，因此可以保证元素的迭代顺序与添加顺序一致。它的性能与HashSet相近，但在迭代时会保持元素的顺序。
• 线程安全性：非线程安全，同样可以通过Collections.synchronizedSet方法进行包装。
• 适用场景：适用于需要保证元素顺序，同时又需要快速判断元素是否存在的情况。

（三）TreeSet

• 特点：基于红黑树实现，元素会按照自然顺序（或指定的比较器顺序）进行排序。它提供了许多与排序相关的操作，如first、last、headSet、tailSet等。不允许存储null值。
• 线程安全性：非线程安全，可以通过Collections.synchronizedSortedSet方法进行包装。
• 适用场景：适用于需要对元素进行排序的场景。

四、Map接口及其实现类

Map接口用于存储键值对，实现类有HashMap、LinkedHashMap、TreeMap和Hashtable。

（一）HashMap

• 特点：基于哈希表实现，键是唯一的，值可以重复。它提供了高效的插入、删除和查找操作（平均时间复杂度为O(1)）。在Java 8及以后版本中，当哈希冲突较多时，会将链表转换为红黑树，进一步优化性能。它不允许存储null键，但可以存储null值。
• 线程安全性：非线程安全，可以通过Collections.synchronizedMap方法进行包装，或者使用ConcurrentHashMap来实现线程安全。
• 适用场景：适用于需要快速通过键查找值，且对线程安全要求不高的场景。

（二）LinkedHashMap

• 特点：是HashMap的子类，它在HashMap的基础上增加了双向链表来记录元素的访问顺序（或插入顺序）。它提供了两种迭代顺序：插入顺序和访问顺序。它的性能与HashMap相近，但在迭代时会保持元素的顺序。
• 线程安全性：非线程安全，可以通过Collections.synchronizedMap方法进行包装。
• 适用场景：适用于需要保持元素顺序，同时又需要快速通过键查找值的情况。

（三）TreeMap

• 特点：基于红黑树实现，键会按照自然顺序（或指定的比较器顺序）进行排序。它提供了许多与排序相关的操作，如firstKey、lastKey、headMap、tailMap等。不允许存储null键。
• 线程安全性：非线程安全，可以通过Collections.synchronizedSortedMap方法进行包装。
• 适用场景：适用于需要对键进行排序的场景。

（四）Hashtable

• 特点：与HashMap类似，也是基于哈希表实现，但它是一个线程安全的类。内部通过synchronized方法来保证线程安全，不过这也导致了它的性能相对较低。它不允许存储null键和null值。
• 适用场景：在单线程环境下，一般不推荐使用Hashtable，而是使用HashMap，并通过其他方式来保证线程安全（如使用ConcurrentHashMap等）。

五、集合的性能比较

在实际开发中，选择合适的集合类型需要综合考虑性能、线程安全性和功能需求等因素。以下是一些常见集合的性能比较：

• 随机访问性能：ArrayList > LinkedList。
• 插入和删除性能：LinkedList > ArrayList。
• 线程安全：Vector、Hashtable、ConcurrentHashMap > ArrayList、HashMap、LinkedList。
• 排序性能：TreeSet、TreeMap > HashSet、HashMap。

六、集合的遍历方式

在面试中，集合的遍历方式也是一个常见的考点。以下是几种常见的遍历方式：

（一）for-each循环

java复制

List list = Arrays.asList("a", "b", "c");
for (String s : list) {
    System.out.println(s);
}

（二）迭代器

java复制

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    System.out.println(s);
}

（三）Stream API（Java 8及以上版本）

java复制

list.stream().forEach(System.out::println);

（四）Lambda表达式（Java 8及以上版本）

java复制

list.forEach(System.out::println);

七、面试相关

（一）ArrayList和LinkedList的区别是什么？

• ArrayList：基于动态数组实现，随机访问效率高，插入和删除效率低，非线程安全。
• LinkedList：基于双向链表实现，插入和删除效率高，随机访问效率低，非线程安全。

（二）HashMap和Hashtable的区别是什么？

• HashMap：基于哈希表实现，非线程安全，允许存储null键和null值。
• Hashtable：基于哈希表实现，线程安全，不允许存储null键和null值。

（三）如何保证线程安全？

• 对于ArrayList、HashMap等非线程安全的集合，可以通过Collections.synchronizedList、Collections.synchronizedMap等方法进行包装，或者使用Vector、Hashtable等线程安全的集合，还可以使用ConcurrentHashMap等并发集合。

八、算法复杂度分析和原理相关

时间复杂度：时间复杂度表示了算法的执行时间与数据规模之间的增长关系

O(1)、O(n)、O(n^2)、O(logn)， 速记口诀：常对幂指阶

空间复杂度：空间复杂度全称是渐进空间复杂度，表示算法占用的额外存储空间与数据规模之间的增长关系，我们常见的空间复杂度就是O(1),O(n),O(n ^2)，其他像对数阶的复杂度几乎用不到，因此空间复杂度比时间复杂度分析要简单的多。

List相关

结构：数组（Array），是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

List数组下标为什么从0开始？

寻址公式是：baseAddress+ i * dataTypeSize，计算下标的内存地址效率较高；

List查找的时间复杂度？

• 随机(通过下标)查询的时间复杂度是O(1)
• 查找元素（未知下标）的时间复杂度是O(n)
• 查找元素（未知下标但排序）通过二分查找的时间复杂度是O(logn)

List插入和删除的负责度？

插入和删除的时候，为了保证数组的内存连续性，需要挪动数组元素，平均时间复杂度为O(n)

ArrayList底层的实现原理是什么？

数据结构-->动态的数组

初始容量-->初始容量为0，当第一次添加数据的时候才会初始化容量为10

扩容逻辑-->扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组

添加逻辑:

• 确保数组已使用长度（size）加1之后足够存下下一个数据
• 计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）
• 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。?
• 返回添加成功布尔值。

如何实现数组和List之间的转换?

数组转List :使用JDK中java.util.Arrays工具类的asList方法-->Arrays.asList();,准换后list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

List转数组:使用List的toArray方法。无参toArray方法返回 Object数组，传入初始化长度的数组对象，返回该对象数组;如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响；

ArrayList 和 LinkedList 的区别是什么？

LinkedList的数据结构：链表

单向链表：链表中的每一个元素称之为结点（Node）物理存储单元上，非连续、非顺序的存储结构

单向链表：每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next

单向链表时间复杂度分析：

查询/插入/删除：

• 只有在查询头节点的时候不需要遍历链表，时间复杂度是O(1)
• 查询其他结点需要遍历链表，时间复杂度是O(n)

双向链表：支持两个方向成链

• 每个结点不止有一个后继指针 next 指向后面的结点
• 有一个前驱指针 prev 指向前面的结点

对比单链表：

• 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址
• 支持双向遍历，这样也带来了双向链表操作的灵活性

双向链表时间复杂度分析：

查询/插入/删除：

• 查询头尾结点的时间复杂度是O(1)
• 平均的查询时间复杂度是O(n)
• 给定节点找前驱节点的时间复杂度为O(1)

ArrayList和LinkedList的区别是什么？

• 数据结构：ArrayList 是动态数组，LinkedList 是双向链表
• 操作数据效率：

查找：都是时间复杂度都是O(n)

新增和删除：

ArrayList尾部插入和删除时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)

LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)

• 内存空间占用

ArrayList底层是数组内存连续，节省内存

LinkedList 是双向链表需要存储数据，和两个指针，更占用内存

• 线程安全

ArrayList和LinkedList都不是线程安全的

如果需要保证线程安全，有两种方案：

• 在方法内使用，局部变量则是线程安全的
• 使用线程安全的LinkedList
• List