Java集合框架详解：List、Set、Map及其实现类的使用与特性 第二章

目录

一、List接口及其常见实现类

List接口定义与特性：

ArrayList：

Vector与Stack：

二、Set接口及其常见实现类

Set接口定义与特性：

HashSet：

TreeSet：

LinkedHashSet：

一、List接口及其常见实现类

List接口定义与特性：

List接口是Java集合框架中一个重要的接口，继承自Collection接口，它代表一个有序的元素序列，允许重复元素。List接口的主要特性如下：

1. 有序性：List中的元素按照插入顺序保持严格的先后关系，可以通过索引来精确地定位和访问任何一个元素。

2. 允许重复：同一个元素可以在List中出现多次，没有唯一性限制。

3. 增删改查方法：

   • 增：add(E element)将元素添加到列表末尾；add(int index, E element)在指定位置插入元素。
   • 删：remove(Object obj)移除首次出现的指定元素；remove(int index)移除指定索引处的元素。
   • 改：set(int index, E element)用新元素替换指定索引处的原有元素。
   • 查：get(int index)返回指定索引处的元素；indexOf(Object obj)返回指定元素首次出现的索引（不存在则返回-1）；contains(Object obj)检查列表是否包含指定元素。

4. 其他常用方法：

   • 列表操作：size()返回列表长度；isEmpty()判断列表是否为空；clear()清空列表；addAll(Collection<? extends E> c)添加一个集合中的所有元素到列表。
   • 迭代与列表迭代器：提供iterator()方法返回迭代器，用于遍历列表；还提供listIterator()返回列表迭代器，除了具备普通迭代器功能外，还支持双向遍历、通过索引访问元素以及在迭代过程中插入或替换元素。

ArrayList：

ArrayList是List接口的一个常用实现类，基于动态数组实现。其特性与适用场景如下：

实现原理：ArrayList内部维护一个Object类型的数组，随着元素的添加，当容量不足时自动扩容（通常是当前容量的1.5倍）。元素的访问、插入和删除主要通过索引来操作数组元素。

优点：

• 查询速度快：由于采用数组存储，通过索引直接访问元素，时间复杂度为O(1)。
• 随机访问高效：支持通过索引进行快速定位和修改。

缺点：

• 插入和删除慢：在非末尾位置插入或删除元素时，需要移动后续元素以保持连续性，时间复杂度为O(n)。
• 线程不安全：ArrayList未提供内在的线程同步机制，不适合在多线程环境下直接共享使用，除非外部进行同步控制。

适用场景：

• 当需要频繁进行随机访问或按索引进行操作时。
• 对列表的并发访问控制有严格要求，但可通过Collections.synchronizedList()方法包装得到线程安全版本。

LinkedList：

LinkedList同样是List接口的一个实现类，基于双向链表（双端链表）实现。其特性与适用场景如下：

实现原理：LinkedList内部由节点（Node）组成，每个节点包含元素本身以及指向前后节点的引用。元素的添加、删除主要通过调整节点间的引用关系实现。

优点：

• 插入和删除快：在任何位置插入或删除元素仅需改变相邻节点的引用，时间复杂度为O(1)（平均情况下，最坏情况为O(n)）。
• 支持双端操作：除了常规的添加、删除、查询等方法外，还提供了在头部和尾部进行操作的方法，如addFirst(), addLast(), removeFirst(), removeLast()等。

缺点：

• 查询慢：由于元素并非连续存储，查询元素需要从头或尾部开始逐个遍历，时间复杂度为O(n)。
• 线程不安全：与ArrayList类似，LinkedList也不具备线程同步机制，不适用于多线程环境下的直接共享。

适用场景：

• 当需要频繁进行元素的插入、删除操作，尤其是列表中间位置的操作时。
• 需要利用双端特性进行栈、队列操作时。

Vector与Stack：

Vector是早期与ArrayList类似的基于动态数组的List实现，主要区别在于Vector是线程安全的，其方法内部已经做了同步处理。由于同步带来的性能开销，以及ArrayList在Java 1.2之后引入并逐渐成为首选，Vector在现代编程实践中较少使用，除非确实需要一个线程安全的List且不介意牺牲一些性能。

Stack继承自Vector，实现了后进先出（LIFO）栈的数据结构。它提供了专门的push(E item)（入栈）、pop()（出栈）、peek()（查看栈顶元素而不移除）等方法。虽然Stack类依然存在，但在现代Java编程中，更推荐使用Deque接口（如ArrayDeque）来实现栈的功能，因为Deque提供了更丰富的方法和更好的性能。

总结起来，List接口及其常见实现类（ArrayList、LinkedList、Vector、Stack）提供了多样化的列表数据结构选择，开发者应根据实际需求（如数据规模、操作类型、并发要求等）来选择最合适的实现。

二、Set接口及其常见实现类

Set接口定义与特性：

Set接口是Java集合框架中的一个重要接口，继承自Collection接口，它代表一个不允许重复元素的集合，其主要特性如下：

1. 无序性：Set中的元素没有固定的顺序，即不支持索引访问，也无法通过索引来确定元素的位置。遍历Set的结果可能因插入顺序、哈希值分布等因素而不同，但不影响元素本身的正确性。

2. 不允许重复：Set保证集合内元素的唯一性。判断元素是否重复的标准是通过元素的equals()方法和hashCode()方法。如果集合中已经存在一个与待添加元素相等（即equals()返回true）的元素，那么新元素将无法添加到Set中。

3. 主要操作方法：

   • 增：add(E element)尝试将元素添加到Set中，如果集合中已有相同元素则添加失败，返回false。
   • 删：remove(Object obj)移除Set中首次遇到的与指定对象相等的元素，成功移除返回true。
   • 查：contains(Object obj)检查Set是否包含指定对象，包含则返回true。
   • 集合并集、交集、差集：通过addAll(Collection<? extends E> c), retainAll(Collection<?> c), removeAll(Collection<?> c)等方法与其他集合进行集合运算。
   • 迭代：通过iterator()方法返回迭代器，遍历Set中的所有元素。

HashSet：

HashSet是Set接口的一个常用实现类，基于哈希表（HashMap）实现。其特性与适用场景如下：

实现原理：HashSet内部使用HashMap存储元素，元素作为HashMap的键（key），值（value）则是一个无关紧要的固定对象。通过哈希函数将元素映射到哈希表的桶中，通过比较哈希值和equals()方法确保元素唯一性。

优点：

• 查找速度快：通过哈希表实现，平均时间复杂度接近O(1)，查找、添加、删除操作效率高。
• 不保证元素顺序：由于哈希表的无序性，HashSet也不保证元素的插入或遍历顺序。

缺点：

• 不保证元素顺序：这也是一个缺点，如果需要保持元素插入顺序或自然排序，需选择其他Set实现。
• 线程不安全：HashSet不是线程安全的，若在多线程环境下使用，需自行进行同步控制或使用Collections.synchronizedSet()方法包装得到线程安全版本。

适用场景：

• 当需要快速查找、添加、删除元素，且不关心元素的顺序时。
• 需要一个无重复元素的集合，且对性能有较高要求时。

TreeSet：

TreeSet是另一个Set接口的实现类，基于红黑树（自平衡二叉查找树）实现。其特性与适用场景如下：

实现原理：TreeSet内部使用NavigableMap（如TreeMap）存储元素，元素作为键（key），值（value）同样是一个固定对象。红黑树保证了元素的有序性，且插入、删除、查找等操作能在对数时间内完成。

优点：

• 自动排序：TreeSet会根据元素的自然排序（实现Comparable接口）或提供的Comparator进行排序，遍历结果始终有序。
• 查找速度较HashSet慢但稳定：由于红黑树的特性，查找、添加、删除操作的时间复杂度为O(log n)，相比HashSet在大数据量下性能更稳定。

缺点：

• 插入、删除、查找性能略低于HashSet：在小数据量下可能感觉不到差异，但在大规模数据下，尤其在频繁插入删除的情况下，性能不如HashSet。
• 线程不安全：与HashSet一样，TreeSet也不具备线程同步机制，不适用于多线程环境下的直接共享。

适用场景：

• 当需要一个无重复元素的集合，并且需要元素按照某种顺序（自然排序或自定义排序）排列时。
• 需要在有序集合上进行范围查找、最大最小值查询等操作时。

LinkedHashSet：

LinkedHashSet结合了HashSet与LinkedList的特点，是Set接口的一个实现类。其特性与适用场景如下：

特点：

• 保持插入顺序：如同LinkedList，LinkedHashSet内部使用双向链表结构保存元素的插入顺序，因此遍历结果会按照元素的插入顺序呈现。
• 不允许重复元素：如同HashSet，利用哈希表保证元素唯一性，通过equals()和hashCode()方法判断元素是否相等。
• 查找速度介于HashSet与TreeSet之间：由于额外维护链表结构，查找性能略低于HashSet，但优于TreeSet。
• 线程不安全：与HashSet和TreeSet一致，不提供线程同步。

适用场景：

• 当需要一个无重复元素的集合，同时希望保留元素的插入顺序时。
• 需要快速查找，但对元素顺序有一定要求，且不涉及大规模数据或频繁插入删除操作时。

总结来说，Set接口的实现类（HashSet、TreeSet、LinkedHashSet）提供了不同特性的无重复元素集合，开发者应根据对元素唯一性、排序需求、性能要求以及线程安全性的考量来选择最合适的实现。