Java 集合详解

目录

一. 概述

二. 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接口实现类

  1.  List 接口继承Collection接口
    1.  ArrayList:基于动态数组实现的List(查询快,增删慢)
    2.  LinkedList:基于双向链表实现的List接口和Deque 接口(查询慢,增删快)
    3. Vector:和ArrayList类似,但它是同步的(线程安全)
  2.  Set 接口继承Collection接口
    • HashSet:基于HashMap实现的Set。
    • LinkedHashSet:类似于HashSet,但维护元素插入顺序。
    • TreeSet:基于红黑树实现的Set,元素自动排序。
  3.  Queue 接口继承Collection接口
    • PriorityQueue:基于堆实现的Queue,元素按自然顺序或自定义Comparator排序。
    • ArrayDeque:基于双向队列实现的Deque。
    • LinkedList:也可以用作Queue。

三. Map接口实现类

  1. HashMap:基于哈希表实现的Map。
  2. LinkedHashMap:类似于HashMap,但维护插入顺序。
  3. TreeMap:基于红黑树实现的Map,键值按自然顺序或自定义Comparator排序。
  4. Hashtable:和HashMap类似,但它是同步的。
  5. ConcurrentHashMap:线程安全的HashMap实现。

四. 线程安全集合

在 java.util.concurrent 包下:

  1. ConcurrentHashMap:线程安全的HashMap。
  2. ConcurrentSkipListMap:线程安全的有序Map。
  3. ConcurrentSkipListSet:线程安全的有序Set。
  4. CopyOnWriteArrayList:线程安全的ArrayList。
  5. CopyOnWriteArraySet:线程安全的HashSet。
  6. ConcurrentLinkedQueue:线程安全的Queue。
  7. 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 提供了两种类型的迭代器:IteratorListIteratorListIterator 支持双向遍历(向前和向后),而 Iterator 只支持单向遍历。

1.6. 克隆和序列化

ArrayList 实现了 CloneableSerializable 接口,这意味着 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 提供了 IteratorListIterator 两种迭代器。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.synchronizedListCopyOnWriteArrayList)通常提供更好的性能和灵活性。

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. 红黑树特性
  1. 自平衡:红黑树通过一系列旋转操作保持树的平衡,确保树的高度大致等于 log(n),其中 n 是树中元素的数量。
  2. 有序性:红黑树保证了元素的有序性,使得元素可以按照自然顺序或自定义顺序进行排序。
  3. 二叉搜索树:红黑树是一种特殊的二叉搜索树,其中每个节点都有一个颜色属性(红或黑),用于维护树的平衡。
3.2. TreeSet的关键特性
  1. 元素唯一性TreeSet 不允许重复元素,它会自动根据元素的自然顺序或自定义比较器进行排序。
  2. 有序集合TreeSet 保证了元素的顺序,可以用于需要有序数据的场合。
  3. 性能TreeSet 提供了对元素的快速查找、插入和删除操作,时间复杂度为 O(log(n))。
3.3. TreeSet的实现原理
  1. TreeSet 内部使用一个 TreeMap 来存储元素,其中元素作为键,一个固定的对象(如 PRESENT)作为值。
  2. 当元素添加到 TreeSet 时,实际上是将元素添加到 TreeMap 的键集中。
  3. 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. 红黑树特性

  1. 自平衡:红黑树通过一系列旋转操作保持树的平衡,确保树的高度大致等于 log(n),其中 n 是树中元素的数量。
  2. 有序性:红黑树保证了元素的有序性,使得元素可以按照自然顺序或自定义顺序进行排序。
  3. 二叉搜索树:红黑树是一种特殊的二叉搜索树,其中每个节点的左子节点的值小于节点本身的值,右子节点的值大于节点本身的值。

2.2. TreeMap的特性

  1. 元素唯一性TreeMap 不允许重复的键,如果尝试插入一个已存在的键,它的值将被更新。
  2. 有序集合TreeMap 保证了元素的顺序,可以用于需要有序数据的场合。
  3. 性能TreeMap 提供了对元素的快速查找、插入和删除操作,时间复杂度为 O(log(n))

2.3. TreeMap实现原理

  1. TreeMap 内部使用一个红黑树来存储键值对,其中键作为红黑树的节点。
  2. 当元素添加到 TreeMap 时,它们会被插入到红黑树中,并根据键的自然顺序或自定义比较器进行排序。
  3. TreeMap 维护了一个指向红黑树中第一个(最小)和最后一个(最大)元素的引用,以及一个指向当前元素的引用,以便快速访问第一个、最后一个和当前元素。

2.5. 注意事项

  1. TreeMap 要求键必须实现 Comparable 接口,或者在创建 TreeMap 时提供一个 Comparator
  2. TreeMap 是可导航的,提供了 firstEntrylastEntrylowerEntryhigherEntry 等方法来快速访问元素。
  3. TreeMap 是非线程安全的。
  4. 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 节点包含 beforeafter 指针,用于维护双向链表。

3.6. 保证顺序的操作

  1. 插入操作:新元素总是插入到链表的尾部。
  2. 访问操作:如果 accessOrdertrue,则访问的元素会被移动到链表尾部。
  3. 删除操作:删除元素时,相应的链表节点也会被删除。

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. 注意事项

  1. Hashtable 是遗留类,它的大多数功能已经被 HashMap ConcurrentHashMap 取代。
  2. Hashtable 继承自 Dictionary 类,而 HashMap 实现自 Map 接口。
  3. 在新的代码中,通常推荐使用 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. 特点

  1. 高效的并发访问ConcurrentHashMap 提供了比 Hashtable 更好的并发访问性能。
  2. 动态扩容:可以根据需要动态扩容,以适应不断增长的数据量。
  3. 支持高性能迭代:即使在多线程环境中,也支持高效的迭代操作。

1.6. 注意事项

  1. 选择合适的初始容量:合理设置初始容量可以减少扩容操作的次数,提高性能。
  2. 考虑使用默认构造函数:如果不明确初始容量,可以使用默认构造函数,ConcurrentHashMap 会提供一个合理的默认容量。
  3. 避免在循环中使用 get 方法:在循环中使用 get 方法可能会导致性能问题,考虑使用 computeIfAbsentgetOrDefault 等方法。

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. 特性

  1. 线程安全ConcurrentSkipListMap 提供了线程安全的有序映射表实现。
  2. 有序性:它保证了键的有序性,可以按照键的自然顺序或自定义顺序进行排序。
  3. 高性能:相比于 TreeMapConcurrentSkipListMap 在并发环境下具有更高的性能。
  4. 支持并发操作:可以在多线程环境中进行高效的并发读写操作。

2.2. 实现原理

  1. 跳表结构ConcurrentSkipListMap 内部使用多层索引,每一层都是一个有序的链表。
  2. 索引节点:每一层的索引节点包含对下一个节点的引用,以及对下一层索引的引用。
  3. 自旋锁:在某些操作中,ConcurrentSkipListMap 使用自旋锁来提高并发性能。
  4. 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. 特性

  1. 线程安全ConcurrentSkipListSet 提供了线程安全的集合实现,可以在多线程环境中安全地使用。
  2. 有序性:它保证了元素的有序性,可以按照自然顺序或自定义顺序进行排序。
  3. 高性能:跳表结构提供了较高的查找、插入和删除性能,时间复杂度为 O(log(n))。
  4. 使用场景ConcurrentSkipListSet 是一个非常有用的集合类,它结合了 SortedSet 的有序性和 Concurrent 的线程安全性,适用于需要有序数据集和高并发访问的场景。

3.2. 实现原理

  1. 跳表结构ConcurrentSkipListSet 内部使用一个跳表,每个节点包含多个层级的指针,上层的指针指向下层的节点,形成多条路径,以实现快速查找。
  2. 自旋锁:在某些操作中,如查找和删除,ConcurrentSkipListSet 使用自旋锁来提高并发性能。
  3. volatile 关键字:使用 volatile 关键字确保多线程环境下的内存可见性。
  4. 分段锁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. 注意事项

  1. 内存消耗:由于写操作需要复制数组,因此可能会消耗更多的内存。
  2. 写操作性能:写操作的性能可能不如其他并发集合,因为每次修改都需要复制数组。
  3. 数据一致性:由于读操作作用于原始数组,因此在迭代过程中,迭代器可能不会看到最新的修改。

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. 特性

  1. 线程安全CopyOnWriteArraySet 提供了线程安全的集合实现,可以在多线程环境中安全地使用。
  2. 有序性:它保证了元素的有序性,可以按照自然顺序或自定义顺序进行排序。
  3. 高性能读取:读操作不需要加锁,因此读性能很高。
  4. 写时复制:写操作(添加、删除等)会复制整个底层数组,因此写操作的开销较大。

5.2. 实现原理

  1. 基于 CopyOnWriteArrayListCopyOnWriteArraySet 内部使用 CopyOnWriteArrayList 来存储元素。
  2. 写操作:在执行写操作时,CopyOnWriteArraySet 会创建一个新的数组副本,修改在这个副本上进行,然后替换原数组引用。
  3. 迭代器CopyOnWriteArraySet 的迭代器在创建时会依赖于一个不变的数组快照,因此迭代器不会受到并发修改的影响。

5.3. 注意事项

  1. 写操作性能:由于写操作需要复制整个数组,因此写操作的性能开销较大,尤其是在数据量大的情况下。
  2. 内存消耗:写操作可能会消耗更多的内存,因为每次写操作都会创建一个新的数组副本。
  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. 特性

  1. 线程安全ConcurrentLinkedQueue 提供了线程安全的队列实现,可以在多线程环境中安全地使用。
  2. 无界队列:它是一个无界队列,这意味着它可以存储任意数量的元素,但实际使用时需要考虑内存限制,Queue 的先进先出特性和 Concurrent 的线程安全性。
  3. 非阻塞算法:使用高效的非阻塞算法,通过原子变量和 CAS (Compare-And-Swap) 操作来保证线程安全,而不是传统的锁机制。
  4. 高性能:在高并发场景下具有出色的性能表现,特别是在读多写少的场景中。

6.2. 实现原理

  1. 基于链表ConcurrentLinkedQueue 内部使用一个单向链表结构,每个节点包含元素和指向下一个节点的引用。
  2. 无锁编程:通过无锁编程技术,利用 CAS 操作来实现节点的添加和删除,避免了锁的开销。
  3. 自旋锁:在某些情况下,使用自旋锁来保证操作的原子性。
  4. 哨兵节点:使用哨兵节点来处理只有一个节点时的特殊情况,避免 ABA 问题。

6.3. 注意事项

  1. 内存管理:由于 ConcurrentLinkedQueue 是无界的,需要合理控制生产者和消费者的速度,以避免内存溢出。
  2. 并发问题:在并发环境下,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. 特性

  1. 线程安全ConcurrentLinkedDeque 提供了线程安全的双端队列实现,可以在多线程环境中安全地使用。
  2. 无界队列:它是一个无界队列,这意味着它可以存储任意数量的元素,但实际使用时需要考虑内存限制。
  3. 非阻塞算法:使用高效的非阻塞算法,通过原子变量和 CAS (Compare-And-Swap) 操作来保证线程安全,而不是通过传统的锁机制。
  4. 高性能:在高并发场景下具有出色的性能表现。
  5. 双端操作:支持在队列的两端进行高效的添加和移除操作。

7.2. 实现原理

  1. 基于链表ConcurrentLinkedDeque 内部使用一个双向链表结构,每个节点包含元素和指向前后节点的引用。
  2. 无锁编程:通过无锁编程技术,利用 CAS 操作来实现节点的添加和删除,避免了锁的开销。
  3. 自旋锁:在某些情况下,使用自旋锁来保证操作的原子性。
  4. volatile 关键字:使用 volatile 关键字确保多线程环境下的内存可见性。

7.3. 注意事项

  1. 内存管理:由于 ConcurrentLinkedDeque 是无界的,需要合理控制生产者和消费者的速度,以避免内存溢出。
  2. 并发问题:在并发环境下使用 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);}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/428092.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux环境变量进程地址空间

目录 一、初步认识环境变量 1.1常见的环境变量 1.2环境变量的基本概念 二、命令行参数 2.1通过命令行参数获取环境变量 2.2本地变量和内建命令 2.3环境变量的获取 三、进程地址空间 3.1进程&#xff08;虚拟&#xff09;地址空间的引入 3.2进程地址空间的布局和理解 …

11年计算机考研408-数据结构

设执行了k次。 解析&#xff1a; d要第一个出&#xff0c;那么abc先入栈&#xff0c;d入栈然后再出栈&#xff0c;这前面是一个固定的流程&#xff0c;后面就很灵活了&#xff0c;可以ecba&#xff0c;ceba&#xff0c;cbea&#xff0c;cbae。 答案是4个序列。 解析&#xff1a…

【论文阅读】PERCEIVER-ACTOR: A Multi-Task Transformer for Robotic Manipulation

Abstract transformers凭借其对大型数据集的扩展能力&#xff0c;彻底改变了视觉和自然语言处理。但在机器人操作中&#xff0c;数据既有限又昂贵。通过正确的问题表述&#xff0c;操纵仍然可以从变形金刚中受益吗&#xff1f;我们使用peract来研究这个问题&#xff0c;peract…

Spring Boot利用dag加速Spring beans初始化

1.什么是Dag&#xff1f; 有向无环图(Directed Acyclic Graph)&#xff0c;简称DAG&#xff0c;是一种有向图&#xff0c;其中没有从节点出发经过若干条边后再回到该节点的路径。换句话说&#xff0c;DAG中不存在环路。这种数据结构常用于表示并解决具有依赖关系的问题。 DAG的…

elasticsearch同步mysql方案

文章目录 1、1. 使用数据库触发器2. 使用定时任务3. 监听MySQL二进制日志&#xff08;binlog&#xff09;4. 使用数据管道5. 使用第三方工具或服务6. 编写自定义脚本注意事项 2、1. 使用Logstash步骤&#xff1a;示例配置&#xff1a; 2. 使用Debezium步骤&#xff1a; 3. 自定…

【Redis入门到精通三】Redis核心数据类型(List,Set)详解

目录 Redis数据类型 ​编辑 1.List类型 &#xff08;1&#xff09;常见命令 &#xff08;2&#xff09;内部编码 2.Set类型 &#xff08;1&#xff09;常见命令 &#xff08;2&#xff09;内部编码 Redis数据类型 查阅Redis官方文档可知&#xff0c;Redis提供给用户的核…

JavaScript - Document文档操作

1. 前言 ​​​​​​​ 编写网页时&#xff0c;我们需要时刻操作文档进而完成我们想要的效果。这就是通过文档对象模型实现&#xff0c;使用Document对象控制HTML以及样式信息的API 2. Document的树结构 在了解Document文档对象模型之前&#xff0c;我们先了解Dom的树结构 …

使用scp命令从本地往服务器传输文件失败

解决办法&#xff1a; 找到这个文件&#xff0c;打开&#xff0c;将里面的服务器ip对应的一行数据删掉即可。

(c语言+数据结构链表)项目:贪吃蛇

目录 1.项目背景 2.游戏效果演⽰ 3. ⽬标 4. 技术要点 5. Win32 API介绍 5.1 Win32 API 5.2 控制台程序 5.3 控制台屏幕上的坐标COORD 5.4 GetStdHandle 5.5 GetConsoleCursorInfo 5.5.1 CONSOLE_CURSOR_INFO 5.6 SetConsoleCursorInfo 5.7 SetConsoleCursorPositi…

d3dcompiler47dll丢失怎么解决,详细介绍6种解决方案

在电脑使用过程中&#xff0c;我们可能会遇到各种问题&#xff0c;其中之一就是系统提示某个文件缺失。其中&#xff0c;d3dcompiler_47.dll是许多用户经常遇到的问题之一。这个文件是DirectX组件的一部分&#xff0c;如果缺失&#xff0c;可能会导致游戏或应用程序无法正常运行…

Qt/C++ 多线程同步机制详解及应用

在多线程编程中&#xff0c;线程之间共享资源可能会导致数据竞争和不一致的问题。因此&#xff0c;采用同步机制确保线程安全至关重要。在Qt/C中&#xff0c;常见的同步机制有&#xff1a;互斥锁&#xff08;QMutex、std::mutex&#xff09;、信号量&#xff08;QSemaphore&…

Ansbile-变量

文章目录 一、Ansible的常量&#xff08;内置的变量&#xff09;有哪些&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1…

vulnhub(11):derpnstink(hydra爆破用户名和密码、验证的文件上传)

端口 nmap主机发现 nmap -sn 192.168.159.120/24 ​ Nmap scan report for 192.168.159.120 Host is up (0.00020s latency). ​ 120是新出现的机器&#xff0c;他就是靶机 nmap端口扫描 nmap -Pn 192.168.159.120 -p- --min-rate 10000 -oA nmap/scan 扫描开放端口保存到 nma…

【论文笔记】Are Large Kernels Better Teacheres than Transformers for ConvNets

Abstract 本文提出蒸馏中小核ConvNet做学生时&#xff0c;与Transformer相比&#xff0c;大核ConvNet因其高效的卷积操作和紧凑的权重共享&#xff0c;使得其做教师效果更好&#xff0c;更适合资源受限的应用。 用蒸馏从Transformers蒸到小核ConvNet的效果并不好&#xff0c;原…

图的应用(关键路径)

基于你设计的带权有向无环图&#xff0c;写出所有合法的关键路径&#xff0c;并算出关键路径总长度 文字描述&#xff1a;关键路径总长度的现实意义是什么&#xff1f; 1.关键路径 总长度454316 2.现实意义 从源点到汇点的所有路径中&#xff0c;具有最大路径长度的路径称…

好的头戴式降噪耳机一定很贵吗?四款热门头戴耳机盘点及推荐!

在快节奏的现代生活中&#xff0c;噪音无处不在&#xff0c;它常常干扰着我们的工作、学习与休闲时光。而一款高性价比的降噪蓝牙耳机&#xff0c;就如同一个贴心的伙伴&#xff0c;能为我们营造出一片宁静的听觉空间。如今&#xff0c;耳机市场蓬勃发展&#xff0c;想要好的头…

Broadcast:Android中实现组件及进程间通信

目录 一&#xff0c;Broadcast和BroadcastReceiver 1&#xff0c;简介 2&#xff0c;广播使用 二&#xff0c;静态注册和动态注册 三&#xff0c;无序广播和有序广播 1&#xff0c;有序广播的使用 2&#xff0c;有序广播的截断 3&#xff0c;有序广播的信息传递 四&am…

如何在GitHub上克隆仓库:HTTPS、SSH和GitHub CLI的区别

GitHub是开发者的天堂&#xff0c;提供了丰富的工具和功能来管理代码和项目。在克隆GitHub仓库时&#xff0c;你可能会遇到三种常见的方法&#xff1a;HTTPS、SSH和GitHub CLI。每种方法都有其独特的优势和适用场景。本文将深入探讨这三种克隆方式的区别&#xff0c;帮助你选择…

C++--类的实例化

一、实例化的概念 用类类型在屋里内存中创建对象的过程&#xff0c;称为类实例化出对象 类是对对象进行一种抽象描述&#xff0c;是一个模型一样的东西&#xff0c;限定了类有哪些成员变量&#xff0c;这些成员变量只是声明&#xff0c;没有分配空间&#xff0c;用类实例化出…

java项目之编程训练系统源码(springboot)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的编程训练系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 编程训练系统的主要使用者管…