Java 集合
1. 集合框架概述
集合框架(Collection Framework) 是 Java 中为处理一组对象而设计的一套标准化 API,它包括一组通用的接口、实现类和算法。这些接口和类为各种数据结构和操作方法提供了统一的实现方式,使得开发者可以轻松地对数据进行存储、检索和操作。
1.1 集合框架的定义与作用:
定义:集合框架是一套标准化的接口和类,用来操作一组对象。它将各种数据结构(如动态数组、链表、队列、集合等)转换为 Java 中的类,并为其定义统一的操作方式。
作用:
- 简化编程:集合框架提供了一组常用的数据结构和算法,开发者无需重复编写基本的存储、查找、排序等操作。
- 可扩展性:通过标准接口和抽象类,开发者可以轻松实现自定义的数据结构并与框架兼容。
- 提高效率:集合框架中的许多实现都是高度优化的,适用于各种场景的性能需求(如快速查找、增删、排序等)。
- 提高代码的可维护性:集合框架通过接口将实现细节与具体数据结构分离,降低了代码的耦合度,方便后期维护和扩展。
1.2 集合与数组的区别:
- 容量:数组大小固定,声明后无法调整;集合是动态的,大小可以根据需要自动调整。
- 类型限制:数组只能存储同一类型的元素(基本类型或引用类型);集合存储对象(引用类型),且可以存储不同类型的对象(通过泛型可以实现类型安全)。
- 功能:集合提供丰富的 API 来进行增、删、查找、遍历等操作,数组的功能较为有限。
1.3 集合框架的主要接口
Collection 接口:
Collection
是集合框架的根接口,它定义了一组操作集合对象的方法,所有集合类(除 Map
之外)都直接或间接实现了这个接口。常见的子接口包括:
- List:有序集合,允许元素重复,如
ArrayList
、LinkedList
。 - Set:无序集合,不允许元素重复,如
HashSet
、TreeSet
。 - Queue:先进先出的队列接口,如
LinkedList
、PriorityQueue
。 - Deque:双端队列接口,支持从两端插入、删除,如
ArrayDeque
。
Map 接口:
Map
用于存储键值对(key-value pairs),不属于 Collection
接口体系,但它是集合框架的核心部分之一。常见实现有:
- HashMap:基于哈希表,快速查找和插入,不保证顺序。
- TreeMap:基于红黑树,按自然顺序或比较器顺序排序键。
- LinkedHashMap:有序版本的
HashMap
,按插入顺序或访问顺序保持键值对。 - Hashtable:线程安全的
HashMap
,效率较低。
1.4 接口与实现类
1.4.1 接口只能声明对象,实例化对象由实现类通过构造函数创建
1. 只能通过接口声明一个接口类的对象
List<String> list; // 仅仅声明一个接口类型的对象
2. 这个接口类的对象可以接受所有接口实现类实例化的对象
list = new ArrayList<>(); // 使用 ArrayList 实现类来创建 List 的实例
3. 接口类不能实例化
List<String> list = new List<>(); // 错误:接口不能直接实例化
1.4.2 接口类的常用操作由实现类的对象调用
接口类中定义的方法都会被实现类进行重写,当你创建了对应实现类的对象想去调用那些接口类中定义的方法,实际上调用的是已经被实现类重写的方法。
List<String> list = new ArrayList<>(); // 实例化接口对象
list.add("Item 1"); // 调用的是 ArrayList 实现的 add() 方法
System.out.println(list.get(0)); // 调用 ArrayList 实现的 get() 方法
2. List 接口及其实现
2.1 List 概述
List
是 Java 集合框架中一个重要的接口,继承自 Collection
。它表示一个有序的集合,允许包含重复的元素,并且支持基于索引的操作,能够通过索引对元素进行添加、删除和访问。
- 有序集合:
List
中的元素按插入顺序排列,每个元素都有对应的索引值。 - 允许重复元素:与
Set
不同,List
允许存储相同的元素。
2.2 List 的常见实现类
List是个接口,不能直接实例化, 故不能创建对象。要创建实例化对象必须要通过List的实现类来创建对象。
2.2.1 ArrayList
概述:
ArrayList
是基于动态数组实现的 List
。它是最常用的 List
实现类,底层通过数组存储数据,能够提供快速的随机访问。
特点:
- 查找快:由于底层是数组结构,可以通过索引直接访问元素,随机访问的时间复杂度为 O(1)。
- 增删慢:在中间插入或删除元素时,可能需要移动大量元素,因此时间复杂度为 O(n)。例如,删除列表第一个元素后,其他元素都需要向前移动。
- 动态扩容:当
ArrayList
容量不足时,它会自动扩展容量(通常为当前容量的 1.5 倍),扩容操作是相对耗时的。 - 适用场景:适用于读取频繁、插入和删除较少的场景,例如需要频繁遍历或随机访问元素的场景。
示例:
import java.util.ArrayList;public class ArrayListExample {public static void main(String[] args) {// 创建一个 ArrayListArrayList<String> list = new ArrayList<>();// 添加元素list.add("A");list.add("B");list.add("C");list.add("D");// 随机访问元素System.out.println("Element at index 1: " + list.get(1)); // 输出: B// 删除元素list.remove(2); // 删除索引为2的元素// 遍历列表System.out.println("ArrayList elements:");for (String element : list) {System.out.println(element);}}
}
2.2.2 LinkedList
概述:
LinkedList
是基于双向链表实现的 List
,同时实现了 Deque
(双端队列)接口,因此它不仅可以作为列表使用,还可以作为队列或栈使用。
特点:
- 增删快:在链表的首尾添加或删除元素时效率很高,时间复杂度为 O(1)。在中间插入或删除元素时也相对高效,只需调整相关节点的指针,而不需要像数组那样移动其他元素。
- 查找慢:由于链表不支持随机访问,查找某个元素时需要从头或尾部遍历,时间复杂度为 O(n)。
- 适用场景:适用于频繁插入和删除元素的场景,例如队列、栈操作或需要频繁在集合中间添加、删除元素的场景。
示例:
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {// 创建一个 LinkedListLinkedList<String> list = new LinkedList<>();// 添加元素list.add("A");list.add("B");list.add("C");list.addFirst("First"); // 在头部添加元素list.addLast("Last"); // 在尾部添加元素// 删除元素list.remove(2); // 删除索引为2的元素list.removeFirst(); // 删除第一个元素list.removeLast(); // 删除最后一个元素// 遍历列表System.out.println("LinkedList elements:");for (String element : list) {System.out.println(element);}}
}
2.2.3 Vector
概述:
Vector
是一个线程安全的动态数组实现,和 ArrayList
类似,底层也是通过数组来实现的,但每个操作都通过 synchronized
关键字保证了线程安全。
特点:
- 线程安全:每个方法都使用了
synchronized
关键字,确保在多线程环境下的安全操作,但这也带来了较大的性能开销。 - 性能较差:由于每次操作都涉及线程同步,因此
Vector
的性能低于ArrayList
。在现代开发中较少使用Vector
,通常用ArrayList
并手动同步来替代。 - 适用场景:适用于需要线程安全的场景,但一般不推荐使用。可以选择
ArrayList
,并通过显式的同步机制来实现线程安全。
示例:
import java.util.Vector;public class VectorExample {public static void main(String[] args) {// 创建一个线程安全的 VectorVector<String> vector = new Vector<>();// 添加元素vector.add("A");vector.add("B");vector.add("C");// 随机访问元素System.out.println("Element at index 1: " + vector.get(1)); // 输出: B// 删除元素vector.remove(2); // 删除索引为2的元素// 遍历 VectorSystem.out.println("Vector elements:");for (String element : vector) {System.out.println(element);}}
}
2.2.4 总结
ArrayList
:基于动态数组,适合频繁访问元素的场景,但插入、删除操作较慢。LinkedList
:基于双向链表,适合频繁插入和删除元素的场景,但随机访问较慢。Vector
:线程安全的动态数组实现,性能较差,适合多线程场景,但一般用ArrayList
加锁替代。
2.3 List 常用操作
List
提供了多种操作方法,用于元素的添加、删除、访问和遍历等。
这些接口的方法都是供接口的实现类的实例化对象来调用的。
List是个接口,不能实例化,只能被List的实现类的对象调用。
2.3.1 添加元素
add(E e)
:在列表末尾添加元素。
list.add("Element");
add(int index, E element)
:在指定索引处插入元素。
list.add(1, "New Element");
2.3.2 删除元素
remove(int index)
:删除指定索引处的元素。
list.remove(2);
remove(Object o)
:删除列表中第一次出现的指定元素。
list.remove("Element");
2.3.3 访问元素
get(int index)
:通过索引访问元素。
String element = list.get(0);
set(int index, E element)
:修改指定位置的元素。
list.set(2, "Updated Element");
2.3.4 子列表操作
subList(int fromIndex, int toIndex)
:返回列表中从某个索引位置(fromIndex
)到某个索引位置(toIndex
)的元素(不包含toIndex),并将这些元素组成一个新列表(子列表)进行返回。
List<String> subList = list.subList(1, 3);
2.3.5 批量操作
addAll(Collection<? extends E> c)
:将另一个集合的所有元素添加到当前列表中。
List<String> anotherList = Arrays.asList("A", "B", "C");
list.addAll(anotherList);
2.4 List
遍历方式
List
提供了多种遍历方式,可以根据不同的需求选择合适的遍历方法。每种遍历方式都有其特点和适用场景。接下来我们详细讲解三种常见的遍历方式:增强 for
循环、Iterator
和 ListIterator
,并通过代码示例逐一解析。
2.4.1 增强 for
循环
概述:
增强 for
循环(也称为 for-each
循环)是一种简洁的遍历集合的方式,适合不需要修改集合元素的场景。这种遍历方式的优点是代码更加简洁、易读,不需要处理索引或遍历条件。
示例:
import java.util.ArrayList;public class EnhancedForLoopExample {public static void main(String[] args) {// 创建一个 ArrayListArrayList<String> list = new ArrayList<>();list.add("Apple");list.add("Banana");list.add("Orange");// 使用增强 for 循环遍历集合for (String element : list) {System.out.println(element);}}
}
代码解释:
for (String element : list)
语法简化了传统的for
循环,通过直接获取每个元素而不需要处理索引。- 这种方式适用于不修改集合的情况。它无法在遍历过程中对集合元素进行增删操作。
- 增强
for
循环背后实际上使用了Iterator
,但语法更加简洁。
2.4.2 Iterator
遍历
概述:
Iterator
是 List
提供的一种标准遍历方式,适合需要在遍历时修改(删除)集合元素的情况。Iterator
可以通过 hasNext()
判断是否有下一个元素,通过 next()
获取当前元素,并可以通过 remove()
删除当前元素。
示例:
import java.util.ArrayList;
import java.util.Iterator;public class IteratorExample {public static void main(String[] args) {// 创建一个 ArrayListArrayList<String> list = new ArrayList<>();list.add("Apple");list.add("Banana");list.add("Orange");// 获取 Iterator 对象Iterator<String> iterator = list.iterator();// 使用 Iterator 遍历集合while (iterator.hasNext()) {String element = iterator.next();System.out.println(element);// 删除元素 "Banana"if (element.equals("Banana")) {iterator.remove(); // 通过 iterator 删除当前元素}}// 遍历后的集合内容System.out.println("After removal: " + list);}
}
代码解释:
iterator()
:通过list.iterator()
方法获取Iterator
对象,用于遍历集合。hasNext()
:判断集合中是否还有未遍历的元素。next()
:获取当前元素,并将游标移动到下一个元素。remove()
:通过Iterator
删除当前元素。注意:只能在调用next()
后调用remove()
,否则会抛出异常。Iterator
的主要优势是可以在遍历时安全地删除集合中的元素,而不会抛出ConcurrentModificationException
异常。这在需要在遍历时修改集合的场景下非常有用。
2.4.3 ListIterator
遍历
概述:
ListIterator
是 Iterator
的增强版,专门用于 List
集合。它不仅支持像 Iterator
一样的正向遍历,还支持双向遍历。此外,它还允许在遍历过程中修改集合(如添加、删除或替换元素),这是 Iterator
无法提供的功能。
示例:
import java.util.LinkedList;
import java.util.ListIterator;public class ListIteratorExample {public static void main(String[] args) {// 创建一个 LinkedListLinkedList<String> list = new LinkedList<>();list.add("Apple");list.add("Banana");list.add("Orange");// 获取 ListIterator 对象ListIterator<String> listIterator = list.listIterator();// 正向遍历集合System.out.println("Forward traversal:");while (listIterator.hasNext()) {String element = listIterator.next();System.out.println(element);// 在元素 "Banana" 之后插入一个新元素 "Grapes"if (element.equals("Banana")) {listIterator.add("Grapes");}}// 反向遍历集合System.out.println("Backward traversal:");while (listIterator.hasPrevious()) {String element = listIterator.previous();System.out.println(element);}}
}
代码解释:
listIterator()
:通过list.listIterator()
方法获取ListIterator
对象,它允许正向和反向遍历。hasNext()
和next()
:正向遍历时使用这些方法来获取下一个元素。hasPrevious()
和previous()
:反向遍历时使用这些方法来获取上一个元素。add()
:允许在遍历过程中插入新元素,而不会破坏遍历流程。ListIterator
的主要优势是可以在遍历过程中添加、删除或替换元素,同时支持双向遍历。这使得它在复杂的修改场景中非常有用,比如需要在遍历过程中灵活插入或删除元素。
2.4.4 总结
- 增强
for
循环:语法简洁,适合只读遍历,不适合在遍历过程中修改集合。Iterator
:适合在遍历过程中删除元素,不能反向遍历或在遍历时插入新元素。ListIterator
:支持双向遍历,允许在遍历过程中添加、删除或替换元素,功能比Iterator
更强大。
3. Set 接口及其实现
3.1 Set 概述
Set
是 Java 集合框架中的一个接口,继承自 Collection
。它代表一个无序的集合,其中的元素不能重复。这意味着 Set
中的每个元素都是唯一的,并且 Set
不维护元素的插入顺序(除了一些特殊实现类,如 LinkedHashSet
)。Set
适合用于去重操作和需要集合运算(如并集、交集等)的场景。
- 无序集合:
Set
中的元素没有固定顺序,具体的排序取决于Set
的具体实现。 - 不允许重复元素:在
Set
中,每个元素都是唯一的,如果试图向Set
中添加一个已经存在的元素,则插入操作会被忽略。
3.2 Set 的常见实现类
Set
接口有多个常见的实现类,它们的底层数据结构不同,因此在性能和适用场景上各有差异。常见的实现类包括 HashSet
、LinkedHashSet
和 TreeSet
。
3.2.1 HashSet
-
概述:
HashSet
是基于哈希表实现的Set
,元素存储在哈希表中,因此没有固定的顺序。HashSet
提供了高效的查找和插入操作。 -
特点:
- 无序:
HashSet
不保证元素的插入顺序。插入的元素位置是由其哈希值决定的,因此每次遍历时元素顺序可能不同。 - 允许
null
值:HashSet
可以存储null
,但只能存储一个null
值,因为Set
不允许重复元素。 - 查找和插入性能较好:由于底层是哈希表,查找和插入的时间复杂度为 O(1),非常高效。
- 无序:
-
适用场景:适用于不关心元素顺序、只需确保元素唯一且需要高效查找和插入的场景。
代码示例:
import java.util.HashSet;public class HashSetExample {public static void main(String[] args) {// 创建一个 HashSetHashSet<String> set = new HashSet<>();// 添加元素set.add("Apple");set.add("Banana");set.add("Orange");set.add("Banana"); // 重复元素,不会被添加// 允许存储一个 null 值set.add(null);// 遍历集合for (String element : set) {System.out.println(element);}}
}
代码解释:
HashSet
是无序的,所以每次遍历时元素的顺序可能不同。- 尝试添加重复的元素时不会抛出异常,但重复的元素不会再次添加到集合中。
3.2.2 LinkedHashSet
-
概述:
LinkedHashSet
是基于哈希表和链表实现的Set
,它与HashSet
的不同之处在于,它维护了元素的插入顺序,即元素会按照插入的顺序进行存储和遍历。 -
特点:
- 有序:
LinkedHashSet
保留了元素的插入顺序,在遍历时按元素插入的顺序进行。 - 允许
null
值:与HashSet
一样,LinkedHashSet
允许存储null
值,但只能存储一个null
。 - 查找和插入性能较好:性能略低于
HashSet
,因为维护了链表以存储插入顺序,但查找和插入的时间复杂度依然是 O(1)。
- 有序:
-
适用场景:适用于需要保证元素的插入顺序,并且需要进行快速查找和插入的场景。
代码示例:
import java.util.LinkedHashSet;public class LinkedHashSetExample {public static void main(String[] args) {// 创建一个 LinkedHashSetLinkedHashSet<String> set = new LinkedHashSet<>();// 添加元素set.add("Apple");set.add("Banana");set.add("Orange");set.add("Banana"); // 重复元素,不会被添加// 遍历集合(按插入顺序)for (String element : set) {System.out.println(element);}}
}
代码解释:
LinkedHashSet
保留了元素的插入顺序,因此遍历时输出的顺序与插入顺序一致。
3.2.3 TreeSet
-
概述:
TreeSet
是基于红黑树实现的Set
,它保证了集合中元素的自然顺序(或者通过提供的Comparator
进行定制排序)。由于底层是平衡二叉树,TreeSet
的查找、插入和删除操作的时间复杂度为 O(log n)。 -
特点:
- 有序:
TreeSet
保证元素按照自然顺序(如数字从小到大、字符串按字典顺序)进行存储和遍历。如果需要自定义排序,则可以通过构造TreeSet
时提供Comparator
实现。 - 不允许
null
值:TreeSet
不允许存储null
,因为TreeSet
需要对元素进行排序,而null
值无法进行排序操作。 - 查找和插入性能较好:基于红黑树,插入、删除、查找的时间复杂度为 O(log n),适合需要有序存储和快速查找的场景。
- 定制排序:可以通过在创建
TreeSet
时传入Comparator
对象,来自定义排序规则。
- 有序:
-
适用场景:适用于需要对元素进行自然排序或自定义排序的场景,特别适合有序集合操作。
代码示例:
import java.util.TreeSet;public class TreeSetExample {public static void main(String[] args) {// 创建一个 TreeSetTreeSet<String> set = new TreeSet<>();// 添加元素(自动按自然顺序排序)set.add("Banana");set.add("Apple");set.add("Orange");// 遍历集合(按自然顺序)for (String element : set) {System.out.println(element);}}
}
代码解释:
TreeSet
会按照字典顺序对字符串进行排序,因此遍历时输出的顺序为Apple
、Banana
、Orange
。
使用 Comparator
进行定制排序
1. 你需要先定义一个Comparator
Comparator<String> lengthComparator;就定义了一个比较String类型的名叫lengthComparator的Comparator。
2. 重写 compare()
方法
你需要重写新创建的 Comparator
中的 compare()
方法,该方法通过比较传入的两个参数,并根据返回值确定这两个参数的顺序(类似于逐对比较集合中的所有元素,通过 compare()
方法的返回值来确定最终的排序)
在 compare(T o1, T o2)
方法中,定义你希望的比较逻辑:
- 返回负值:表示
o1
应该排在o2
之前。 - 返回正值:表示
o1
应该排在o2
之后。 - 返回 0:表示
o1
和o2
在排序中视为相等,顺序不变。
3. 将 Comparator
应用于集合
通过代码,TreeSet<String> set = new TreeSet<>(lengthComparator);可以将你自定义的名为lengthComparator的Comparator应用于集合。
示例 :按字符串长度排序
假设我们要按字符串长度排序,而不是默认的字母顺序。我们可以创建一个自定义的 Comparator
:
import java.util.Comparator;
import java.util.TreeSet;public class CustomComparatorExample {public static void main(String[] args) {// 定义自定义 Comparator,按字符串长度排序Comparator<String> lengthComparator = new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {// 比较两个字符串的长度return Integer.compare(s1.length(), s2.length());}};// 使用自定义 Comparator 创建 TreeSetTreeSet<String> set = new TreeSet<>(lengthComparator);set.add("Banana");set.add("Apple");set.add("Orange");set.add("Kiwi");// 输出结果,按字符串长度排序for (String s : set) {System.out.println(s);}}
}
Integer.compare(s1.length(), s2.length())
用于比较两个字符串的长度。- 返回负值时(
s1.length() < s2.length()
),表示s1
排在s2
之前。 - 返回正值时(
s1.length() > s2.length()
),表示s1
排在s2
之后。 - 返回 0 时表示长度相同,按自然顺序或保留插入顺序。
3.2.4 总结
HashSet
:基于哈希表,提供无序的集合,允许存储null
,性能高效。LinkedHashSet
:基于哈希表和链表,保留插入顺序,适合需要有序遍历的场景。TreeSet
:基于红黑树,提供按自然顺序或自定义顺序排序的有序集合,不允许null
值。
3.3 Set 常用操作
Set
提供了一些常见的集合操作,除了 Collection
接口定义的基本操作外,Set
还可以进行一些集合运算,如交集、并集和差集。
3.3.1 添加元素
add(E e)
:将元素添加到 Set
中,如果元素已经存在,则不会添加。
set.add("Apple");
3.3.2 删除元素
remove(Object o)
:删除 Set
中指定的元素。
set.remove("Apple");
3.3.3 判断元素是否存在
contains(Object o)
:判断 Set
中是否包含指定元素。
boolean exists = set.contains("Apple");
3.3.4 集合运算
交集
retainAll(Collection<?> c)
,保留当前 Set
中与另一个集合相同的元素。
set1.retainAll(set2); // 计算 set1 和 set2 的交集
并集
addAll(Collection<? extends E> c)
,将另一个集合的所有元素添加到当前 Set
中。
set1.addAll(set2); // 计算 set1 和 set2 的并集
差集
removeAll(Collection<?> c)
,从当前 Set
中删除所有在另一个集合中出现的元素。
set1.removeAll(set2); // 计算 set1 和 set2 的差集
retainAll()
:计算两个集合的交集,保留set1
和set2
的共同元素。addAll()
:计算两个集合的并集,将set2
中的元素添加到set1
中。removeAll()
:计算两个集合的差集,从set1
中移除set2
中存在的元素。
4. Map 接口及其实现
4.1 Map 概述
Map
是一个用于存储键值对(key-value pairs)的集合接口。与其他集合类型不同,Map
是通过键(key)来映射到对应的值(value),并且每个键在 Map
中是唯一的。
- 键:在
Map
中,每个键是唯一的,不能重复。如果尝试添加相同的键,新值将会覆盖旧值。 - 值:与键关联的对象,可以重复。多个不同的键可以映射到相同的值。
- 键值对:一个键和一个值共同组成一个键值对,这个键值对在
Map
中作为一个整体元素进行存储。
4.2 常见的 Map
实现类
4.2.1 HashMap
-
概述:
HashMap
是最常用的Map
实现类,基于哈希表(Hash Table)实现,能够提供快速的键值对存储和查找。 -
特点:
- 无序:
HashMap
不保证键值对的存储顺序,插入和遍历时顺序可能不同。 - 允许
null
键和null
值:HashMap
允许一个null
键和多个null
值。 - 性能高效:由于哈希表的底层实现,查找、插入和删除的时间复杂度为 O(1),适合大规模数据的处理。
- 无序:
-
适用场景:适用于需要通过键快速存取数据,但不关心数据顺序的场景。
示例:
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("username", "john_doe");
hashMap.put("email", "john@example.com");
String value = hashMap.get("username");
4.2.2 LinkedHashMap
-
概述:
LinkedHashMap
是HashMap
的有序版本,内部使用哈希表和双向链表结合的方式实现,能够维护键值对的插入顺序或访问顺序。 -
特点:
- 按插入顺序排序:
LinkedHashMap
默认按照键值对插入的顺序存储和遍历。 - 允许
null
键和null
值:与HashMap
类似,允许一个null
键和多个null
值。 - 支持按访问顺序排序:可以通过构造方法指定
LinkedHashMap
为按访问顺序排序,每次访问(如get()
操作)都会将键值对移到末尾。
- 按插入顺序排序:
-
适用场景:适用于需要维护键值对顺序的场景,尤其是在插入顺序或访问顺序相关的场景。
示例:
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("username", "john_doe");
linkedHashMap.put("email", "john@example.com");
String value = linkedHashMap.get("username");
如果你希望每次访问(如
get()
操作)都会将键值对移到末尾,则需要使用如下的构造函数来创建LinkedHashMap。
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
三个参数分别是:初始容量、负载因子、是否按访问顺寻排序
4.2.3 TreeMap
-
概述:
TreeMap
基于红黑树(Red-Black Tree)实现,能够保证键值对按照键的自然顺序或通过Comparator
进行定制排序。 -
特点:
- 按键排序:
TreeMap
会根据键的自然顺序进行排序(如数字从小到大、字符串按字母顺序)。 - 支持自定义排序:可以通过
Comparator
定制键的排序规则。 - 不允许
null
键:由于键需要排序,TreeMap
不允许存储null
键,但允许null
值。
- 按键排序:
-
适用场景:适用于需要对键值对进行排序存储的场景,尤其是根据键的自然顺序或定制顺序进行排序的需求。
示例:
TreeMap<String, String> treeMap = new TreeMap<>();
treeMap.put("username", "john_doe");
treeMap.put("email", "john@example.com");
String value = treeMap.get("username");
4.2.4 ConcurrentHashMap
-
概述:
ConcurrentHashMap
是HashMap
的线程安全版本,专为高并发环境设计。它通过分段锁机制提高了并发性能,允许多个线程同时对ConcurrentHashMap
进行操作。 -
特点:
- 线程安全:
ConcurrentHashMap
使用分段锁(segment locking),确保线程安全,但只在需要的部分加锁,允许高效的并发读写。 - 不允许
null
键和null
值:与Hashtable
类似,ConcurrentHashMap
不允许null
键或null
值。 - 性能较好:相比于传统的
Hashtable
,ConcurrentHashMap
在多线程场景下具有更好的性能。
- 线程安全:
-
适用场景:适用于多线程环境中需要线程安全的键值对存储操作,同时具有较高并发性能的场景。
示例:
ConcurrentHashMap<String, String> concurrentHashMap = new ConcurrentHashMap<>();
concurrentHashMap.put("username", "john_doe");
concurrentHashMap.put("email", "john@example.com");
String value = concurrentHashMap.get("username");
这里所实现的线程安全(使用分段锁)是自动实现的,它通过判断读操作不需要加锁,写操作需要加锁来自动进行,不需要再代码层面显式操作。
4.2.5 总结
HashMap
:基于哈希表实现,键值无序,允许null
键和null
值,性能高效。LinkedHashMap
:基于哈希表和链表实现,按插入顺序或访问顺序排序,允许null
键和null
值。TreeMap
:基于红黑树实现,按键的自然顺序排序或通过Comparator
定制排序,不允许null
键。ConcurrentHashMap
:线程安全的HashMap
,使用分段锁机制,提高了多线程环境下的性能,不允许null
键和null
值。
4.3 Map 常用操作
Map
提供了一些基础的操作方法,用于存储、删除、访问和遍历键值对。
4.3.1 添加键值对
put(K key, V value)
:将一个键值对插入到 Map
中。如果键已经存在,则替换旧值。
map.put("username", "john_doe");
4.3.2 删除键值对
remove(Object key)
:根据键删除对应的键值对。
map.remove("username");
4.3.3 访问键值对
get(Object key)
:根据键获取对应的值。如果键不存在,返回 null
。
String value = map.get("username");
4.3.4 判断是否包含键或值
containsKey(Object key)
:检查 Map
是否包含指定的键。
containsValue(Object value)
:检查 Map
是否包含指定的值。
boolean hasKey = map.containsKey("username");
boolean hasValue = map.containsValue("john_doe");
4.3.5 获取键、值或键值对集合
keySet()
:返回 Map
中所有键的集合(Set<K>
)。
values()
:返回 Map
中所有值的集合(Collection<V>
)。
entrySet()
:返回 Map
中所有键值对的集合(Set<Map.Entry<K, V>>
)。
Set<String> keys = map.keySet(); // 获取所有键
Collection<String> values = map.values(); // 获取所有值
Set<Map.Entry<String, String>> entries = map.entrySet(); // 获取所有键值对
Map.Entry<K, V>
是Map
接口的一个内部静态接口,表示Map
中的一个键值对(key-value pair)。它用来封装Map
中的键(K
)和值(V
)作为一个完整的对象。- 这里要用Set<Map.Entry<String, String>>集合声明对象的原因是因为map.entrySet()就返回的是一个键值对的Set的集合,Set集合的内部是一个个单独的键值对,所以这里要用Map.Entry<String, String>作为Set集合中的元素类型。
4.4 遍历 Map
Map
可以通过多种方式遍历其键值对:
4.4.1 遍历键集合(keySet()
)
通过 keySet()
获取所有键,然后通过键访问对应的值:
for (String key : map.keySet()) {System.out.println("Key: " + key + ", Value: " + map.get(key));
}
4.4.2 遍历值集合(values()
)
通过 values()
获取所有值并进行遍历:
for (String value : map.values()) {System.out.println("Value: " + value);
}
4.4.3 遍历键值对集合(entrySet()
)
使用 entrySet()
获取所有键值对并直接遍历:
for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
Map.Entry<String, String> entry声明的是一个单独的键值对,不是一个键值对集合。
5. Queue 和 Deque 接口及其实现
5.1 Queue 概述
Queue(队列)是 Java 中用于处理先进先出(FIFO,First-In-First-Out)操作的集合接口。队列中的元素按插入顺序排列,最早插入的元素最先被处理。Queue
接口扩展了 Collection
接口,并定义了一些特定于队列的操作方法。Deque(双端队列)是 Queue
的扩展,允许在队列两端进行元素插入和删除操作。
- Queue:适用于按顺序处理元素的场景,例如任务调度、消息处理。
- Deque:支持从两端插入和删除元素,可以作为队列(FIFO)或栈(LIFO,后进先出)使用。
5.2 Queue 和 Deque 的常见实现类
5.2.1 LinkedList
-
概述:
LinkedList
是双向链表的实现类,既实现了Queue
接口,也实现了Deque
接口。因此,它支持队列操作(先进先出),同时也支持双端队列和栈操作(后进先出)。 -
特点:
- 既可以作为标准的队列使用,也可以作为双端队列,并提供了栈操作方法。
- 插入和删除操作的效率较高,适合频繁增删操作的场景。
-
适用场景:适合需要同时支持队列、双端队列和栈操作的场景。
示例:
Deque<String> deque = new LinkedList<>();// 双端队列操作:从队首和队尾插入元素
deque.offerFirst("Item 1"); // 从队首插入
deque.offerLast("Item 2"); // 从队尾插入// 移除元素
System.out.println(deque.pollFirst()); // 输出 "Item 1",从队首移除
System.out.println(deque.pollLast()); // 输出 "Item 2",从队尾移除// 栈操作:后进先出(LIFO)
deque.push("Item 3"); // 压栈
System.out.println(deque.pop()); // 出栈,输出 "Item 3"
- 双端队列操作:通过
offerFirst()
和offerLast()
可以分别从队首和队尾插入元素,通过pollFirst()
和pollLast()
可以分别从队首和队尾移除元素。 - 栈操作:通过
push()
实现压栈,通过pop()
实现后进先出(LIFO)的出栈操作。
5.2.2 PriorityQueue
-
概述:
PriorityQueue
是基于优先级堆实现的队列,元素按优先级排序,而不是插入顺序。默认情况下,它使用自然顺序(最小的元素优先),也可以通过自定义的Comparator
实现定制的排序规则。 -
特点:
- 元素按优先级排序,队列头部是优先级最高的元素(默认是最小的元素)。
PriorityQueue
不允许存储null
元素。
-
适用场景:适用于需要根据优先级处理元素的场景,如任务调度、事件处理。
示例:
// 自定义 Comparator 实现优先级由大到小排序(降序)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1; // 降序:o2 比 o1 大,o2 优先级更高}
});priorityQueue.offer(5);
priorityQueue.offer(1);
priorityQueue.offer(3);System.out.println(priorityQueue.poll()); // 输出 5(优先级最高的元素)
System.out.println(priorityQueue.poll()); // 输出 3
System.out.println(priorityQueue.poll()); // 输出 1
- 自定义
Comparator
:通过PriorityQueue
的构造函数传入Comparator
,可以定制元素的排序规则。此例中通过Comparator
实现降序排序,优先级从大到小排列。如果不自主定义Comparator
,则是按升序排序。
5.2.3 ArrayDeque
-
概述:
ArrayDeque
是基于数组实现的双端队列,既可以用作队列,也可以用作栈。它提供了高效的双端队列操作,相比LinkedList
,ArrayDeque
的内存开销更小,操作速度更快。 -
特点:
- 无界双端队列:
ArrayDeque
没有固定大小,可以根据需要动态扩展。 - 高效的队列和栈操作:它的双端操作和栈操作比
LinkedList
更加高效,因为它基于数组实现。
- 无界双端队列:
-
适用场景:适用于需要频繁从两端操作元素的场景,或者需要高效的栈操作。
示例:
Deque<String> arrayDeque = new ArrayDeque<>();// 双端队列操作
arrayDeque.offerFirst("Item 1"); // 从队首插入
arrayDeque.offerLast("Item 2"); // 从队尾插入System.out.println(arrayDeque.pollFirst()); // 输出 "Item 1",从队首移除
System.out.println(arrayDeque.pollLast()); // 输出 "Item 2",从队尾移除// 栈操作:后进先出
arrayDeque.push("Item 3"); // 压栈
System.out.println(arrayDeque.pop()); // 出栈,输出 "Item 3"
- 双端队列操作:通过
offerFirst()
和offerLast()
从两端插入元素,pollFirst()
和pollLast()
从两端移除元素。 - 栈操作:使用
push()
进行压栈操作,使用pop()
进行后进先出的栈操作。
5.3 Queue 和 Deque 常用操作
Queue
和 Deque
提供了许多常用的操作方法,这些方法可用于队列操作(FIFO)或栈操作(LIFO),根据场景选择不同的实现类。以下是一些常见操作方法:
5.3.1 入队操作
offer(E e)
:将元素插入到队列的尾部,如果队列已满,返回 false
。不同于 add()
,offer()
不会抛出异常。
queue.offer("Item");
5.3.2 出队操作
poll()
:从队列头部移除并返回元素,如果队列为空,返回 null
。不同于 remove()
,poll()
不会抛出异常。
queue.poll();
5.3.3 查看队首元素
peek()
:查看队列头部的元素,但不移除。如果队列为空,返回 null
。
queue.peek();
5.3.4 栈操作
push(E e)
:将元素压入栈,作为栈顶元素。
deque.push("Item");
pop()
:弹出栈顶元素并返回它,如果栈为空,则抛出异常。
deque.pop();
5.3.5 处理阻塞队列(BlockingQueue)
BlockingQueue
是 Queue
的一种特殊实现,常用于多线程环境下的生产者-消费者模型。BlockingQueue
支持线程安全的操作,在队列为空时阻塞获取操作,在队列已满时阻塞插入操作。
ArrayBlockingQueue
:基于数组的有界阻塞队列,队列大小固定。LinkedBlockingQueue
:基于链表的阻塞队列,可以指定大小,也可以不指定(默认无界)。
BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(10);
blockingQueue.put("Item 1"); // 阻塞插入
String item = blockingQueue.take(); // 阻塞获取
6. 集合工具类
在 Java 中,Collections
和 Arrays
工具类极大地简化了对集合和数组的常用操作。它们提供了排序、搜索、同步化等功能,方便开发者对集合或数组进行常规处理。接下来,针对一些常见的操作方法,我们做详细解释和代码示例,并纠正部分内容。
6.1 Collections
类
Collections
是一个静态工具类,用于操作集合。它包含了排序、搜索、同步化等常用方法。所有方法都是静态的,无需创建 Collections
实例即可使用。(一般来说更多使用于List集合)
6.1.1 常用方法
sort(List<T> list)
:对List
集合进行排序。如果元素实现了Comparable
接口,可以按照自然顺序排序。如果传入了Comparator
,则按照自定义的规则进行排序。
自然排序:
自然排序要求 List
中的元素实现了 Comparable
接口。Comparable
定义了默认的排序方式,例如字母或数字的升序排列。
List<Integer> list = Arrays.asList(5, 1, 3, 8, 2);
Collections.sort(list); // 对 list 进行自然排序
System.out.println(list); // 输出 [1, 2, 3, 5, 8]
自定义排序规则(使用 Comparator
):
你可以传入自定义的 Comparator
,用于自定义排序规则。Comparator
是一个函数接口,允许你根据需要定义比较逻辑。
List<Integer> list = Arrays.asList(5, 1, 3, 8, 2);// 使用 Comparator 实现降序排序
Collections.sort(list, (a, b) -> b - a); // 按降序排列
System.out.println(list); // 输出 [8, 5, 3, 2, 1]
在这个示例中,Comparator
通过 lambda 表达式定义了比较规则:b - a
,这意味着 b
的优先级高于 a
,从而实现降序排序。
binarySearch(List<T> list, T key)
:使用二分查找法查找List
中的元素。要求List
必须已经按升序排序,否则结果不可预期。
List<Integer> list = Arrays.asList(1, 2, 3, 5, 8);
int index = Collections.binarySearch(list, 3); // 查找元素 3
System.out.println(index); // 输出 2
如果 List
没有按照升序排列,binarySearch()
会返回错误的结果。因此,确保在调用 binarySearch()
之前,List
已经被排序。
reverse(List<?> list)
:将List
中的元素顺序反转。
List<String> list = Arrays.asList("A", "B", "C", "D");
Collections.reverse(list);
System.out.println(list); // 输出 [D, C, B, A]
shuffle(List<?> list)
:将List
中的元素随机打乱顺序。
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
Collections.shuffle(list); // 随机打乱元素顺序
System.out.println(list); // 输出可能是 [3, 5, 2, 1, 4]
synchronizedList(List<T> list)
:将一个List
变为线程安全的List
。其他集合类型如Set
和Map
也有类似的同步化方法,如synchronizedSet()
和synchronizedMap()
。
List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);synchronized (synchronizedList) {synchronizedList.add("Item 1");
}
fill(List<? super T> list, T obj)
:用指定的元素替换List
中的所有元素。例如将所有元素替换为"Z"
:
List<String> list = Arrays.asList("A", "B", "C");
Collections.fill(list, "Z"); // 将所有元素替换为 "Z"
System.out.println(list); // 输出 [Z, Z, Z]
6.2 Arrays
类
Arrays
是用于操作数组的工具类。它提供了数组转换、排序、搜索等功能,方便对数组进行各种操作。Arrays
类中的方法类似于 Collections
,但它专门用于处理数组。
6.2.1 常用方法
asList(T... a)
:将一个数组转换为List
集合。注意,此方法返回的List
是固定大小的,不能添加或删除元素,但可以修改已有的元素。
String[] array = {"A", "B", "C"};
List<String> list = Arrays.asList(array);
System.out.println(list); // 输出 [A, B, C]
sort(T[] a)
:对数组进行自然排序。如果是对象数组,数组中的对象必须实现Comparable
接口。
int[] array = {5, 3, 8, 1, 2};
Arrays.sort(array); // 对数组进行升序排序
System.out.println(Arrays.toString(array)); // 输出 [1, 2, 3, 5, 8]
binarySearch(T[] a, T key)
:在排序的数组中使用二分查找法查找元素的索引。
int[] array = {1, 2, 3, 5, 8};
int index = Arrays.binarySearch(array, 3); // 查找元素 3 的索引
System.out.println(index); // 输出 2
类似于 Collections.binarySearch()
,Arrays.binarySearch()
也要求数组必须是升序排列的,否则结果不可预期。
equals(T[] a, T[] b)
:比较两个数组是否相等。数组中的元素必须一一对应相等。
int[] array1 = {1, 2, 3};
int[] array2 = {1, 2, 3};
boolean isEqual = Arrays.equals(array1, array2);
System.out.println(isEqual); // 输出 true
toString(T[] a)
:将数组转换为字符串,便于输出数组内容。
int[] array = {1, 2, 3, 4, 5};
System.out.println(Arrays.toString(array)); // 输出 [1, 2, 3, 4, 5]
6.3 总结
Collections
类
- 排序:
sort()
对List
进行自然排序或自定义排序。 - 搜索:
binarySearch()
需要集合已排序,使用二分查找法查找元素。 - 修改顺序:
reverse()
反转元素顺序,shuffle()
随机打乱顺序。 - 同步化:
synchronizedList()
将List
包装为线程安全集合。 - 其他操作:如
fill()
用指定值替换List
中的所有元素,max()
返回最大元素。
Arrays
类
- 转换:
asList()
将数组转换为List
。 - 排序和搜索:
sort()
对数组进行排序,binarySearch()
在排序数组中查找元素。 - 实现
Comparable
接口:如果数组中的对象需要排序,必须实现Comparable
接口,并提供compareTo()
方法。 - 其他操作:
equals()
比较两个数组是否相等,toString()
打印数组内容。
7. 集合框架的性能与优化
7.1 集合类的选择
在实际开发中,选择合适的集合类是性能优化的关键。下面是不同场景下如何选择合适的集合类的指南:
1. 快速访问元素:ArrayList
和 HashMap
是理想选择,能够提供 O(1) 的读操作。
ArrayList
:适用于需要频繁随机访问元素的场景,例如缓存、索引。HashMap
:适用于快速查找键值对的场景,例如缓存键值对数据。
2. 频繁插入和删除:LinkedList
和 HashSet
是合适的选择。
LinkedList
:适用于频繁在头部或中间插入/删除元素的场景,例如队列或双端队列。HashSet
:适用于频繁插入、删除且无需排序的场景,且需要确保元素唯一。
3. 需要排序的集合:选择基于排序的集合类,如 TreeSet
、TreeMap
。
TreeSet
和TreeMap
:适用于需要对集合中的元素或键值对进行有序存储的场景。
4. 多线程环境:选择线程安全的集合类,如 ConcurrentHashMap
、Collections.synchronizedList()
。
ConcurrentHashMap
:适用于高并发情况下的键值对存储。Collections.synchronizedList()
:通过同步包装的线程安全集合。
7.2 如何优化集合的性能
优化集合的性能可以通过合理设置集合的初始容量,减少不必要的扩容操作和复制操作。以下是两个主要的优化方向:
7.2.1 初始化容量设置与避免多次扩容操作导致复制
集合类如 ArrayList
和 HashMap
在底层是基于动态数组实现的。当集合中的元素超过当前容量时,会自动扩容,通常扩容为原来容量的 1.5 倍。每次扩容都会创建一个新的更大数组,并将旧数组的元素复制到新数组中,这个过程会产生大量内存分配和元素复制的开销,特别是在大量数据插入时性能影响显著。
优化建议:
ArrayList
:在创建ArrayList
时,可以通过构造函数指定初始容量,避免扩容导致的性能开销。
List<String> list = new ArrayList<>(100); // 初始化容量为 100
HashMap
:同样可以通过构造函数指定初始容量和负载因子,以减少扩容带来的性能问题。
Map<String, Integer> map = new HashMap<>(100, 0.75f); // 初始容量为 100,负载因子为 0.75
- 100是初始容量,初始容量是指在初始化时分配的哈希表的初始大小。如果你预估有大量数据要存储,可以适当增加这个值,以避免哈希表频繁扩容的开销。
- 0.75f是负载因子,负载因子是一个衡量哈希表在自动扩容之前,允许多大比例的空间可以被使用的参数。负载因子 0.75 表示当哈希表中已使用的空间达到总容量的 75% 时,会自动扩容(通常是容量翻倍),以保持查找效率。如果你想减少扩容次数,可以设置一个较大的负载因子,但这可能会导致查找性能下降。
7.2.2 避免重复的集合转换操作
在开发中,频繁地在不同集合类型(如 List
和 Set
)之间转换会导致不必要的性能损耗,因为每次转换都需要遍历集合并复制所有元素。这种操作在大数据量的场景下尤其影响性能。
优化建议:
-
在选择集合类型时,尽量避免后期频繁的集合转换操作。比如,如果需要保证元素的唯一性,直接使用
Set
初始化集合,而不是先用List
,然后再转换为Set
。
8. 线程安全的集合
在多线程环境下,集合类的使用需要格外注意,因为标准的集合类(如 ArrayList
、HashMap
等)并不具备线程安全的特性。在多个线程并发访问或修改这些集合时,可能会导致数据不一致甚至引发程序崩溃。Java 提供了几种不同方式来保证集合的线程安全性,主要分为同步集合和并发集合框架。
8.1 同步集合与并发集合的区别
-
同步集合:通过同步(
synchronized
)机制来保证线程安全,通常会锁定整个集合操作,保证同一时刻只有一个线程可以修改集合。这种方法虽然能保证线程安全,但性能较低,尤其在高并发场景下,多个线程竞争同一锁时会导致性能瓶颈。 -
并发集合:并发集合框架(
java.util.concurrent
包)提供了一些集合类,它们使用更加精细的锁机制,甚至无锁机制,来提高并发场景下的性能。这些集合类支持高效的并发访问,减少线程间的争用,适用于高并发环境。
8.2 同步集合
同步集合是通过 Collections.synchronizedXXX()
方法对现有的非线程安全集合进行同步包装。所有的集合操作都会被加锁,确保同一时间只有一个线程能访问集合。虽然这保证了线程安全,但由于每次操作都需要加锁和解锁,性能较低,尤其在写操作频繁时,竞争锁的开销较大。
8.2.1 Collections.synchronizedList()
将 List
集合同步化,保证其在线程并发访问时的安全性。适合不太频繁的并发访问场景。
示例:
List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);synchronized (synchronizedList) {synchronizedList.add("Item 1"); // 在同步代码块中进行操作
}
注意:在迭代 synchronizedList
时,必须手动在外层加上 synchronized
块,确保整个迭代过程的线程安全性。
8.2.2 Collections.synchronizedMap()
将 Map
集合同步化,保证并发情况下的安全性。
示例:
Map<String, Integer> map = new HashMap<>();
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(map);synchronized (synchronizedMap) {synchronizedMap.put("key1", 1); // 在同步代码块中进行操作
}
8.2.3 同步集合的缺点
- 性能瓶颈:同步集合使用全局锁,每次访问集合时需要获取锁,这意味着多个线程同时访问时,会有锁竞争和阻塞,导致性能下降。
- 适用场景:同步集合适合低并发场景或写操作较少、读操作较多的情况。对于高并发场景,使用并发集合框架更加合适。
8.3 并发集合框架
并发集合框架(java.util.concurrent
)为多线程环境提供了高效、线程安全的集合类。这些类通过更复杂的机制(如分段锁或无锁算法)来提高在高并发场景下的性能。与同步集合相比,并发集合框架中的集合类具有更细粒度的锁定机制,能够支持更高的并发访问。
8.3.1 ConcurrentHashMap
-
概述:
ConcurrentHashMap
是HashMap
的线程安全版本,它采用分段锁机制(Segmented Locking
),将整个哈希表分为多个段,每个段有独立的锁,这样多个线程可以同时访问不同段的哈希表,从而提高并发性能。 -
特点:
- 线程安全,适用于高并发环境。
- 支持高效的读写操作,避免了传统同步集合中的全局锁。
- 读取操作几乎不需要加锁,写操作只对涉及的部分加锁。
示例:
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put("key1", 1); // 线程安全的插入操作
concurrentMap.put("key2", 2);int value = concurrentMap.get("key1"); // 线程安全的读取操作
-
适用场景:
ConcurrentHashMap
适合高并发场景,尤其在需要频繁读写键值对的情况下,性能优于Collections.synchronizedMap()
。
8.3.2 CopyOnWriteArrayList
和 CopyOnWriteArraySet
-
概述:
CopyOnWriteArrayList
和CopyOnWriteArraySet
是基于写时复制(Copy-on-Write)机制的集合类,适用于读多写少的场景。写操作时,会将整个数组复制一份进行修改,读操作时则不需要加锁。 -
特点:
- 读操作不会加锁,保证高效的读取性能。
- 每次写操作(如
add()
)时,会复制整个底层数组,所以写操作开销较大,适用于写操作较少的场景。
示例:
List<String> cowList = new CopyOnWriteArrayList<>();
cowList.add("Item 1"); // 写操作会复制整个底层数组for (String item : cowList) {System.out.println(item); // 读操作不会加锁
}
-
适用场景:适用于读多写少的场景,如缓存、配置项加载等。
8.3.3 阻塞队列 (BlockingQueue
)
阻塞队列是并发集合框架中的特殊队列,支持阻塞的插入和取出操作,通常用于生产者-消费者模型。在队列为空时,消费者线程会阻塞等待;在队列满时,生产者线程会阻塞,直到有空间为止。
ArrayBlockingQueue
-
概述:
ArrayBlockingQueue
是一个基于数组实现的有界阻塞队列,队列的大小是固定的。当队列满时,生产者线程会阻塞,直到有空间插入元素;当队列为空时,消费者线程会阻塞,直到有新的元素入队。
示例:
BlockingQueue<String> arrayBlockingQueue = new ArrayBlockingQueue<>(10);arrayBlockingQueue.put("Item 1"); // 阻塞插入,当队列满时会等待
String item = arrayBlockingQueue.take(); // 阻塞获取,当队列为空时会等待
-
适用场景:
ArrayBlockingQueue
适合在生产者-消费者模型中使用,尤其是在对队列长度有明确限制时。
LinkedBlockingQueue
-
概述:
LinkedBlockingQueue
是基于链表实现的阻塞队列,可以是有界队列(设置最大容量),也可以是无界队列(默认)。与ArrayBlockingQueue
不同,LinkedBlockingQueue
的吞吐量通常会更高,因为它的生产者和消费者使用独立的锁机制。
示例:
BlockingQueue<String> linkedBlockingQueue = new LinkedBlockingQueue<>();linkedBlockingQueue.put("Item 1"); // 阻塞插入
String item = linkedBlockingQueue.take(); // 阻塞获取
-
适用场景:
LinkedBlockingQueue
适合在生产者-消费者模型中使用,尤其是对队列长度没有严格限制的情况下。
8.4 总结
- 同步集合(如
Collections.synchronizedList()
)通过全局锁保证线程安全,但性能较低,适合并发访问不频繁的场景。 - 并发集合框架(如
ConcurrentHashMap
、CopyOnWriteArrayList
)通过更加精细的锁机制或无锁设计,适合高并发场景,特别是在读多写少、键值对存储、生产者-消费者模型中,表现优异。 - 阻塞队列(如
ArrayBlockingQueue
和LinkedBlockingQueue
)为生产者-消费者模型提供了线程安全的队列操作,适用于多线程环境下的任务调度与数据交换。
9. 表格总结
Java 集合框架实现类及其特点与使用情况
集合接口 | 实现类 | 特点 | 使用情况 |
---|---|---|---|
List | ArrayList | 基于动态数组,提供 O(1) 的随机访问,扩容时会重新分配内存,增删元素较慢(O(n))。 | 适用于读多写少、需要随机访问元素的场景,例如缓存、列表数据存储。 |
LinkedList | 基于双向链表,插入和删除操作高效(O(1)),但随机访问较慢(O(n))。 | 适用于频繁插入和删除操作的场景,特别是需要在中间或两端操作的场景,例如队列、双端队列。 | |
Vector | 线程安全的 ArrayList ,但性能较差。 | 适用于早期的 Java 代码中需要线程安全的场景,但不推荐在现代开发中使用。 | |
CopyOnWriteArrayList | 基于写时复制,写操作时复制整个数组,读操作不需要加锁,适合读多写少的场景。 | 适用于读多写少的场景,例如配置信息的缓存、事件监听器等。 | |
Set | HashSet | 基于哈希表,提供 O(1) 的插入、删除、查找操作,无序。 | 适用于需要保证元素唯一性且不关心顺序的场景,例如集合去重。 |
LinkedHashSet | 基于哈希表和链表,按插入顺序存储元素。 | 适用于既需要保证唯一性,又需要按照插入顺序遍历元素的场景。 | |
TreeSet | 基于红黑树,按自然顺序或自定义 Comparator 进行排序,插入、删除、查找时间复杂度 O(log n)。 | 适用于需要保证元素唯一性且按顺序存储的场景,例如排序后的集合存储。 | |
CopyOnWriteArraySet | 基于写时复制,写操作时复制整个底层数组,读操作不加锁,适合读多写少的场景。 | 适用于读多写少且需要线程安全的场景,例如缓存、线程间共享数据。 | |
Map | HashMap | 基于哈希表,提供 O(1) 的插入、删除和查找操作,键值无序,允许 null 键和 null 值。 | 适用于需要快速查找和插入键值对的场景,例如存储配置、数据缓存等。 |
LinkedHashMap | 基于哈希表和链表,按插入顺序或访问顺序存储键值对。 | 适用于既需要快速查找,又需要保持插入或访问顺序的场景,例如缓存实现。 | |
TreeMap | 基于红黑树,按键的自然顺序或自定义顺序排序,插入、删除、查找时间复杂度 O(log n)。 | 适用于需要按键排序存储键值对的场景,例如排序索引、自然顺序存储。 | |
ConcurrentHashMap | 线程安全,基于分段锁机制,允许多个线程同时访问不同的段,读操作无锁,写操作只对部分加锁。 | 适用于高并发场景,例如计数器、线程安全的缓存。 | |
Hashtable | 线程安全,早期版本的 HashMap ,不允许 null 键和 null 值,性能较差。 | 适用于需要线程安全但性能要求较低的场景,不推荐使用。 | |
Queue | LinkedList | 实现了 Queue 和 Deque 接口,支持队列(FIFO)和双端队列操作。 | 适用于需要双端队列和栈操作的场景,例如任务调度、双端队列实现。 |
PriorityQueue | 基于优先级堆,元素按优先级排序,默认最小堆,不允许 null 元素。 | 适用于需要按优先级处理任务或事件的场景,例如事件队列、任务调度。 | |
ArrayDeque | 基于数组的双端队列,提供高效的栈和队列操作,性能优于 LinkedList 。 | 适用于需要双端队列操作且需要高效性能的场景,例如栈、队列实现。 | |
BlockingQueue | ArrayBlockingQueue | 基于数组的有界阻塞队列,线程安全,队列满时会阻塞插入,队列空时会阻塞获取。 | 适用于生产者-消费者模型,队列大小固定的场景。 |
LinkedBlockingQueue | 基于链表的阻塞队列,可以是有界或无界队列,支持阻塞插入和获取操作。 | 适用于生产者-消费者模型,队列大小不固定或较大时的场景。 | |
PriorityBlockingQueue | 基于优先级堆的阻塞队列,按优先级排序,支持阻塞插入和获取操作。 | 适用于需要按优先级排序的任务调度场景。 | |
Deque | LinkedList | 实现了 Deque 接口,支持双端队列和栈操作。 | 适用于需要双端队列和栈操作的场景,例如任务调度、队列的实现。 |
ArrayDeque | 基于数组实现的双端队列,提供高效的栈和队列操作。 | 适用于需要双端队列操作且需要高效性能的场景,性能优于 LinkedList 。 |