当前位置： 首页 > news >正文

Java容器类详解(Collection与Map，含多线程性能对比)

news 来源：原创 2023/6/8 0:11:27

概览

Java里的容器类，主要包括Collection和Map接口下的类，具体如下：

Collection细分为Set、List、Queue，无key，直接存储数据元素。而Map不但存储数据元素，还有key进行映射。

List

List是一个有序集合，主要有：ArrayList、LinkedList、Vector、CopyOnWriteArrayList，它们的各自特点如下：

ArrayList

底层是数组，内部维护Object[]。它线程不安全，查询快，但增删慢，物理内存是连续的。线程不安全是若多线程同时给线程添加数据，可能出现多个线程读取到同一个副本然后都将添加后的结果给主内存中的ArrayList造成其中一个或多个元素被覆盖丢失！查询是直接指针偏移获取数据，不需要一个一个对比查找数据。但增加或删除时元素可能需要移动，这个代价比较大，所以增删慢，其实增加的话若不扩容，也比较快的。JDK8中ArrayList默认初始容器大小为10，不够后基本按grow方法里的int newCapacity = oldCapacity + (oldCapacity >> 1);即按原来的1.5倍来扩容。

LinkedList

底层用的数据结构是链表，内部维护Node<E>节点。它线程不安全，查询慢，增删快，物理内存可以不连续。它只有get(index)方法，即只按节点索引值查找，依然要经过前面的节点找到元素，索引查找比ArrayList慢，增删快，只需修改要插入或删除元素前后指针即可，不需扩容什么的。

Vector

底层是数组，内部维护Object[]。它相当于线程安全的ArrayList。里面addElement、get、size等方法都加上了synchronized关键字修饰。一般扩容是双倍扩容。查询和增删都较慢。

CopyOnWriteArrayList

底层是数组，维护一个Object[]，加入了重入锁，是线程安全的。注意：它添加元素很慢！因为它每调用一个add方法，都要锁住复制当前数组加上新元素成立新数组！即当用add方法添加一个元素立即调用查询方法有可能是查不到这个元素的！有延迟，但能保证线程安全，即添加的元素不会丢失。这个只能用于查询非常多，增删非常少的情况，建议用addAll方法不建议用add方法。

多线程下性能对比

这里主要对比Vector与CopyOnWriteArrayList的写性能，读就不测了，毕竟一个加了锁一个没加锁差距明显，具体代码如下：

package com.longqi.boottest.collection;

import org.apache.commons.lang3.RandomStringUtils;

import java.util.List;
import java.util.Vector;
import java.util.concurrent.*;

/**
 * @author LongQi
 * @projectName boot-integration
 * @description: TODO
 * @date 2023/3/23 10:31
 */
public class ListThreadApplication {

    public static void main(String[] args) {
        List<String> vector = new Vector<>();
        List<String> cowArr = new CopyOnWriteArrayList<>();
        int size = 10;
        int len = 500;
        String data = RandomStringUtils.randomAlphanumeric(len);
        vector.add(data);
        cowArr.add(data);
        CountDownLatch vectorLatch = new CountDownLatch(4);
        Runnable vectorRun = new Runnable() {
            @Override
            public void run() {
                Long start = System.nanoTime();
                for(int i=0;i<size;i++){
                    vector.add(data);
                }
                Long end = System.nanoTime();
                System.out.println("vector时间花费："+(end-start));
                vectorLatch.countDown();
            }
        };
        CountDownLatch cowArrLatch = new CountDownLatch(4);
        Runnable cowArrayRun = new Runnable() {
            @Override
            public void run() {
                Long start = System.nanoTime();
                for(int i=0;i<size;i++){
                    cowArr.add(data);
                }
                Long end = System.nanoTime();
                System.out.println("cowArr时间花费："+(end-start));
                cowArrLatch.countDown();
            }
        };
        ThreadPoolExecutor executor = new ThreadPoolExecutor(10,15,1, TimeUnit.SECONDS,new LinkedBlockingDeque<>());
        executor.submit(vectorRun);
        executor.submit(vectorRun);
        executor.submit(vectorRun);
        executor.submit(vectorRun);
        try{
            vectorLatch.await(5,TimeUnit.SECONDS);
        }catch (Exception e){
            e.printStackTrace();
        }
        executor.submit(cowArrayRun);
        executor.submit(cowArrayRun);
        executor.submit(cowArrayRun);
        executor.submit(cowArrayRun);
        try{
            cowArrLatch.await(5,TimeUnit.SECONDS);
        }catch (Exception e){
            e.printStackTrace();
        }
        System.out.println("vector.size:"+vector.size());
        System.out.println("cowArr.size:"+cowArr.size());
    }
}

1、第一次新增不计时间，4个线程，每个线程添加10条数据，结果如下：

多次测试结果与上面类似：在数十条数据量级下，CopyOnWriteArrayList性能比Vector写性能更好。

2、第一次新增不计时间，4个线程，每个线程添加100条数据，结果如下：

多次测试结果与上面类似：在数百条数据量级下，Vector性能比CopyOnWriteArrayList写性能更好。

后续数量越大，Vector写性能比CopyOnWriteArrayList越好，毕竟元素越多，复制成本比锁的成本越大。

总结

一般的业务用ArrayList就够了，毕竟大部分场景是查询出数据库的数据，对数据查询进行属性值的一些调整再返回，很少查询出了数据还做增删的。若对于计算类业务，需要对数据做大量增删的，则可以使用linkedList。若是多个线程要使用List，若是大量读以及少量写，则建议使用CopyOnWriteArrayList，若涉及到较多或大量写，建议使用Vector。

Set

Set大部分是无序集合，一般只能添加不存在的元素，不能添加两个相同元素，主要有：HashSet、TreeSet、ConcurrentSkipListSet、CopyOnWriteArraySet，它们的各自特点如下：

HashSet

底层是HashMa的Key，内部维护HashMap，底层数据结构是Hash表+链表/红黑树。它线程不安全，查询以及增删都不错，Hash的物理内存是连续的，Node[]数组实现，链表/红黑树地址不连续。由于线程不安全，则多个线程同时修改HashSet时会造成数据对不上！获取值局势先根据key通过hash算法查找数组下标，然后链表或二叉树查询有没有该值 。Set实例化时只是调用HashMap的实例化方法。初始化大小默认16，建议大小为（需要存储元素/负载因子）+1，HashMap默认负载因子0.75。

TreeSet

底层直接使用TreeMap的key，内部维护TreeMap，底层数据结构为红黑树。它不是线程安全，查询以及增删都不错，但速度对比HashMap要慢些。不过TreeSet要求元素实现比较接口，可以用于排序，所以TreeSet适用于排序元素遍历。由于底层直接是自平衡的红黑树，所以它无需优化容量等！

ConcurrentSkipListSet

底层直接使用ConcurrentSkipListMap的key。数据结构为跳表（比寻常链表多了个索引）。它是线程安全、查询增删也不错，速度甚至和红黑树相当（索引基本是二分的）。但就是会耗费额外的空间来维护索引。

CopyOnWriteArraySet

底层直接使用CopyOnWriteArrayList来存储数据，它是有序的(不会打乱添加元素的顺序)，除了新增其它方法都调用list原有方法，新增方法调用它自己的addIfAbsent()/addAllAbsent()方法，即元素不存在才进行添加。

多线程下性能对比

这里主要对比ConcurrentSkipListSet与CopyOnWriteArraySet的写性能，读就不测了，毕竟一个加了锁一个没加锁差距明显，具体代码如下：

package com.longqi.boottest.collection;

import org.apache.commons.lang3.RandomStringUtils;

import java.util.Collection;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.CopyOnWriteArraySet;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;

/**
 * @author LongQi
 * @projectName boot-integration
 * @description: TODO
 * @date 2023/3/23 10:31
 */
public class ListThreadApplication {

    public static void main(String[] args) throws Exception {
        // 线程数
        int count = 4;
        // 每个线程添加元素个数
        int size = 10;
        // 字符串长度
        int len = 50;
        ConcurrentSkipListSet<String> skipSet = new ConcurrentSkipListSet<>();
        CopyOnWriteArraySet<String> copySet = new CopyOnWriteArraySet<>();
        CountDownLatch latch = new CountDownLatch(count);
        test(skipSet,"skipSet",latch,count,size,len);
        latch.await(600,TimeUnit.SECONDS);
        latch = new CountDownLatch(count);
        test(copySet,"copySet",latch,count,size,len);
        latch.await(600,TimeUnit.SECONDS);
        System.out.println("============ 避免类加载影响，测试结果以下面为准 ============");
        latch = new CountDownLatch(count);
        test(skipSet,"skipSet",latch,count,size,len);
        latch.await(600,TimeUnit.SECONDS);
        latch = new CountDownLatch(count);
        test(copySet,"copySet",latch,count,size,len);
        latch.await(600,TimeUnit.SECONDS);
        System.out.println("skipSet.size:"+skipSet.size());
        System.out.println("copySet.size:"+copySet.size());
    }

    public static void test(Collection<String> collection,String collectName,CountDownLatch latch,int count,int size,int len){
        Runnable run = new Runnable() {
            @Override
            public void run() {
                Long start = System.nanoTime();
                for(int i=0;i<size;i++){
                    collection.add(RandomStringUtils.randomAlphanumeric(len));
                }
                Long end = System.nanoTime();
                System.out.println(collectName+"时间花费："+(end-start));
                latch.countDown();
            }
        };
        for(int i=0;i<count;i++){
            new Thread(run).start();
        }
    }

}

  1. 第一次运行方法新增不计时间，4个线程，每个线程添加10条数据，结果如下：

多次测试结果两者互有胜负：在数十条数据量级下，ConcurrentSkipListSet和CopyOnWriteArraySet写性能相当。

  1. 第一次运行方法新增不计时间，4个线程，每个线程添加100条数据，结果如下：

总体来讲，ConcurrentSkipListSet胜多败少，它受添加的元素影响较大，遇到调整较多索引的情况，耗时会比CopyOnWriteArraySet多。

  1. 第一次运行方法新增不计时间，4个线程，每个线程添加1000条数据，结果如下：

这里ConcurrentSkipListSe就完胜了，越大于1000数量级，ConcurrentSkipListSe相等对于CopyOnWriteArraySet耗时越少。

总结

一般的业务用HashSet就够了，需要保证元素去重有序则可以用LinkedHashSet。若是多个线程要使用Set，建议直接用ConcurrentSkipListSet，除非读非常多以及存储的元素少且写入很少的场景才选择CopyOnWriteArraySet。

Queue

队列分为阻塞和非阻塞队列。阻塞队列满了新增元素或队列为空获取数据则会阻塞当前线程，直到队列有空余或有元素。而非阻塞队列不会阻塞当前线程。它有add()和offer()方法添加元素到队列尾部，有remove()和poll()方法返回并删除队头元素，有peek()和element()方法返回但不删除队头元素，它们不同之处在于队列空或满的异常处理。

linkedList

linkedList底层是一个Node链表，它最终也是实现了Queue接口，是个非阻塞队列，add()和offer()方法可以添加元素，它并有容量限制，但由于size是int类型，因此它可以存int最大值个元素。poll()等方法可以返回头元素，当无头元素会返回null，不会阻塞线程。由于没有锁或cas之类的，所以它是线程不安全的。

ConcurrentLinkedQueue

底层维护一个Node链表。它是非阻塞队列。添加等方法用和cas比较添加或删除。线程获取元素时若队列无元素则会直接返回null，不会阻塞线程执行。它的size()方法需要遍历元素，很慢，判断有无元素最好使用isEmpty()方法。该队列无锁，通常并发性能比LinkedBlockingQueue好，该队列不允许添加null元素。

LinkedBlockingQueue

底层维护一个Node链表。有两把锁以及两个条件。一把用于入队、一把用于出队。由于两把锁避免了出队入队的竞争锁，所以在入队和出队都高并发下性能比ArrayBlockingQueue高很多。由于采用链表，容量几乎无限，为整形最大值（capacity为int类型）。该队列是阻塞队列，若线程获取元素时若队列无元素则会阻塞该线程，线程一直到获取元素后才继续执行。

ArrayBlockingQueue

底层维护一个Object[]数组。有一把锁和两个条件（不为空或不是已满）。入队与出队都用同一把锁，由于只有一把锁，所以只有当入队高并发或只有出队高并发的情况下性能才高，当入队元素大于数组时，需扩容，所以一般先估算指定好队列容量。

SynchronousQueue

底层维护一个transfer点。可以看做容量为1阻塞队列。

PriorityQueue

底层维护一个Object[]数组。线程不安全。该队列即可以让元素自然添加顺序排序，也可以让元素按指定顺序排序，需要指定比较器。

PriorityBlockingQueue

底层维护一个Object数组。它是PriorityQueue的线程安全版本，会阻塞线程。

总结

由于这些队列结构简单，就不做测试了，基本可以看出性能，基本是基于链表的队列的写速度大于基于数组的队列速度，而且只返回头元素，读速度都一样。所以，若不需要考虑并发，不需要给队列排序，用LinkedList即可，若需要排序则用PriorityQueue；若需要考虑并发，则需要建议使用ConcurrentLinkedQueue(非阻塞)，LinkedBlockingQueue(阻塞)、PriorityBlockingQueue(可排序)。

Map

Map是键值对集合，能够准确根据key获取数据value。主要有：HashMap、TreeMap、ConcurrentHashMap、HashTable，它们的各自特点如下：

HashMap

底层是HashMa的Key，内部维护HashMap，底层数据结构是Hash表+链表/红黑树。它线程不安全，查询以及增删都不错，Hash的物理内存是连续的，Node[]数组实现，链表/红黑树地址不连续。由于线程不安全，则多个线程同时修改HashSet时会造成数据对不上！获取值局势先根据key通过hash算法查找数组下标，然后链表或二叉树查询有没有该值 。Set实例化时只是调用HashMap的实例化方法。初始化大小默认16，建议大小为（需要存储元素/负载因子）+1，HashMap默认负载因子0.75。

TreeMap

底层直接使用TreeMap的key，内部维护TreeMap，底层数据结构为红黑树。它不是线程安全，查询以及增删都不错，但速度对比HashMap要慢些。不过TreeSet要求元素实现比较接口，可以用于排序，所以TreeSet适用于排序元素遍历。由于底层直接是自平衡的红黑树。

ConcurrentHashMap

HashMap的线程安全版本，Jdk8用了cas+synchronized+LockSupport来实现线程安全。相对于HashTable，它的锁更轻量级，只锁住需要修改的那个node。

HashTable

底层也是用Hash表存储数据，线程安全，但所有方法加了synchronized来保证线程安全。锁住了整个表，put()和get()以及size()方法都是加了synchronized。增删查询都慢。

总结

这里就不测试对比速度了，很显然，ConcurrentHashMap的性能比HashTable好。不是多线程场景直接使用HashMap即可，是多线程场景使用ConcurrentHashMap即可。

相关文章：

  • 项目文件的组织方式
  • 系统集成路由器OSPF动态、综合路由配置
  • windows搭建ftp服务器、抓取虚拟机数据包、局域网流量监听
  • 数值分析——求积公式
  • php模拟文件上传使用curl向远程服务器上传文件,php将图片转成二进制文件进行请求接口上传
  • 【大数据之Hadoop】三、HDFS概述及组成框架
  • MapReduce数据倾斜产生的原因及其解决方案
  • docker开启的Mysql修改时区
  • 完成首选项
  • 【C语言进阶】自定义类型之结构体，枚举和联合
  • springboot校友社交系统
  • 【Python算法】简单深搜练习
  • ASO优化之应用商店中的A/B测试——改良版
  • Github隐藏功能显示自己的README，个人化你的Github主页
  • 什么是 SSL 证书管理
  • java中如何实现全文搜索
  • Eigen中的SparseMatrix（稀疏矩阵）元素的快速插入
  • 第十四届蓝桥杯三月真题刷题训练——第 21 天
  • JavaScript到底如何存储数据?
  • 结构体详解
  • 《微信小程序案例9》小程序登录流程
  • UNI-APP安卓本地打包详细教程（保姆级）
  • Flutter 实现你所谓的弹窗 (对话框)
  • uniapp实现公众号H5、小程序和App微信授权登录功能
  • Android 控件描边、加阴影
  • 收藏这份Android Framework开发入门指南，带你步入Android系统开发的殿堂
  • Swift5中String、数组相互转换
  • 一次搞懂Java如何调用Kotlin的高级特性
  • Mac使用Python接入东方财富量化接口Choice，调试与获取数据
  • Android Bluetooth（一）——蓝牙的开启和搜索