目录

一. 概述

二. 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;
    }

    @Override
    public 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);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public 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;
    }

    @Override
    public 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);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public 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;
    }

    @Override
    public int compareTo(User o) {
        return Integer.compare(this.age, o.age);
    }

    @Override
    public 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);
    }

    @Override
    public 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;
    }

    @Override
    public 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;
    }

    @Override
    public int compareTo(MyUser user) {
        return Integer.compare(this.age,user.getAge());
    }

    @Override
    public 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");
        //遍历HashMap
        for (String key : map.keySet()) {
            System.out.println(key + " : " + map.get(key));
        }
        System.out.println("======================================");
        //遍历EntrySet
        System.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;
    }
    @Override
    public 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;
    }
    @Override
    public 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> {
    @Override
    public 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.创建一个按照插入顺序排序的 LinkedHashMap
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        map.put("Three", 3);
        // 遍历 LinkedHashMap
        for (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");
        // 遍历 Hashtable
        for (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");
        // 遍历 ConcurrentHashMap
        for (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);
        }
    }
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部