萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

Java的集合类(容器)

发表于 2021-06-19 | 分类于 Java SE | 0 | 阅读次数 262

四大集合接口

Java中的集合类主要由Collection和Map这两个接口派生而出,其中Collection接口又派生出三个子接口,分别是Set、List、Queue。所有的Java集合类,都是Set、List、Queue、Map这四个接口的实现类,这四个接口将集合分成了四大类:

  • Set代表无序的,元素不可重复的集合
  • List代表有序的,元素可以重复的集合
  • Queue代表先进先出(FIFO)的队列
  • Map代表具有映射关系(key-value)的集合

这些接口拥有众多的实现类,其中最常用的实现类有HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。

集合类的继承树

Collection体系继承树:

Collection

Map体系继承树:

Map

线程安全和线程不安全

线程不安全的集合类:HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap
它们虽然线程不安全,但是性能很高。如果需要使用线程安全的集合类,则可以使用Collections工具类提供的synchronizedXxx()方法,将这些集合类包装成线程安全的集合类。

线程安全集合类:Vector、Hashtable
它们比较古老,而且性能很差。如果要使用线程安全的集合类,建议将线程不安全的集合类包装成线程安全集合类的方式,而不是直接使用这些古老的API。

从Java5开始,Java在java.util.concurrent包下提供了大量支持高效并发访问的集合类,它们既能包装良好的访问性能,有能包装线程安全。这些集合类可以分为两部分,它们的特征如下:

  • 以Concurrent开头的集合类:
    以Concurrent开头的集合类代表了支持并发访问的集合,它们可以支持多个线程并发写入访问,这些写入线程的所有操作都是线程安全的,但读取操作不必锁定。以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合,因此在并发写入时有较好的性能。
  • 以CopyOnWrite开头的集合类:
    以CopyOnWrite开头的集合类采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时,线程将会直接读取集合本身,无须加锁与阻塞。当线程对此类集合执行写入操作时,集合会在底层复制一份新的数组,接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作,因此它是线程安全的。

1 Map集合

1.1 Map的常用实现类

  1. HashMap
    应用场景:不需要排序、不要求线程安全(如果需要线程安全则用ConcurrentHashMap,它的性能好于Hashtable)
    特点:性能最好的Map

  2. LinkedHashMap
    应用场景:需要按插入顺序排序、不要求线程安全

  3. TreeMap
    应用场景:需要将key按自然顺序排列甚至是自定义顺序排列、线程不安全

  4. ConcurrentHashMap
    应用场景:线程安全、不需要排序

  • 补充:LinkedHashMap、TreeMap如果需要线程安全可用Collections工具类将两者包装成线程安全的Map。

1.2 Map的put过程

HashMap是最经典的Map实现,下面以它的视角描述put的过程:

  1. 首次扩容:
    先判断数组是否为空,若数组为空则进行第一次扩容(resize)
  2. 计算索引:
    通过hash算法,计算键值对在数组中的索引
  3. 插入数据:
    如果当前位置元素为空,则直接插入数据
    如果当前位置元素非空,且key已存在,则直接覆盖其value
    如果当前位置元素非空,且key不存在,则将数据链到链表末端
    若链表长度达到8,则将链表转换成红黑树,并将数据插入树中
  4. 再次扩容:
    如果数组中元素个数(size)超过threshold,则再次进行扩容操作。

1.3 HashMap的特点

  1. HashMap是线程不安全的实现;
  2. HashMap可以使用null作为key或value。

1.4 jdk7和jdk8中HashMap的区别

  1. jdk7
    jdk7中的HashMap,是基于数组+链表来实现的,它的底层维护一个Entry数组。它会根据计算的hashCode将对应的KV键值对存储到该数组中,一旦发生hashCode冲突,那么就会将该KV键值对放到对应的已有元素的后面, 此时便形成了一个链表式的存储结构
    jdk7中HashMap的实现方案有一个明显的缺点,即当Hash冲突严重时,在桶上形成的链表会变得越来越长,这样在查询时的效率就会越来越低,其时间复杂度为O(N)。

  2. jdk8
    jdk8中的HashMap,是基于数组+链表+红黑树来实现的,它的底层维护一个Node数组。当链表的存储的数据个数大于等于8的时候,不再采用链表存储,而采用了红黑树存储结构。这么做主要是在查询的时间复杂度上进行优化,链表为O(N),而红黑树一直是O(logN),可以大大的提高查找性能。

1.5 HashMap底层的实现原理

HashMap基于hash算法,通过put方法和get方法存储和获取对象。
存储对象时,我们将K/V传给put方法时,它调用K的hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Factor则resize为原来的2倍)。
获取对象时,我们将K传给get方法,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals方法确定键值对。
如果发生碰撞的时候,HashMap通过链表将产生碰撞冲突的元素组织起来。在Java8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

1.6 HashMap实现线程安全的方法

  1. 直接使用Hashtable类(不推荐)
  2. 直接使用ConcurrentHashMap
  3. 使用Collections将HashMap包装成线程安全的Map

1.7 HashMap和HashTable的区别

  1. Hashtable是一个线程安全的Map实现,但HashMap是线程不安全的实现,所以HashMap比Hashtable的性能高一点。
  2. Hashtable不允许使用null作为key和value,如果试图把null值放进Hashtable中,将会引发空指针异常,但HashMap可以使用null作为key或value。

1.8 HashMap与ConcurrentHashMap的区别

HashMap是非线程安全的,这意味着不应该在多线程中对这些Map进行修改操作,否则会产生数据不一致的问题,甚至还会因为并发插入元素而导致链表成环,这样在查找时就会发生死循环,影响到整个应用程序。

Collections工具类可以将一个Map转换成线程安全的实现,其实也就是通过一个包装类,然后把所有功能都委托给传入的Map,而包装类是基于synchronized关键字来保证线程安全的(Hashtable也是基于synchronized关键字),底层使用的是互斥锁,性能与吞吐量比较低。

ConcurrentHashMap的实现细节远没有这么简单,因此性能也要高上许多。它没有使用一个全局锁来锁住自己,而是采用了减少锁粒度的方法,尽量减少因为竞争锁而导致的阻塞与冲突,而且ConcurrentHashMap的检索操作是不需要锁的。

1.9 ConcurrentHashMap是怎么实现的

  1. jdk1.7

    在jdk1.7中,ConcurrentHashMap是由Segment数据结构和HashEntry数组结构构成,采取分段锁来保证安全性。Segment是ReentrantLock重入锁,在ConcurrentHashMap中扮演锁的角色,HashEntry则用于存储键值对数据。一个 ConcurrentHashMap里包含一个Segment数组,一个Segment里包含一个HashEntry 数组,Segment的结构和HashMap类似,是一个数组和链表结构。
    image.png

  2. jdk1.8

    jdk1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在jdk1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。
    image.png

1.10 对LinkedHashMap的理解

LinkedHashMap使用双向链表来维护key-value对的顺序(其实只需要考虑key的顺序),该链表负责维护Map的迭代顺序,迭代顺序与key-value对的插入顺序保持一致。

LinkedHashMap可以避免对HashMap、Hashtable里的key-value对进行排序(只要插入key-value对时保持顺序即可),同时又可避免使用TreeMap所增加的成本。

LinkedHashMap需要维护元素的插入顺序,因此性能略低于HashMap的性能。但因为它以链表来维护内部顺序,所以在迭代访问Map里的全部元素时将有较好的性能。

1.11 LinkedHashMap的底层原理

LinkedHashMap继承于HashMap,它在HashMap的基础上,通过维护一条双向链表,解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表重写了部分方法。

1.12 TreeMap的底层原理

TreeMap基于红黑树(Red-Black tree)实现。映射根据其键的自然顺序进行排序,或者根据创建映射时提供的Comparator进行排序,具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法,它的时间复杂度是log(N)。

TreeMap包含几个重要的成员变量:root、size、comparator。其中root是红黑树的根节点。它是Entry类型,Entry是红黑树的节点,它包含了红黑树的6个基本组成:key、value、left、right、parent和color。Entry节点根据根据Key排序,包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。

1.13 Map和Set有什么区别

Set代表无序的,元素不可重复的集合;
Map代表具有映射关系(key-value)的集合,其所有的key是一个Set集合,即key无序且不能重复。

2 List集合

2.1 List和Set有什么区别

Set代表无序的,元素不可重复的集合;
List代表有序的,元素可以重复的集合。

2.2 ArrayList和LinkedList有什么区别

  1. ArrayList的实现是基于数组,LinkedList的实现是基于双向链表;
  2. 对于随机访问ArrayList要优于LinkedList,ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问,而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起,查找某个元素的时间复杂度是O(N);
  3. 对于插入和删除操作,LinkedList要优于ArrayList,因为当元素被添加到LinkedList任意位置的时候,不需要像ArrayList那样重新计算大小或者是更新索引;
  4. LinkedList比ArrayList更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。

2.3 线程安全的List

Vector

Vector是比较古老的API,虽然保证了线程安全,但是由于效率低一般不建议使用。

Collections.SynchronizedList

SynchronizedList是Collections的内部类,Collections提供了synchronizedList方法,可以将一个线程不安全的List包装成线程安全的List,SynchronizedList。它比Vector有更好的扩展性和兼容性,但是它所有的方法都带有同步锁,也不是性能最优的List。

CopyOnWriteArrayList

CopyOnWriteArrayList是Java1.5在java.util.concurrent包下增加的类,它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时,线程将会直接读取集合本身,无须加锁与阻塞。当线程对此类集合执行写入操作时,集合会在底层复制一份新的数组,接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作,因此它是线程安全的。在所有线程安全的List中,它是性能最优的方案。

2.4 ArrayList的数据结构

ArrayList的底层是用数组来实现的,默认第一次插入元素时创建大小为10的数组,超出限制时会增加50%的容量,并且数据以System.arraycopy()复制到新的数组,因此最好能给出数组大小的预估值。

按数组下标访问元素的性能很高,这是数组的基本优势。直接在数组末尾加入元素的性能也高,但如果按下标插入、删除元素,则要用System.arraycopy()来移动部分受影响的元素,性能就变差了,这是基本劣势。

2.5 CopyOnWriteArrayList的原理

CopyOnWriteArrayList是Java并发包里提供的并发类,简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样,在写操作时会复制一份新的List,在新的List上完成写操作,然后再将原引用指向新的List。这样就保证了写操作的线程安全。

CopyOnWriteArrayList允许线程并发访问读操作,这个时候是没有加锁限制的,性能较高。而写操作的时候,则首先将容器复制一份,然后在新的副本上执行写操作,这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意,在上锁执行写操作的过程中,如果有需要读操作,会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

  • 优点:读操作性能很高,因为无需任何同步措施,比较适用于读多写少的并发场景。在遍历传统的List时,若中途有别的线程对其进行修改,则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想,遍历和修改操作分别作用在不同的List容器,所以在使用迭代器进行遍历时候,也就不会抛出ConcurrentModificationException异常了。
  • 缺点:一是内存占用问题,毕竟每次执行写操作都要将原容器拷贝一份,数据量大时,对内存压力较大,可能会引起频繁GC。二是无法保证实时性,Vector对于读写操作均加锁同步,可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因,写和读分别作用在新老不同容器上,在写操作执行过程中,读不会阻塞但读取到的却是老容器的数据。

3 Set容器

3.1 HashSet的底层结构

HashSet是基于HashMap实现的,默认构造方法是构建一个初始容量为16,负载因子为0.75的HashMap。它封装了一个HashMap对象来存储所有的集合元素,所有放入 HashSet中的集合元素实际上由HashMap的key来保存,而HashMap的value则存储了一个PRESENT,它是一个静态的Object对象。

3.2 TreeSet和HashSet的区别

HashSet、TreeSet中的元素都是不能重复的,并且它们都是线程不安全的,二者的区别是:

  1. HashSet中的元素可以是null,但TreeSet中的元素不能是null;
  2. HashSet不能保证元素的排列顺序,而TreeSet支持自然排序、定制排序两种排序的方式;
  3. HashSet底层是采用哈希表实现的,而TreeSet底层是采用红黑树实现的。

4 Queue容器

4.1 BlockingQueue中的方法

为了应对不同的业务场景,BlockingQueue 提供了4 组不同的方法用于插入、移除以及对队列中的元素进行检查。如果请求的操作不能得到立即执行的话,每组方法的表现是不同的。这些方法如下:

抛异常特定值阻塞超时
插入add(e)offer(e)put(e)offer(e, time, unit)
移植remove()poll()take()poll(time, unit)
检查element()peek()

四组不同的行为方式含义如下:

  • 抛异常:如果操作无法立即执行,则抛一个异常;
  • 特定值:如果操作无法立即执行,则返回一个特定的值(一般是 true / false)。
  • 阻塞:如果操作无法立即执行,则该方法调用将会发生阻塞,直到能够执行;
  • 超时:如果操作无法立即执行,则该方法调用将会发生阻塞,直到能够执行。但等待时间不会超过给定值,并返回一个特定值以告知该操作是否成功(典型的是true / false)。

4.2 BlockingQueue的实现

BlockingQueue是一个接口,它的实现类有ArrayBlockingQueue、DelayQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。它们的区别主要体现在存储结构上或对元素操作上的不同,但是对于put与take操作的原理是类似的。下面以ArrayBlockingQueue为例,来说明BlockingQueue的实现原理。

首先看一下ArrayBlockingQueue的构造方法,它初始化了put和take方法中用到的关键成员变量,这两个变量的类型分别是ReentrantLock和Condition。ReentrantLock是AbstractQueuedSynchronizer(AQS)的子类,它的newCondition方法返回的Condition实例,是定义在AQS类内部的ConditionObject类,该类可以直接调用AQS相关的方法。

/** ArrayBlockingQueue的构造器 **/
public ArrayBlockingQueue(int capacity, boolean fair) {
	if (capacity <= 0)
		throw new IllegalArgumentException();
	this.items = new Object[capacity];
	lock = new ReentrantLock(fair);
	notEmpty = lock.newCondition();
	notFull = lock.newCondition();
}

put方法会在队列末尾添加元素,如果队列已经满了,无法添加元素的话,就一直阻塞等待到可以加入为止。方法的源码如下所示。我们会发现put方法使用了wait/notify的机制。与一般生产者-消费者的实现方式不同,同步队列使用ReentrantLock和Condition相结合的机制,即先获得锁,再等待,而不是synchronized和wait的机制。

/** put方法源码:注释是我根据自己的理解加的,如有错误欢迎指正 **/
public void put(E e) throws InterruptedException {
	checkNotNull(e);  // 检查插入的元素是否为空
	final ReentrantLock lock = this.lock;  // 获取锁
	lock.lockInterruptibly();  // 上锁
	try {
		while (count == items.length)  // 队列满
			notFull.await();  // 等待
		enqueue(e);  // 入队
	} finally {
		lock.unlock();  // 释放锁
	}
}

再来看一下消费者调用的take方法,take方法在队列为空时会被阻塞,一直到阻塞队列加入了新的元素。

/** take方法源码:注释是我根据自己的理解加的,如有错误欢迎指正 **/
public E take() throws InterruptedException {
	final ReentrantLock lock = this.lock;  // 获取锁
	lock.lockInterruptibly();  // 上锁
	try {
		while (count == 0)  // 队列为空时
			notEmpty.await();  // 等待
		return dequeue();  // 出队
	} finally {
		lock.unlock();  // 释放锁
	}
}
# Java
力扣53题-最大子序和-动态规划题解
Java的枚举(enum)
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持