目录
一. 概述
二. Collection接口实现类
三. Map接口实现类
四. 线程安全集合
五. List接口下集合实现原理
1. ArrayList实现原理
1.1. 基于动态数组
1.2. 随机访问
1.3. 添加元素
1.4. 删除元素
1.5. 迭代器
1.6. 克隆和序列化
1.7. ArrayList简单使用
2. LinkedList实现原理
2.1. 基于双向链表
2.2. 动态数据结构
2.3. 随机访问
2.4. 添加和删除元素
2.5. 迭代器
2.6. LinkedList简单使用
2.6.1. 基础操作
2.6.2. 栈操作
2.6.3. 队列操作
2.6.4. 双端队列操作
3. Vector实现原理
3.1. 同步性
3.2. 动态数组
3.3. 性能
3.4. 容量和大小
3.5. 遗留代码
3.6. 代码示例
六. Set接口下集合实现原理
1. HashSet实现原理
1.1. 基于 HashMap
1.2. 无序集合
1.3. 不允许重复
1.4. 快速查找
1.5. 不保证元素的唯一性
1.6. 扩容
1.8. 代码示例
1.8.1. 定义用户类
1.8.2. 测试类
1.8.3. 测试结果
2. LinkedHashSet实现原理
2.1. 基于 HashSet
2.2. 维护链表
2.3. 有序性
2.4. LinkedHashSet 的使用场景
2.5. 代码示例
2.5.1. 定义用户类
2.5.2. 测试类
2.5.3. 测试结果
3. TreeSet实现原理
3.1. 红黑树特性
3.2. TreeSet的关键特性
3.3. TreeSet的实现原理
3.4. 代码示例
3.4.1. 自定义用户类
3.4.2. 自定义测试类
3.4.3. 测试结果
七. Queue接口下集合实现原理
1. PriorityQueue实现原理
1.1. 排序机制
1.2. 插入操作
1.3. 删除操作
1.4. 非线程安全
1.5. 使用场景
1.6. 代码示例
1.6.1. 自定义用户类
1.6.2. 定义测试类
1.6.3. 测试结果
八. Map接口下集合实现原理
1. HashMap实现原理
1.1. 哈希表结构
1.2. 哈希码计算
1.3. 冲突解决
1.4. 动态扩容
1.5. 负载因子
1.6. 初始容量减少扩容次数
1.7. 代码实例
2. TreeMap实现原理
2.1. 红黑树特性
2.2. TreeMap的特性
2.3. TreeMap实现原理
2.5. 注意事项
2.4. 代码示例
3. LinkedHashMap实现原理
3.1. 继承自HashMap
3.2. 维护链表
3.3. 插入顺序
3.4. 访问顺序
3.5. 链表结构
3.6. 保证顺序的操作
3.7. 性能考虑
3.8. 示例代码
4. Hashtable实现原理
4.1. 基于数组和链表
4.2. 哈希码计算
4.3. 冲突解决
4.4. 线程安全
4.5. 不允许空键和空值
4.6. 迭代器
4.7. 性能
4.8. 注意事项
4.8. 代码示例
九. 常用线程安全集合
1. ConcurrentHashMap集合
1.1. 数据结构
1.2. 线程安全
1.3. 扩容机制
1.4. 性能优化
1.5. 特点
1.6. 注意事项
1.7. 代码示例
2. ConcurrentSkipListMap集合
2.1. 特性
2.2. 实现原理
2.3. 代码示例
3. ConcurrentSkipListSet集合
3.1. 特性
3.2. 实现原理
3.3. 代码示例
4. CopyOnWriteArrayList集合
4.1. 写时复制(Copy-On-Write)
4.2. 读操作不加锁
4.3. volatile 关键字
4.4. 锁分离
4.5. 适用于读多写少的场景
4.6. 注意事项
4.6. 使用示例
5. CopyOnWriteArraySet集合
5.1. 特性
5.2. 实现原理
5.3. 注意事项
5.4. 代码示例
6. ConcurrentLinkedQueue集合
6.1. 特性
6.2. 实现原理
6.3. 注意事项
6.4. 代码示例
7. ConcurrentLinkedDeque集合
7.1. 特性
7.2. 实现原理
7.3. 注意事项
7.4. 代码示例
一. 概述
Java 集合框架是一组用于存储和处理对象集合的类和接口的集合。这些集合类和接口可以分为两大类:集合(Collection)和 映射(Map)。
二. Collection接口实现类
- List 接口继承Collection接口
- ArrayList:基于动态数组实现的List(查询快,增删慢)
- LinkedList:基于双向链表实现的List
接口和Deque
接口(查询慢,增删快)- Vector:和ArrayList类似,但它是同步的(线程安全)
- Set 接口继承Collection接口
- HashSet:基于HashMap实现的Set。
- LinkedHashSet:类似于HashSet,但维护元素插入顺序。
- TreeSet:基于红黑树实现的Set,元素自动排序。
- Queue 接口继承Collection接口
- PriorityQueue:基于堆实现的Queue,元素按自然顺序或自定义Comparator排序。
- ArrayDeque:基于双向队列实现的Deque。
- LinkedList:也可以用作Queue。
三. Map接口实现类
- HashMap:基于哈希表实现的Map。
- LinkedHashMap:类似于HashMap,但维护插入顺序。
- TreeMap:基于红黑树实现的Map,键值按自然顺序或自定义Comparator排序。
- Hashtable:和HashMap类似,但它是同步的。
- ConcurrentHashMap:线程安全的HashMap实现。
四. 线程安全集合
在 java.util.concurrent 包下:
- ConcurrentHashMap:线程安全的HashMap。
- ConcurrentSkipListMap:线程安全的有序Map。
- ConcurrentSkipListSet:线程安全的有序Set。
- CopyOnWriteArrayList:线程安全的ArrayList。
- CopyOnWriteArraySet:线程安全的HashSet。
- ConcurrentLinkedQueue:线程安全的Queue。
- ConcurrentLinkedDeque:线程安全的双端Queue。
五. List接口下集合实现原理
1. ArrayList实现原理
ArrayList
是 Java 中最常用的集合类之一,它实现了 List
接口。
ArrayList
优点: 底层数据结构是数组,查询快,增删慢。
缺点: 线程不安全,效率高
1.1. 基于动态数组
ArrayList
内部使用一个动态数组(即数组列表)来存储元素。这个数组的大小是可变的,可以根据需要 自动扩容,扩容为原来的1.5倍(即新容量 = 旧容量 + (旧容量 >> 1)),这样可以在添加大量元素时减少扩容的次数。
1.2. 随机访问
ArrayList
支持快速随机访问,即可以通过索引快速定位元素。这是因为它是基于数组实现的,数组的随机访问时 间复杂度为 O(1)。
1.3. 添加元素
添加元素到 ArrayList
的时间复杂度为 O(1),如果数组空间足够的话。如果空间不足需要扩容,那么 时间复杂度为 O(n),其中 n 是数组中元素的数量。
1.4. 删除元素
删除元素的 时间复杂度为 O(n),因为删除操作可能需要移动被删除元素之后的所有元素。
1.5. 迭代器
ArrayList
提供了两种类型的迭代器:Iterator
和 ListIterator
。ListIterator
支持双向遍历(向前和向后),而 Iterator
只支持单向遍历。
1.6. 克隆和序列化
ArrayList
实现了 Cloneable
和 Serializable
接口,这意味着 ArrayList
可以被克隆,并且可以被序列化和反序列化。
1.7. ArrayList简单使用
package com.demo.array;import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/*** 文件名:Main* 创建者:* 创建时间:2024-09-18* 描述: list 测试*/
public class Main {public static void main(String[] args) {//arrayList的简单使用List<String> arrayList = new ArrayList<>();//1.添加元素arrayList.add("小明");arrayList.add("小王");arrayList.add("小李");//2.遍历元素for (String s : arrayList) {System.out.println("元素:"+s);}System.out.println("======================================");//3.移除元素Iterator<String> iterator = arrayList.iterator();while (iterator.hasNext()){String num = iterator.next();if (num.contains("小王")) {iterator.remove();}}//查看是否删除 小王 这个元素arrayList.forEach(e-> System.out.println("元素:"+e));}
}
2. LinkedList实现原理
LinkedList
是 Java 中的一个双向链表实现,它实现了 List
接口和 Deque
接口,因此它可以用作列表、堆栈和队列
LinkedList
优点: 底层数据结构是链表,查询慢,增删快。
缺点: 线程不安全,效率高
2.1. 基于双向链表
LinkedList
内部使用一个双向链表结构来存储元素。每个节点包含三个部分:存储数据的 data
部分,指向前一个节点的 prev
引用,以及指向后一个节点的 next
引用。
2.2. 动态数据结构
LinkedList
可以动态地添加和删除节点,而不需要像数组那样进行扩容操作。
2.3. 随机访问
虽然 LinkedList
支持通过索引进行随机访问,但由于其链表的结构,随机访问的时间复杂度为 O(n),因此在频繁执行随机访问操作时,性能不如 ArrayList
。
2.4. 添加和删除元素
LinkedList
在列表的头部、尾部或中间添加和删除元素都非常高效,因为这些操作只需要改变节点之间的引用关系,而不需要移动其他元素。
2.5. 迭代器
LinkedList
提供了 Iterator
和 ListIterator
两种迭代器。ListIterator
支持双向遍历,并且可以进行元素的添加、删除和替换操作。
2.6. LinkedList简单使用
2.6.1. 基础操作
package com.demo.array;import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.ListIterator;/*** 文件名:MainLinkedList* 创建者:* 创建时间:2024-09-18* 描述:LinkedList 示例*/
public class MainLinkedList {public static void main(String[] args) {//1.创建链表集合LinkedList<String> linkedList = new LinkedList<>();//2.添加元素linkedList.add("小王");linkedList.add("小明");linkedList.add("小李");//3.将"小黑" 插入索引 1 的位置linkedList.add(1, "小黑");//4.获取索引 0 的元素String firstElement = linkedList.get(0);//5.删除元素linkedList.remove("小明"); //删除 "小明"linkedList.remove(1); //删除索引 1 的元素//6.迭代元素for (String element : linkedList) {System.out.println("元素:"+element);}System.out.println("====================================================");//8.迭代器迭代ListIterator<String> iterator = linkedList.listIterator();//替换索引 1 的元素linkedList.set(1, "小红");while (iterator.hasNext()) {String element = iterator.next();System.out.println("元素:"+element);}System.out.println("====================================================");//9. 返回 "小黑" 的索引System.out.println("元素下标:"+linkedList.indexOf("小王"));System.out.println("====================================================");System.out.println("检查元素是否存在:"+linkedList.contains("小红"));System.out.println("列表大小:"+linkedList.size());linkedList.clear(); //清空列表Collections.sort(linkedList); //对列表进行排序}
}
2.6.2. 栈操作
LinkedList
可以用作栈(后进先出)
package com.demo.array;import java.util.LinkedList;/*** 文件名:MainLinkedList* 创建者:* 创建时间:2024-09-18* 描述:LinkedList 示例*/
public class MainLinkedList {public static void main(String[] args) {//1.LinkedList 可以用作栈(后进先出)LinkedList<String> stack = new LinkedList<>();//2.添加元素到栈顶stack.push("1");stack.push("2");stack.push("3");//3.移除并返回栈顶元素String topElement = stack.pop();System.out.println("栈顶元素:"+topElement);}
}
2.6.3. 队列操作
LinkedList
可以用作队列(先进先出)
package com.demo.array;import java.util.LinkedList;/*** 文件名:MainLinkedList* 创建者:* 创建时间:2024-09-18* 描述:LinkedList 示例*/
public class MainLinkedList {public static void main(String[] args) {//1.LinkedList 可以用作队列(先进先出)LinkedList<String> queue = new LinkedList<>();//2.在队尾添加元素queue.offer("1");queue.offer("2");queue.offer("3");//3.移除并返回队首元素String headElement = queue.poll();System.out.println("元素:"+headElement);}
}
2.6.4. 双端队列操作
LinkedList
实现了 Deque
接口,可以作为双端队列使用
package com.demo.array;import java.util.Deque;
import java.util.LinkedList;/*** 文件名:MainLinkedList* 创建者:* 创建时间:2024-09-18* 描述:LinkedList 示例*/
public class MainLinkedList {public static void main(String[] args) {//1.LinkedList 实现了 Deque 接口,可以作为双端队列使用Deque<Integer> deque = new LinkedList<>();//2.在队首添加元素deque.addFirst(1);//3.添加到队尾deque.addLast(2);deque.addLast(3);//4.移除并返回队首元素Integer firstElement = deque.pollFirst();//5.移除并返回队尾元素Integer lastElement = deque.pollLast();System.out.println("队首元素:"+firstElement);System.out.println("队尾元素:"+lastElement);}
}
3. Vector实现原理
Vector
是 Java 中的一个古老但不太推荐使用的类,它实现了 List
接口和 RandomAccess
接口,提供了一个动态数组的实现。
Vector
优点: 底层数据结构是数组,查询快,增删慢。
缺点: 线程安全,效率低
3.1. 同步性
Vector
是线程安全的,这意味着它的所有公开方法都是同步的。在多线程环境中,Vector
可以确保同时只有一个线程可以修改它的内部数据。
3.2. 动态数组
Vector
内部使用一个数组来存储元素,当添加元素超出数组容量时,Vector
会创建一个新的数组并将旧数组的元素复制到新数组中,这个过程称为“扩容”。默认情况下,扩容策略是将数组大小翻倍。
3.3. 性能
由于 Vector
的所有方法都是同步的,因此在单线程环境中它的性能通常不如 ArrayList
。在多线程环境中,虽然 Vector
提供了线程安全,但现代的并发集合(如 Collections.synchronizedList
或 CopyOnWriteArrayList
)通常提供更好的性能和灵活性。
3.4. 容量和大小
Vector
可以像 ArrayList
一样动态地调整大小,但它提供了一些额外的方法来直接操作容量,如 setCapacity
。
3.5. 遗留代码
Vector
是 Java 早期版本的一部分,现在已经很少使用。在新的 Java 代码中,通常推荐使用 ArrayList
(对于非线程安全的单线程场景)或 Collections.synchronizedList
(对于线程安全的简单场景),或者使用 java.util.concurrent
包中的并发集合类。
3.6. 代码示例
package com.demo.array;import java.util.Vector;/*** 文件名:MainVector* 创建者:* 创建时间:2024-09-18* 描述:Vector 使用示例*/
public class MainVector {public static void main(String[] args) {Vector<String> vector = new Vector<>();vector.add("小明");vector.add("小红");vector.add("小黑");// 获取并打印所有元素for (int i = 0; i < vector.size(); i++) {System.out.println(vector.get(i));}System.out.println("=================================");// 删除元素vector.remove("小红");// 再次打印所有元素for (int i = 0; i < vector.size(); i++) {System.out.println(vector.get(i));}}
}
六. Set接口下集合实现原理
1. HashSet实现原理
HashSet
实现了 Set
接口。HashSet
的实现原理 基于 HashMap
,它使用一个 HashMap
来存储元素,每个元素都作为 HashMap
的键,而对应的值是一个固定的对象(通常是 PRESENT
常量),它提供了一个简单、高效的方式来存储不重复的元素集合。
1.1. 基于 HashMap
HashSet
底层使用一个 HashMap
来存储元素。当你向 HashSet
添加元素时,它实际上是将元素作为键添加到 HashMap
中。
1.2. 无序集合
HashSet
不保证元素的顺序,每次迭代 HashSet
时,元素的顺序可能会不同。
1.3. 不允许重复
由于 HashMap
的键不能重复,所以 HashSet
也不允许重复的元素。尝试添加重复元素到 HashSet
时,它将不会被添加也不会抛出异常,一定要重写equals(Object o)和hashCode()方法
1.4. 快速查找
HashSet
利用 HashMap
的快速查找特性,提供了快速的查找、插入和删除操作。
1.5. 不保证元素的唯一性
如果元素正确地实现了 equals()
和 hashCode()
方法,HashSet
才能保证元素的唯一性。如果元素没有正确实现这些方法,HashSet
可能无法正确地识别重复元素。
1.6. 扩容
HashSet
的扩容是在其底层的HashMap
实现的扩容机制上进行的。HashSet
本身并不直接控制扩容,而是依赖于其内部使用的HashMap
的扩容行为(HashMap
默认的初始容量,通常是16,默认的负载因子是0.75)。
1.7. 序列化
HashSet
实现了 Serializable
接口,这意味着 HashSet
的实例可以被序列化和反序列化。
1.8. 代码示例
1.8.1. 定义用户类
package com.demo.kaujiejian;import java.util.Objects;/*** 文件名:UserTest* 创建者:* 创建时间:2024-09-11* 描述:重写equals(Object o)和hashCode()方法*/
public class UserTest {public UserTest(String name, int age) {this.name = name;this.age = age;}private String name;private int age;public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;UserTest userTest = (UserTest) o;return age == userTest.age && Objects.equals(name, userTest.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "UserTest{" +"name='" + name + '\'' +", age=" + age +'}';}
}
1.8.2. 测试类
package com.demo.array;import com.demo.kaujiejian.UserTest;import java.util.HashSet;
import java.util.Set;/*** 文件名:MainHashSet* 创建者:* 创建时间:2024-09-18* 描述:HashSet 示例*/
public class MainHashSet {public static void main(String[] args) {//1.如果字符串重复则添加失败Set<String> strSet = new HashSet<>();strSet.add("小明");strSet.add("小红");strSet.add("小黑");strSet.add("小明"); // 重复元素,不会被添加for (String str : strSet) {System.out.println(str);}//2.如果是对象添加相同的对象需要重写equals(Object o)和hashCode()方法Set<UserTest> user = new HashSet<>();user.add(new UserTest("小明",23));user.add(new UserTest("小红",22));user.add(new UserTest("小黑",26));//重复对象一定要重写equals(Object o)和hashCode()方法user.add(new UserTest("小明",23));for (UserTest u : user) {System.out.println(u);}}
}
1.8.3. 测试结果
2. LinkedHashSet实现原理
LinkedHashSet
继承自 HashSet
,但在此基础上增加了一个链表来维护元素的插入顺序。这意味着当你遍历 LinkedHashSet
时,元素将按照它们被添加的顺序进行迭代。
2.1. 基于 HashSet
LinkedHashSet
内部使用 HashSet
来存储元素,保证了元素的唯一性。
2.2. 维护链表
LinkedHashSet
内部使用一个双向链表来维护元素的插入顺序。每个元素在被添加到 HashSet
的同时,也会被添加到这个链表中。
2.3. 有序性
LinkedHashSet
可以保证元素的迭代顺序是按照它们被添加的顺序,这使得LinkedHashSet
在需要保持元素顺序的场景下非常有用。
2.4. LinkedHashSet 的使用场景
-
保持插入顺序: 当你需要一个
Set
集合,并且希望它能够保持元素的插入顺序时,LinkedHashSet
是一个很好的选择。 -
避免重复:
LinkedHashSet
不允许重复元素,这与HashSet
一样。 -
性能考虑:
LinkedHashSet
在插入和删除操作时提供了较好的性能,同时由于其有序性,它在需要顺序访问的场景下比HashSet
更合适。
2.5. 代码示例
2.5.1. 定义用户类
package com.demo.kaujiejian;import java.util.Objects;/*** 文件名:UserTest* 创建者:* 创建时间:2024-09-11* 描述:*/
public class UserTest {public UserTest(String name, int age) {this.name = name;this.age = age;}private String name;private int age;public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;UserTest userTest = (UserTest) o;return age == userTest.age && Objects.equals(name, userTest.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "UserTest{" +"name='" + name + '\'' +", age=" + age +'}';}
}
2.5.2. 测试类
package com.demo.array;import com.demo.kaujiejian.UserTest;
import java.util.LinkedHashSet;
import java.util.Set;/*** 文件名:MainLinkedHashSet* 创建者:* 创建时间:2024-09-18* 描述:LinkedHashSet 示例*/
public class MainLinkedHashSet {public static void main(String[] args) {//1.如果字符串重复则添加失败Set<String> linkedHashSet = new LinkedHashSet<>();linkedHashSet.add("小明");linkedHashSet.add("小红");linkedHashSet.add("小黑");linkedHashSet.add("小明"); // 重复元素,不会被添加for (String str : linkedHashSet) {System.out.println(str); //按照添加顺序打印元素}//2.如果是对象添加相同的对象需要重写equals(Object o)和hashCode()方法Set<UserTest> userTestLinkedHashSet = new LinkedHashSet<>();userTestLinkedHashSet.add(new UserTest("小明",23));userTestLinkedHashSet.add(new UserTest("小红",22));userTestLinkedHashSet.add(new UserTest("小黑",26));//重复对象一定要重写equals(Object o)和hashCode()方法userTestLinkedHashSet.add(new UserTest("小明",23));for (UserTest u : userTestLinkedHashSet) {System.out.println(u); //按照添加顺序打印元素}}
}
2.5.3. 测试结果
3. TreeSet实现原理
TreeSet
是 Java 中的一个集合类,它实现了 Set
接口。TreeSet
基于 TreeMap
的实现,是一个红黑树(一种自平衡二叉搜索树)。
3.1. 红黑树特性
- 自平衡:红黑树通过一系列旋转操作保持树的平衡,确保树的高度大致等于 log(n),其中 n 是树中元素的数量。
- 有序性:红黑树保证了元素的有序性,使得元素可以按照自然顺序或自定义顺序进行排序。
- 二叉搜索树:红黑树是一种特殊的二叉搜索树,其中每个节点都有一个颜色属性(红或黑),用于维护树的平衡。
3.2. TreeSet的关键特性
- 元素唯一性:
TreeSet
不允许重复元素,它会自动根据元素的自然顺序或自定义比较器进行排序。- 有序集合:
TreeSet
保证了元素的顺序,可以用于需要有序数据的场合。- 性能:
TreeSet
提供了对元素的快速查找、插入和删除操作,时间复杂度为 O(log(n))。
3.3. TreeSet的实现原理
TreeSet
内部使用一个TreeMap
来存储元素,其中元素作为键,一个固定的对象(如PRESENT
)作为值。- 当元素添加到
TreeSet
时,实际上是将元素添加到TreeMap
的键集中。TreeSet
维护了一个有序的结构,使得元素可以按照排序顺序进行迭代。
3.4. 代码示例
3.4.1. 自定义用户类
package com.demo.array;import java.util.Objects;/*** 文件名:User* 创建者:* 创建时间:2024-09-19* 描述:测试类,treeSet实现Comparable接口中的compareTo方法*/
public class User implements Comparable<User>{private String name;private int age;public User(String name, int age) {this.name = name;this.age = age;}@Overridepublic int compareTo(User o) {return Integer.compare(this.age, o.age);}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;User user = (User) o;return age == user.age && Objects.equals(name, user.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}
}
3.4.2. 自定义测试类
package com.demo.array;import java.util.TreeSet;/*** 文件名:MainTreeSet* 创建者:* 创建时间:2024-09-19* 描述:TreeSet 示例*/
public class MainTreeSet {public static void main(String[] args) {//1.Integer实现了 Comparable 方法会参与排序TreeSet<Integer> treeSet = new TreeSet<>();treeSet.add(3);treeSet.add(1);treeSet.add(2);for (Integer number : treeSet) {System.out.println(number);}System.out.println("====================================================");//2.String类中也实现了 Comparable 方法会参与排序TreeSet<String> strTreeSet = new TreeSet<>();strTreeSet.add("二");strTreeSet.add("的");strTreeSet.add("个");strTreeSet.add("一");for (String str : strTreeSet) {System.out.println(str);}System.out.println("====================================================");//3.自定义类中也实现了 Comparable 接口TreeSet<User> userTreeSet = new TreeSet<>();userTreeSet.add(new User("小明",23));userTreeSet.add(new User("小红",22));userTreeSet.add(new User("小黑",26));for (User user : userTreeSet) {System.out.println(user);}}
}
3.4.3. 测试结果
七. Queue接口下集合实现原理
1. PriorityQueue实现原理
PriorityQueue
是 Java 中的一个集合类,它实现了 Queue
接口,主要用于实现优先队列。在优先队列中,元素根据其自然顺序或者通过提供的比较器(Comparator)来确定优先级,元素会根据优先级进行排序。
1.1. 基于优先级堆(Priority Heap)
PriorityQueue
内部使用一个优先级堆来存储元素。优先级堆通常是一个二叉堆,可以是最小堆或最大堆。在最小堆中,每个节点的值都小于或等于其子节点的值。
1.1. 排序机制
默认情况下,PriorityQueue 使用元素的自然顺序(通过 compareTo 方法)来排序元素。可以通过构造函数提供一个 Comparator 来自定义元素的排序规则。
1.2. 插入操作
元素添加到队列时,会根据优先级堆的规则进行上浮操作,确保队列始终保持有序状态。
1.3. 删除操作
删除操作通常涉及到移除堆顶元素(优先级最高的元素),然后进行下沉操作来恢复堆的有序状态。
1.4. 非线程安全
PriorityQueue
是非线程安全的。如果需要线程安全的优先队列,可以使用 PriorityBlockingQueue
。
1.5. 使用场景
PriorityQueue
提供了一个基于优先级的队列,适用于需要根据元素优先级处理元素的场景。
1.6. 代码示例
1.6.1. 自定义用户类
package com.demo.array;/*** 文件名:MyUser* 创建者:* 创建时间:2024-09-19* 描述:自定义测试类*/
public class MyUser implements Comparable<MyUser>{private String name;private int age;public MyUser(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic int compareTo(MyUser user) {return Integer.compare(this.age,user.getAge());}@Overridepublic String toString() {return "MyUser{" +"name='" + name + '\'' +", age=" + age +'}';}
}
1.6.2. 定义测试类
package com.demo.array;import java.util.PriorityQueue;/*** 文件名:MainPriorityQueue* 创建者:宁贝贝* 创建时间:2024-09-19* 描述:PriorityQueue 优先队列集合元素根据其自然顺序或者通过提供的比较器(Comparator)来确定优先级*/
public class MainPriorityQueue {public static void main(String[] args) {PriorityQueue<MyUser> priorityQueue = new PriorityQueue<>();priorityQueue.add(new MyUser("小明",3));priorityQueue.add(new MyUser("小红",1));priorityQueue.add(new MyUser("小黑",2));//添加元素priorityQueue.offer(new MyUser("小家",0));//使用 peek() 方法查看但不移除队列中优先级最高的元素System.out.println("获取优先级最高的元素:"+priorityQueue.peek());while (!priorityQueue.isEmpty()) {//poll() 方法返回并移除队列中优先级最高的元素MyUser element = priorityQueue.poll();System.out.println("元素:"+element);}}
}
1.6.3. 测试结果
八. Map接口下集合实现原理
Map接口是一个存储键值对的数据结构,它包含多个实现类集合,主要有 HashMap,TreeMap,LinkedHashMap,Hashtable。
1. HashMap实现原理
Java中的HashMap
是一种基于哈希表的Map实现,它提供了快速的查找、插入和删除操作,HashMap是非线程安全。
1.1. 哈希表结构
HashMap
内部使用一个数组(称为桶数组)来存储元素。每个数组元素称为一个桶(Bucket),它可以包含一个或多个键值对(Entry)。当插入键值对时,HashMap
会根据键的哈希码来计算它应该存储在哪个桶中。
1.2. 哈希码计算
HashMap
通过键的hashCode()
方法计算哈希码,然后使用一个扰动函数(通常是与操作)来减少哈希冲突。扰动函数确保了HashMap
的键分布均匀,提高了查找效率。
1.3. 冲突解决
如果多个键的哈希码相同(哈希冲突),它们会形成链表。在Java 8之前,HashMap
使用链表解决冲突。从Java 8开始,HashMap
引入了红黑树来优化长链表的性能问题,当链表长度超过一定阈值(默认为8)时,链表会转换成红黑树。
1.4. 动态扩容
当HashMap
中的元素数量达到负载因子(默认为0.75)与当前容量的乘积时,HashMap
会进行扩容操作。扩容通常是将桶数组的大小翻倍,并重新计算所有键值对的哈希码,将它们分配到新的桶中。
1.5. 负载因子
HashMap
有一个负载因子,用于控制哈希表的扩容时机。负载因子越小,哈希表的扩容越频繁,但可以减少哈希冲突。负载因子越大,哈希表的扩容频率降低,但可能会增加哈希冲突。
1.6. 初始容量减少扩容次数
HashMap
可以接受一个初始容量作为构造参数,这有助于减少扩容操作的次数。
1.7. 代码实例
package com.demo.array;import java.util.HashMap;/*** 文件名:MainHashMap* 创建者:* 创建时间:2024-09-20* 描述:HashMap 使用示例*/
public class MainHashMap {public static void main(String[] args) {//创建HashMap实例HashMap<String, UserTest> map = new HashMap<>();//添加键值对map.put("1", new UserTest("1","小明",23));map.put("2", new UserTest("2","小红",22));map.put("3", new UserTest("3","小黑",27));//1.获取值UserTest user = map.get("1");System.out.println("获取元素:" + user);System.out.println("======================================");//检查键是否存在if (map.containsKey("2")) {System.out.println("检查键是否存在:" + map.get("2"));}System.out.println("======================================");//删除键值对map.remove("2");//遍历HashMapfor (String key : map.keySet()) {System.out.println(key + " : " + map.get(key));}System.out.println("======================================");//遍历EntrySetSystem.out.println("遍历所有元素:");for (HashMap.Entry<String, UserTest> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}}
}/*** 自定义测试类*/
class UserTest{private String id;private String name;private int age;public UserTest(String id, String name, int age) {this.id = id;this.name = name;this.age = age;}@Overridepublic String toString() {return "UserTest{" +"id='" + id + '\'' +", name='" + name + '\'' +", age=" + age +'}';}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getId() {return id;}public void setId(String id) {this.id = id;}
}
2. TreeMap实现原理
TreeMap
是 Java 中的一个集合类,它实现了 SortedMap
接口。TreeMap
基于红黑树(一种自平衡二叉搜索树)实现,保证了元素的排序。
2.1. 红黑树特性
- 自平衡:红黑树通过一系列旋转操作保持树的平衡,确保树的高度大致等于 log(n),其中 n 是树中元素的数量。
- 有序性:红黑树保证了元素的有序性,使得元素可以按照自然顺序或自定义顺序进行排序。
- 二叉搜索树:红黑树是一种特殊的二叉搜索树,其中每个节点的左子节点的值小于节点本身的值,右子节点的值大于节点本身的值。
2.2. TreeMap的特性
- 元素唯一性:
TreeMap
不允许重复的键,如果尝试插入一个已存在的键,它的值将被更新。- 有序集合:
TreeMap
保证了元素的顺序,可以用于需要有序数据的场合。- 性能:
TreeMap
提供了对元素的快速查找、插入和删除操作,时间复杂度为 O(log(n))。
2.3. TreeMap实现原理
TreeMap
内部使用一个红黑树来存储键值对,其中键作为红黑树的节点。- 当元素添加到
TreeMap
时,它们会被插入到红黑树中,并根据键的自然顺序或自定义比较器进行排序。TreeMap
维护了一个指向红黑树中第一个(最小)和最后一个(最大)元素的引用,以及一个指向当前元素的引用,以便快速访问第一个、最后一个和当前元素。
2.5. 注意事项
TreeMap
要求键必须实现Comparable
接口,或者在创建TreeMap
时提供一个Comparator
。TreeMap
是可导航的,提供了firstEntry
、lastEntry
、lowerEntry
、higherEntry
等方法来快速访问元素。TreeMap
是非线程安全的。TreeMap
是一个可排序的、不允许重复键的映射,适用于需要有序数据集的场景。
2.4. 代码示例
package com.demo.array;import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;/*** 文件名:MainTreeMap* 创建者:* 创建时间:2024-09-20* 描述:TreeMap 测试示例*/
public class MainTreeMap {public static void main(String[] args) {//1.自定义排序TreeMap<Integer, TreeMapUser> treeMap = new TreeMap<>(new MyComparator());treeMap.put(1, new TreeMapUser("1","小明",23));treeMap.put(2, new TreeMapUser("2","小红",22));treeMap.put(3, new TreeMapUser("3","小黑",27));// 遍历 TreeMap,for (Map.Entry<Integer, TreeMapUser> entry : treeMap.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}}
}
/*** 自定义测试类*/
class TreeMapUser {private String id;private String name;private int age;public TreeMapUser(String id, String name, int age) {this.id = id;this.name = name;this.age = age;}@Overridepublic String toString() {return "UserTest{" +"id='" + id + '\'' +", name='" + name + '\'' +", age=" + age +'}';}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getId() {return id;}public void setId(String id) {this.id = id;}
}/*** 自定义比较器*/
class MyComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {// 升序排序return o1.compareTo(o2);}
}
3. LinkedHashMap实现原理
LinkedHashMap
是 Java 中的一个集合类,它继承自 HashMap
,并且使用链表来维护元素的插入顺序或访问顺序。
3.1. 继承自HashMap
LinkedHashMap
继承自 HashMap
,因此它具有 HashMap
的所有基本特性,包括键的唯一性、快速的查找和更新操作等。
3.2. 维护链表
LinkedHashMap
内部使用一个双向链表来维护元素的顺序。每个元素在 HashMap
的桶数组中是一个节点,同时也是链表中的一个节点。
3.3. 插入顺序
默认情况下,LinkedHashMap
维护元素的插入顺序。当元素被添加到 LinkedHashMap
时,它们会被插入到链表的尾部。
3.4. 访问顺序
如果 LinkedHashMap
在创建时指定了 accessOrder
参数为 true
,则它将维护元素的访问顺序,即最近访问的元素会被移动到链表的尾部。
3.5. 链表结构
LinkedHashMap
的链表结构由 Entry
类实现,它继承自 HashMap.Node
。每个 Entry
节点包含 before
和 after
指针,用于维护双向链表。
3.6. 保证顺序的操作
- 插入操作:新元素总是插入到链表的尾部。
- 访问操作:如果
accessOrder
为true
,则访问的元素会被移动到链表尾部。- 删除操作:删除元素时,相应的链表节点也会被删除。
3.7. 性能考虑
LinkedHashMap
在大多数操作(插入、删除、访问)上都保持了与 HashMap
相似的性能(平均时间复杂度为 O(1))。
3.8. 示例代码
package com.demo.array;import java.util.LinkedHashMap;
import java.util.Map;/*** 文件名:MainLinkedHashMap* 创建者:* 创建时间:2024-09-20* 描述:LinkedHashMap 测试示例*/
public class MainLinkedHashMap {public static void main(String[] args) {//1.创建一个按照插入顺序排序的 LinkedHashMapLinkedHashMap<String, Integer> map = new LinkedHashMap<>();map.put("One", 1);map.put("Two", 2);map.put("Three", 3);// 遍历 LinkedHashMapfor (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}//2.创建一个按照访问顺序排序的 LinkedHashMap,把访问过的元素排在最后LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);accessOrderMap.put("One", 1);accessOrderMap.put("Two", 2);accessOrderMap.put("Three", 3);// 访问 "Two"accessOrderMap.get("Two");// 再次遍历,可以看到 "Two" 排到了最后for (Map.Entry<String, Integer> entry : accessOrderMap.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}}
}
4. Hashtable实现原理
Hashtable
是 Java 中的一个古老的集合类,它实现了 Map
接口。Hashtable
的实现原理基于一个数组,每个数组元素都是一个链表的头节点,这个链表用于解决哈希冲突。
4.1. 基于数组和链表
Hashtable
内部使用一个数组来存储元素,数组的每个位置称为一个“桶”。每个桶都包含一个链表,用于存储具有相同哈希值的元素。
4.2. 哈希码计算
Hashtable
使用键对象的 hashCode()
方法来计算哈希码,然后使用这个哈希码来确定元素在数组中的位置。
4.3. 冲突解决
如果两个键的哈希码相同,它们将被存储在同一个桶的链表中。
4.4. 线程安全
Hashtable
是线程安全的,所有公开的方法都是同步的。
4.5. 不允许空键和空值
Hashtable
不允许键或值为 null
。
4.6. 迭代器
Hashtable
提供了 Enumeration
类型的迭代器,而不是现代的 Iterator
。
4.7. 性能
由于 Hashtable
是线程安全的,它的性能通常比 HashMap
低,因为每次操作都需要同步。
4.8. 注意事项
Hashtable
是遗留类,它的大多数功能已经被HashMap
和ConcurrentHashMap
取代。Hashtable
继承自Dictionary
类,而HashMap
实现自Map
接口。- 在新的代码中,通常推荐使用
HashMap
来实现键值存储,如果需要线程安全的Map
,可以使用ConcurrentHashMap
。
4.8. 代码示例
package com.demo.array;import java.util.Enumeration;
import java.util.Hashtable;/*** 文件名:MainHashtable* 创建者:* 创建时间:2024-09-20* 描述:Hashtable 代码示例*/
public class MainHashtable {public static void main(String[] args) {// 创建 Hashtable 实例Hashtable<String, String> hashtable = new Hashtable<>();// 添加键值对hashtable.put("1", "小黑");hashtable.put("2", "小红");hashtable.put("3", "小白");// 获取值String age = hashtable.get("1");System.out.println("获取key为1的: " + age);System.out.println("==========================================");// 检查键是否存在if (hashtable.containsKey("2")) {System.out.println("检查元素是否存在:" + hashtable.get("2"));}System.out.println("==========================================");// 删除键值对hashtable.remove("1");// 遍历 Hashtablefor (Enumeration<String> keys = hashtable.keys(); keys.hasMoreElements(); ) {String key = keys.nextElement();String value = hashtable.get(key);System.out.println(key + " : " + value);}}
}
九. 常用线程安全集合
1. ConcurrentHashMap集合
(线程安全的HashMap)
ConcurrentHashMap
是 Java 中 java.util.concurrent
包下的一个线程安全的哈希表实现。它在内部使用分段锁(Segmentation Lock)或者细粒度的锁机制来提高并发性能,从而在多线程环境中提供高效的键值存储和访问。
1.1. 数据结构
ConcurrentHashMap
内部主要由数组、链表和红黑树组成。数组是存储桶,链表用于解决哈希冲突,红黑树用于提高搜索效率。
1.2. 线程安全
在 JDK 8 及以后的版本中,ConcurrentHashMap
使用 CAS(Compare-And-Swap)操作和 synchronized
同步块来保证线程安全。
1.3. 扩容机制
当 ConcurrentHashMap
中的元素数量达到一定阈值时,会触发扩容操作。扩容过程中,旧数组中的元素会被重新散列到新的数组中。
1.4. 性能优化
ConcurrentHashMap
通过减少锁的粒度,提高了并发访问的性能。在 JDK 8 中,它使用了一种细粒度的锁机制,而不是像早期版本那样使用分段锁。
1.5. 特点
- 高效的并发访问:
ConcurrentHashMap
提供了比Hashtable
更好的并发访问性能。- 动态扩容:可以根据需要动态扩容,以适应不断增长的数据量。
- 支持高性能迭代:即使在多线程环境中,也支持高效的迭代操作。
1.6. 注意事项
- 选择合适的初始容量:合理设置初始容量可以减少扩容操作的次数,提高性能。
- 考虑使用默认构造函数:如果不明确初始容量,可以使用默认构造函数,
ConcurrentHashMap
会提供一个合理的默认容量。- 避免在循环中使用
get
方法:在循环中使用get
方法可能会导致性能问题,考虑使用computeIfAbsent
或getOrDefault
等方法。
1.7. 代码示例
package com.demo.array;import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;/*** 文件名:MainConcurrentHashMap* 创建者:* 创建时间:2024-09-20* 描述:ConcurrentHashMap 使用示例(线程安全的HashMap)*/
public class MainConcurrentHashMap {public static void main(String[] args) {ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();map.put("One", "小红");map.put("Two", "小白");map.put("Three", "小黑");// 获取值String value = map.get("One");System.out.println("Value: " + value);System.out.println("============================");//判断是否存在if(map.containsKey("One")){System.out.println("检查元素是否存在:"+map.get("One"));}System.out.println("============================");// 删除键值对map.remove("Two");// 遍历 ConcurrentHashMapfor (Map.Entry<String, String> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}}
}
2. ConcurrentSkipListMap集合
(线程安全的有序Map)
ConcurrentSkipListMap
是 Java 中 java.util.concurrent
包下的一个线程安全的有序映射表数据结构,它底层的数据结构是一个跳表(SkipList),线程安全集合。
2.1. 特性
- 线程安全:
ConcurrentSkipListMap
提供了线程安全的有序映射表实现。- 有序性:它保证了键的有序性,可以按照键的自然顺序或自定义顺序进行排序。
- 高性能:相比于
TreeMap
,ConcurrentSkipListMap
在并发环境下具有更高的性能。- 支持并发操作:可以在多线程环境中进行高效的并发读写操作。
2.2. 实现原理
- 跳表结构:
ConcurrentSkipListMap
内部使用多层索引,每一层都是一个有序的链表。- 索引节点:每一层的索引节点包含对下一个节点的引用,以及对下一层索引的引用。
- 自旋锁:在某些操作中,
ConcurrentSkipListMap
使用自旋锁来提高并发性能。- volatile 关键字:使用
volatile
关键字确保多线程环境下的内存可见性。
2.3. 代码示例
package com.demo.array;import java.util.Map;
import java.util.concurrent.ConcurrentSkipListMap;/*** 文件名:MainConcurrentSkipListMap* 创建者:* 创建时间:2024-09-20* 描述:ConcurrentSkipListMap 使用示例(线程安全的有序Map)*/
public class MainConcurrentSkipListMap {public static void main(String[] args) {// 创建一个 ConcurrentSkipListMap 实例ConcurrentSkipListMap<String, String> map = new ConcurrentSkipListMap<>();// 向映射表中添加键值对map.put("1", "小黑");map.put("2", "小红");map.put("3", "小明");map.put("4", "小白");map.put("5", "小李");// 迭代遍历映射表for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}System.out.println("========================================");// 获取并打印一个特定键的值System.out.println("获取key为3: " + map.get("3"));System.out.println("========================================");// 检查映射表是否包含某个键System.out.println("检查映射表是否包含(2)某个键: " + map.containsKey("2"));System.out.println("========================================");// 删除一个键值对map.remove("4");// 再次迭代遍历映射表for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}System.out.println("========================================");// 获取映射表的键的有序集合for (String key : map.keySet()) {System.out.println("key:"+key);}// 获取映射表的值的有序集合for (String value : map.values()) {System.out.println("values:"+value);}System.out.println("========================================");// 获取映射表的首个和最后一个元素Map.Entry<String, String> firstEntry = map.firstEntry();Map.Entry<String, String> lastEntry = map.lastEntry();System.out.println("获取第一个元素: " + firstEntry.getKey() + " : " + firstEntry.getValue());System.out.println("获取最后一个元素: " + lastEntry.getKey() + " : " + lastEntry.getValue());}
}
3. ConcurrentSkipListSet集合
(线程安全的有序Set)
ConcurrentSkipListSet
是 Java 中 java.util.concurrent
包下的一个线程安全的有序集合类,它使用跳表(Skip List)作为底层数据结构。
3.1. 特性
- 线程安全:
ConcurrentSkipListSet
提供了线程安全的集合实现,可以在多线程环境中安全地使用。- 有序性:它保证了元素的有序性,可以按照自然顺序或自定义顺序进行排序。
- 高性能:跳表结构提供了较高的查找、插入和删除性能,时间复杂度为 O(log(n))。
- 使用场景:
ConcurrentSkipListSet
是一个非常有用的集合类,它结合了SortedSet
的有序性和Concurrent
的线程安全性,适用于需要有序数据集和高并发访问的场景。
3.2. 实现原理
- 跳表结构:
ConcurrentSkipListSet
内部使用一个跳表,每个节点包含多个层级的指针,上层的指针指向下层的节点,形成多条路径,以实现快速查找。- 自旋锁:在某些操作中,如查找和删除,
ConcurrentSkipListSet
使用自旋锁来提高并发性能。- volatile 关键字:使用
volatile
关键字确保多线程环境下的内存可见性。- 分段锁:
ConcurrentSkipListSet
在底层实现中使用了分段锁(类似于ConcurrentHashMap
),以进一步提高并发性能。
3.3. 代码示例
package com.demo.array;import java.util.concurrent.ConcurrentSkipListSet;/*** 文件名:MainConcurrentSkipListSet* 创建者:* 创建时间:2024-09-20* 描述:ConcurrentSkipListSet 使用示例(线程安全的有序Set)*/
public class MainConcurrentSkipListSet {public static void main(String[] args) {// 创建一个 ConcurrentSkipListSet 实例ConcurrentSkipListSet<Integer> skipListSet = new ConcurrentSkipListSet<>();// 向集合中添加元素skipListSet.add(3);skipListSet.add(1);skipListSet.add(2);skipListSet.add(5);// 迭代遍历集合System.out.println("遍历集合中的元素:");for (Integer number : skipListSet) {System.out.println(number);}// 获取并打印第一个和最后一个元素System.out.println("第一个元素: " + skipListSet.first());System.out.println("最后一个元素: " + skipListSet.last());// 检查集合是否包含某个元素System.out.println("集合是否包含元素 2: " + skipListSet.contains(2));// 删除元素skipListSet.remove(3);// 再次迭代遍历集合System.out.println("删除元素 3 后:");for (Integer number : skipListSet) {System.out.println(number);}// 获取集合的尺寸System.out.println("集合的尺寸: " + skipListSet.size());// 清空集合skipListSet.clear();// 检查集合是否为空System.out.println("集合是否为空: " + skipListSet.isEmpty());}
}
4. CopyOnWriteArrayList集合
(线程安全的ArrayList)
CopyOnWriteArrayList
是 Java 中 java.util.concurrent
包下的一个线程安全的变体数组(ArrayList)实现。它通过在每次修改(添加、删除、设置元素)操作时复制整个底层数组来保证线程安全,从而在并发环境下提供高效的读操作性能。
4.1. 写时复制(Copy-On-Write)
当执行修改操作时,CopyOnWriteArrayList
会创建一个新的数组副本,修改在这个副本上进行,而读操作则作用于原始数组。
4.2. 读操作不加锁
由于写操作的复制机制,读操作不需要加锁,因此可以在多线程环境中高效地进行。
4.3. volatile 关键字
底层数组引用使用 volatile
关键字修饰,确保数组引用的可见性。
4.4. 锁分离
CopyOnWriteArrayList
实现了锁分离,即读操作和写操作不会相互阻塞。
4.5. 适用于读多写少的场景
由于写操作需要复制整个数组,如果写操作非常频繁,可能会导致性能问题。因此,它适用于读操作远多于写操作的场景。
4.6. 注意事项
- 内存消耗:由于写操作需要复制数组,因此可能会消耗更多的内存。
- 写操作性能:写操作的性能可能不如其他并发集合,因为每次修改都需要复制数组。
- 数据一致性:由于读操作作用于原始数组,因此在迭代过程中,迭代器可能不会看到最新的修改。
4.6. 使用示例
package com.demo.array;import java.util.concurrent.CopyOnWriteArrayList;/*** 文件名:MainCopyOnWriteArrayList* 创建者:* 创建时间:2024-09-20* 描述:CopyOnWriteArrayList 使用示例(线程安全的ArrayList)*/
public class MainCopyOnWriteArrayList {public static void main(String[] args) {CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();//1.添加元素list.add(1);list.add(2);list.add(3);// 迭代遍历列表for (Integer num : list) {System.out.println(num);}System.out.println("===================================");//2.删除元素list.remove(2);//3.修改元素list.set(1, 4);// 再次迭代遍历列表for (Integer num : list) {System.out.println(num);}}
}
5. CopyOnWriteArraySet集合
(线程安全的HashSet)
CopyOnWriteArraySet
是 Java 中 java.util.concurrent
包下的一个线程安全的集合类,它是基于 CopyOnWriteArrayList
实现的。
5.1. 特性
- 线程安全:
CopyOnWriteArraySet
提供了线程安全的集合实现,可以在多线程环境中安全地使用。- 有序性:它保证了元素的有序性,可以按照自然顺序或自定义顺序进行排序。
- 高性能读取:读操作不需要加锁,因此读性能很高。
- 写时复制:写操作(添加、删除等)会复制整个底层数组,因此写操作的开销较大。
5.2. 实现原理
- 基于
CopyOnWriteArrayList
:CopyOnWriteArraySet
内部使用CopyOnWriteArrayList
来存储元素。- 写操作:在执行写操作时,
CopyOnWriteArraySet
会创建一个新的数组副本,修改在这个副本上进行,然后替换原数组引用。- 迭代器:
CopyOnWriteArraySet
的迭代器在创建时会依赖于一个不变的数组快照,因此迭代器不会受到并发修改的影响。
5.3. 注意事项
- 写操作性能:由于写操作需要复制整个数组,因此写操作的性能开销较大,尤其是在数据量大的情况下。
- 内存消耗:写操作可能会消耗更多的内存,因为每次写操作都会创建一个新的数组副本。
- 数据一致性:由于迭代器是基于数组快照的,因此迭代器提供的数据视图是一致的,但可能不是最新的。
5.4. 代码示例
package com.demo.array;import java.util.concurrent.CopyOnWriteArraySet;/*** 文件名:MainCopyOnWriteArraySet* 创建者:* 创建时间:2024-09-20* 描述:CopyOnWriteArraySet 使用示例(线程安全的HashSet)*/
public class MainCopyOnWriteArraySet {public static void main(String[] args) {CopyOnWriteArraySet<Integer> set = new CopyOnWriteArraySet<>();//1.添加元素set.add(1);set.add(2);set.add(3);//迭代遍历集合for (Integer number : set) {System.out.println(number);}//2.删除元素set.remove(2);// 再次迭代遍历集合for (Integer number : set) {System.out.println(number);}}
}
6. ConcurrentLinkedQueue集合
(线程安全的Queue)
ConcurrentLinkedQueue
是 Java 中 java.util.concurrent
包下的一个线程安全的无界队列实现,它基于链接节点的非阻塞队列。
6.1. 特性
- 线程安全:
ConcurrentLinkedQueue
提供了线程安全的队列实现,可以在多线程环境中安全地使用。- 无界队列:它是一个无界队列,这意味着它可以存储任意数量的元素,但实际使用时需要考虑内存限制
,Queue
的先进先出特性和Concurrent
的线程安全性。- 非阻塞算法:使用高效的非阻塞算法,通过原子变量和 CAS (Compare-And-Swap) 操作来保证线程安全,而不是传统的锁机制。
- 高性能:在高并发场景下具有出色的性能表现,特别是在读多写少的场景中。
6.2. 实现原理
- 基于链表:
ConcurrentLinkedQueue
内部使用一个单向链表结构,每个节点包含元素和指向下一个节点的引用。- 无锁编程:通过无锁编程技术,利用 CAS 操作来实现节点的添加和删除,避免了锁的开销。
- 自旋锁:在某些情况下,使用自旋锁来保证操作的原子性。
- 哨兵节点:使用哨兵节点来处理只有一个节点时的特殊情况,避免 ABA 问题。
6.3. 注意事项
- 内存管理:由于
ConcurrentLinkedQueue
是无界的,需要合理控制生产者和消费者的速度,以避免内存溢出。- 并发问题:在并发环境下,
size()
和isEmpty()
方法的结果可能不准确,因为它们是基于某个时间点的估计。
6.4. 代码示例
package com.demo.array;import java.util.concurrent.ConcurrentLinkedQueue;/*** 文件名:MainConcurrentLinkedQueue* 创建者:* 创建时间:2024-09-20* 描述:ConcurrentLinkedQueue 使用示例 (线程安全的Queue)*/
public class MainConcurrentLinkedQueue {public static void main(String[] args) {ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();// 添加元素queue.add(1);queue.add(2);queue.add(3);// 迭代遍历队列for (Integer num : queue) {System.out.println(num);}// 从队列中获取并移除元素System.out.println("获取最新元素并移除: " + queue.poll());// 再次迭代遍历队列System.out.println("================================");for (Integer num : queue) {System.out.println(num);}}
}
7. ConcurrentLinkedDeque集合
(线程安全的双端Queue)
ConcurrentLinkedDeque
是 Java 中 java.util.concurrent
包下的一个线程安全的双端队列实现,它基于链接节点的无界并发双端队列。
7.1. 特性
- 线程安全:
ConcurrentLinkedDeque
提供了线程安全的双端队列实现,可以在多线程环境中安全地使用。- 无界队列:它是一个无界队列,这意味着它可以存储任意数量的元素,但实际使用时需要考虑内存限制。
- 非阻塞算法:使用高效的非阻塞算法,通过原子变量和 CAS (Compare-And-Swap) 操作来保证线程安全,而不是通过传统的锁机制。
- 高性能:在高并发场景下具有出色的性能表现。
- 双端操作:支持在队列的两端进行高效的添加和移除操作。
7.2. 实现原理
- 基于链表:
ConcurrentLinkedDeque
内部使用一个双向链表结构,每个节点包含元素和指向前后节点的引用。- 无锁编程:通过无锁编程技术,利用 CAS 操作来实现节点的添加和删除,避免了锁的开销。
- 自旋锁:在某些情况下,使用自旋锁来保证操作的原子性。
- volatile 关键字:使用
volatile
关键字确保多线程环境下的内存可见性。
7.3. 注意事项
- 内存管理:由于
ConcurrentLinkedDeque
是无界的,需要合理控制生产者和消费者的速度,以避免内存溢出。- 并发问题:在并发环境下使用
size()
和isEmpty()
方法时需要特别小心,因为它们的结果可能并不准确。
7.4. 代码示例
package com.demo.array;import java.util.concurrent.ConcurrentLinkedDeque;/*** 文件名:MainConcurrentLinkedDeque* 创建者:* 创建时间:2024-09-20* 描述:ConcurrentLinkedDeque 使用示例(线程安全的双端Queue)*/
public class MainConcurrentLinkedDeque {public static void main(String[] args) {ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();// 添加元素deque.add(1);deque.addLast(2);deque.addFirst(3);// 迭代遍历双端队列for (Integer num : deque) {System.out.println(num);}System.out.println("===============================");// 获取并移除队列头部元素System.out.println("移除头部元素: " + deque.poll());System.out.println("===============================");// 获取并移除队列尾部元素System.out.println("移除尾部元素: " + deque.pollLast());System.out.println("===============================");// 再次迭代遍历双端队列for (Integer num : deque) {System.out.println("遍历双端队列:"+num);}}
}