List and Set and Queue
今天总结一下其他集中容器
ArrayList
list应该是我们工作中最常用的数据结构了先来说说最常见的ArrayList ,一看名字就知道着家伙跟数组有关系。让我们来看看它的实现
我们在使用ArrayList的时候都是尽情的 塞! 塞! 塞! 可是数组是有固定的长度的,它是怎么实现的呢? 让我们看看它的add方法
我们简单来看看ArrayList是怎么扩容的吧 来看看grow方法
到此我们已经基本了解了ArrayList是如何实现一个可变长的数组。但是copy操作后原数组失去引用也不会被立即gc,会造成内存内有两份数组,假如原数组过长,扩容将带来灾难。
让我们看看有哪些线程安全的List 首先Vector这货跟Hashtable 一样简单粗暴的使用synchorized 关键字同步方法来解决线程安全问题 。
CopyOnWriteArrayList
这显然不是我们想要的答案,来让我们看看j.u.c包下有什么宝贝。CopyOnWriteArrayList,就是它了。让我们直接上代码:
再来看看get方法
就一行代码但是我们应该能猜出来就是简单的通过索引获取元素。但是为什么它能高并发的读呢 ?
我们来看CopyOnWrite 这是一种解决并发的机制。实现方案很简单就跟字面意思一样每次写操作就Copy一份。读操作仍读过去的旧值(通过volatile 保证了可见性),待更新完成后将指针指向写入新元素的数组。使用一种无锁方案实现了并发。
(结论:从刚才的描述中我们明显感觉都这个思路跟读写锁有些类似,是一种对读写锁的升级思想,适合大量读少量写的情况下使用)
Set
Set就是所谓的集合二个特性:元素不重复,内部元素无序(有序其实可认为是一种特殊的无序)
HashSet使用HashMap来实现 ,CopyOnWriteArraySet 就使用我们刚刚讲过的CopyOnWriteArrayList来实现。
Queue
Queue是我们今天介绍的最后一种容器
ArrayBlockingQueue
我们从名字上能看出这是个用数组实现的阻塞队列,让我们看一下它是如何实现的上代码
让我们看看ArrayBlockingQueue 是如何实现把数组变成队列
我们先来看看它的非阻塞方法(poll,peek,offer)
我们看看enqueue 和 dequeue 怎么实现的循环数组
poll与peek的代码都比较简单就不再废话了。
然后让我们来看看阻塞的(put/take)方法
ArrayBlockingQueue我们就简单分析到这。
LinkedBlocingQueue
从属性上我们能看出LinkedBlockingQueue的结构是链表 ,并且采用了putLock 和 takeLock 两把锁,因为可以同时进行读写所以需要使用保证原子性的AtomicInteger count 。下面我们来看看它的非阻塞方法
offer方法:
poll 和 peek 代码类似于ArrayBlockingQueue对比来看
下面我们来看一下阻塞的put
阻塞的take方法
LinkedBolockingQueue我们就分析到这里,总体来说从性能上ArrayBlockingQueue要优越于LinkedBlockingQueue 主要由于创建新Node节点问题。但是LinkedBlockingQueue的吞吐量大于ArrayBlockingQueue
ConcurrentLinkedQueue (非阻塞)
我们的这个ConcurrentLinkedQueue也在并发场景下使用,它使用CAS 无锁编程,链表结构来实现,我们来简单看一下它的属性
因为是非阻塞的我们来看看它的offer 和 poll 方法
ConcurrentLinkedQueue就暂时总结到这里 还有一些Dquque 双向队列,SynchronousQuue容量为0的队列,还有带有优先级的队列 PriorityQueue等,原理实现与本篇有介绍的队列有很多相通之处,相信读完这篇的小伙伴可以自行去探寻其中的奥秘。
总结就到这里欢迎大家指正问题 !! 与君共勉