一. 什么是集合框架
集合框架的概述
Java中的集合框架是一组用于管理和操作对象集合的类和接口，它们提供了比数组更高级别的数据结构和算法，以及更方便的数据访问和操作方式。
Java集合框架包括两种类型的集合：一种是基于接口的集合，另一种是基于类的集合。其中基于接口的集合是定义集合操作的一组接口，包括List、Set、Queue、Deque、Map等。基于类的集合是实现这些接口并提供特定实现的类，例如ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等。
集合框架的类库结构
- Collection接口：是所有集合接口的父接口，定义了集合的基本操作方法，包括添加、删除、遍历等。
- List接口：是Collection接口的子接口，表示一个有序的元素集合，允许元素重复。
a. ArrayList类：是List接口的一个实现类，使用数组实现，支持快速随机访问。
b. LinkedList类：也是List接口的一个实现类，使用双向链表实现，支持高效的插入和删除操作。 - Set接口：同样是Collection接口的子接口，表示一个不包含重复元素的无序集合。
a. HashSet类：是Set接口的一个实现类，使用哈希表实现，插入和查询效率高，不保证元素顺序。
b. TreeSet类：也是Set接口的一个实现类，使用红黑树实现，能够按照元素的自然顺序或指定的比较器进行排序。 - Queue接口：表示一个先进先出（FIFO）的元素集合。
a. LinkedList类：是Queue接口的一个实现类，也可以用作Stack（栈）数据结构。
b. PriorityQueue类：也是Queue接口的一个实现类，实现了优先级队列，元素按照自然顺序或指定的比较器进行排序。 - Deque接口：是Queue接口的子接口，表示一个双端队列，可以在队列的两端添加或删除元素。
a. LinkedList类：也是Deque接口的一个实现类，可以同时作为队列和栈使用。
b. ArrayDeque类：也是Deque接口的一个实现类，使用循环数组实现，可以作为栈、队列或双端队列使用。 - Map接口：表示一组键值对的映射，每个键只能对应一个值。
a. HashMap类：是Map接口的一个实现类，使用哈希表实现，插入和查询效率高，不保证元素顺序。
b. TreeMap类：也是Map接口的一个实现类，使用红黑树实现，能够按照键的自然顺序或指定的比较器进行排序。
除了这些核心接口和类之外，Java集合框架还提供了一些辅助类和接口，如Collections、Comparator、Iterator、Enumeration等，它们都提供了在集合操作中非常有用的方法和功能。
二. 集合框架中的基本接口和类
Collection接口和常用实现类（List、Set）
Collection接口是Java集合框架的根接口，它定义了一组通用的集合操作方法，包括添加、删除、遍历、判断是否包含等。常用的实现类包括List和Set。
List接口表示一个有序的元素集合，允许元素重复。常用的实现类有：
- ArrayList类：使用数组实现，支持快速随机访问，适合于随机访问，但是不适合于在中间位置插入或删除元素。
- LinkedList类：使用双向链表实现，支持高效的插入和删除操作，适合于在中间位置插入或删除元素，但是访问元素的效率较低。
Set接口表示一个不包含重复元素的无序集合。常用的实现类有：
- HashSet类：使用哈希表实现，插入和查询效率高，不保证元素顺序。
- TreeSet类：使用红黑树实现，能够按照元素的自然顺序或指定的比较器进行排序。
下面是一个示例代码，演示了如何使用ArrayList和HashSet类：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CollectionExample {
public static void main(String[] args) {
// 使用ArrayList存储整数
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(2); // 允许元素重复
System.out.println("ArrayList: " + list);
// 使用HashSet存储字符串
Set<String> set = new HashSet<>();
set.add("apple");
set.add("orange");
set.add("banana");
set.add("orange"); // 不允许元素重复
System.out.println("HashSet: " + set);
}
}
Map接口和常用实现类
Map接口表示一组键值对的映射关系，每个键最多只能映射到一个值。常用的实现类有：
- HashMap类：使用哈希表实现，插入和查询效率高，不保证元素顺序。
- TreeMap类：使用红黑树实现，能够按照键的自然顺序或指定的比较器进行排序。
- LinkedHashMap类：使用哈希表和双向链表实现，保证元素按照插入顺序排序。
下面是一个示例代码，演示了如何使用HashMap和TreeMap类：
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class MapExample {
public static void main(String[] args) {
// 使用HashMap存储成绩
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 90);
map.put("Bob", 85);
map.put("Charlie", 92);
map.put("Bob", 88); // 相同的键会覆盖原有的值
System.out.println("HashMap: " + map);
// 使用TreeMap存储成绩
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Alice", 90);
treeMap.put("Bob", 85);
treeMap.put("Charlie", 92);
treeMap.put("Bob", 88); // 相同的键会覆盖原有的值
System.out.println("TreeMap: " + treeMap);
}
}
三. 集合框架中的算法
排序算法
集合框架中提供了多种排序算法，其中Arrays类和Collections类提供了一些静态方法来对数组或集合进行排序。
- Arrays.sort()方法：对数组进行排序，使用快速排序或归并排序算法，时间复杂度为O(nlogn)。
- Arrays.parallelSort()方法：对数组进行并行排序，多线程执行排序算法，可以提高排序的速度。
- Collections.sort()方法：对集合进行排序，使用归并排序算法，时间复杂度为O(nlogn)。
- Collections.reverse()方法：对集合进行反转操作。
下面是一个示例代码，演示了如何使用Arrays类和Collections类进行排序操作：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class SortExample {
public static void main(String[] args) {
// 对数组进行排序
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
Arrays.sort(arr);
System.out.println("Sorted Array: " + Arrays.toString(arr));
// 对集合进行排序
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5));
Collections.sort(list);
System.out.println("Sorted List: " + list);
// 对集合进行反转操作
Collections.reverse(list);
System.out.println("Reversed List: " + list);
}
}
需要注意的是，在使用sort()方法进行排序时，集合中的元素必须实现Comparable接口或传入比较器Comparator对象，否则会抛出ClassCastException异常。
查找算法
集合框架中提供了两种查找算法，分别是线性查找和二分查找。
- 线性查找：逐一比较集合中的元素，直到找到指定的元素或搜索到集合的末尾。
- 二分查找：对于有序集合，可以使用二分查找算法进行查找。首先将集合按照元素大小排序，然后在集合的中间位置开始查找，如果中间元素等于指定元素，则查找成功；否则，如果指定元素小于中间元素，则在左半部分集合中查找；否则，在右半部分集合中查找。重复以上步骤，直到找到指定元素或者集合被搜索完毕。
下面是一个示例代码，演示了如何使用线性查找和二分查找算法：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class SearchExample {
public static void main(String[] args) {
// 线性查找
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5));
int index = list.indexOf(9);
System.out.println("Index of 9: " + index);
// 二分查找
Collections.sort(list);
int index2 = Collections.binarySearch(list, 9);
System.out.println("Index of 9: " + index2);
}
}
需要注意的是，在使用二分查找算法进行查找时，集合必须是有序的，否则可能得到错误的结果。另外，在使用binarySearch()方法进行查找时，如果查找的元素不存在于集合中，会返回一个负数，表示应该插入该元素的位置。
四. 集合框架中的线程安全问题
非线程安全的集合类
在Java集合框架中，有些类是非线程安全的，这意味着它们不适用于多线程环境，如果多个线程同时访问这些集合类的实例，可能会导致不可预测的结果。以下是一些非线程安全的集合类：
- ArrayList：它是一个基于数组实现的动态数组，可以在任意位置插入或删除元素。在多线程环境下，如果同时对ArrayList进行修改操作，可能会导致数据不一致或者抛出ConcurrentModificationException异常。
- LinkedList：它是一个基于链表实现的双向链表，可以在任意位置插入或删除元素。在多线程环境下，如果同时对LinkedList进行修改操作，可能会导致数据不一致或者抛出ConcurrentModificationException异常。
- HashMap：它是一个基于哈希表实现的键值对映射，可以快速查找指定的元素。在多线程环境下，如果同时对HashMap进行修改操作，可能会导致数据不一致或者抛出ConcurrentModificationException异常。
- HashSet：它是一个基于哈希表实现的集合，可以快速查找指定的元素。在多线程环境下，如果同时对HashSet进行修改操作，可能会导致数据不一致或者抛出ConcurrentModificationException异常。
如果需要在多线程环境中使用集合类，可以考虑使用线程安全的集合类，例如Vector、Hashtable、ConcurrentHashMap、CopyOnWriteArrayList和CopyOnWriteArraySet等。另外，也可以使用synchronized关键字或Lock对象来保证多线程安全。
线程安全的集合类
在Java集合框架中，线程安全的集合类是为多线程环境设计的，可以保证在多个线程同时访问时，不会出现数据不一致或者抛出ConcurrentModificationException异常等线程安全问题。以下是一些常用的线程安全的集合类：
- Vector：它是一个基于数组实现的动态数组，与ArrayList类似，但是所有的方法都是同步的，因此在多线程环境中可以保证线程安全。
- Hashtable：它是一个基于哈希表实现的键值对映射，与HashMap类似，但是所有的方法都是同步的，因此在多线程环境中可以保证线程安全。
- ConcurrentHashMap：它是一个基于哈希表实现的键值对映射，与HashMap类似，但是在多线程环境中使用更加高效。ConcurrentHashMap使用了分段锁的机制，将整个哈希表分成若干个段，每个段独立加锁，因此不同的线程可以同时访问不同的段，从而提高了并发性能。
- CopyOnWriteArrayList：它是一个基于数组实现的动态数组，与ArrayList类似，但是在修改操作时会创建一个新的数组，因此可以保证并发修改时的线程安全。适用于读多写少的场景。
- CopyOnWriteArraySet：它是一个基于CopyOnWriteArrayList实现的集合，与HashSet类似，但是可以保证并发修改时的线程安全。
需要注意的是，线程安全的集合类在多线程环境下虽然可以保证线程安全，但是会带来额外的开销，因此在单线程环境下使用可能会影响性能。因此，在选择集合类时需要根据实际需求来选择合适的集合类。