2018-06-13 关于Java集合的小抄

原文地址: http://calvin1978.blogcn.com/articles/collection.html

在尽可能短的篇幅里,将所有集合与并发集合的特征、实现方式、性能捋一遍。适合所有"精通Java",其实还不那么自信的人阅读。

期望能不止用于面试时,平时选择数据结构,也能考虑一下其成本与效率,不要看着API合适就用了。

1.List

1.1 ArrayList

以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组。因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。

按数组下标访问元素-get(i)、set(i,e) 的性能很高,这是数组的基本优势。

如果按下标插入元素、删除元素-add(i,e)、 remove(i)、remove(e),则要用System.arraycopy()来复制移动部分受影响的元素,性能就变差了。

越是前面的元素,修改时要移动的元素越多。直接在数组末尾加入元素-常用的add(e),删除最后一个元素则无影响。

1.2 LinkedList

以双向链表实现。链表无容量限制,但双向链表本身使用了更多空间,每插入一个元素都要构造一个额外的Node对象,也需要额外的链表指针操作。

按下标访问元素-get(i)、set(i,e) 要悲剧的部分遍历链表将指针移动到位 (如果i>数组大小的一半,会从末尾移起)。

插入、删除元素时修改前后节点的指针即可,不再需要复制移动。但还是要部分遍历链表的指针才能移动到下标所指的位置。

只有在链表两头的操作-add()、addFirst()、removeLast()或用iterator()上的remove()倒能省掉指针的移动。

Apache Commons 有个TreeNodeList,里面是棵二叉树,可以快速移动指针到位。

1.3 CopyOnWriteArrayList

并发优化的ArrayList。基于不可变对象策略,在修改时先复制出一个数组快照来修改,改好了,再让内部指针指向新数组。

因为对快照的修改对读操作来说不可见,所以读读之间不互斥,读写之间也不互斥,只有写写之间要加锁互斥。但复制快照的成本昂贵,典型的适合读多写少的场景。

虽然增加了addIfAbsent(e)方法,会遍历数组来检查元素是否已存在,性能可想像的不会太好。

1.4 遗憾

无论哪种实现,按值返回下标contains(e), indexOf(e), remove(e) 都需遍历所有元素进行比较,性能可想像的不会太好。

没有按元素值排序的SortedList。

除了CopyOnWriteArrayList,再没有其他线程安全又并发优化的实现如ConcurrentLinkedList。凑合着用Set与Queue中的等价类时,会缺少一些List特有的方法如get(i)。如果更新频率较高,或数组较大时,还是得用Collections.synchronizedList(list),对所有操作用同一把锁来保证线程安全。


2.Map

2.1 HashMap

以Entry[]数组实现的哈希桶数组,用Key的哈希值取模桶数组的大小可得到数组下标。

插入元素时,如果两条Key落在同一个桶(比如哈希值1和17取模16后都属于第一个哈希桶),我们称之为哈希冲突。

JDK的做法是链表法,Entry用一个next属性实现多个Entry以单向链表存放。查找哈希值为17的key时,先定位到哈希桶,然后链表遍历桶里所有元素,逐个比较其Hash值然后key值。

在JDK8里,新增默认为8的阈值,当一个桶里的Entry超过閥值,就不以单向链表而以红黑树来存放以加快Key的查找速度。

当然,最好还是桶里只有一个元素,不用去比较。所以默认当Entry数量达到桶数量的75%时,哈希冲突已比较严重,就会成倍扩容桶数组,并重新分配所有原来的Entry。扩容成本不低,所以也最好有个预估值。

取模用与操作(hash & (arrayLength-1))会比较快,所以数组的大小永远是2的N次方, 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。

iterator()时顺着哈希桶数组来遍历,看起来是个乱序。

2.2 LinkedHashMap

扩展HashMap,每个Entry增加双向链表,号称是最占内存的数据结构。

支持iterator()时按Entry的插入顺序来排序(如果设置accessOrder属性为true,则所有读写访问都排序)。

插入时,Entry把自己加到Header Entry的前面去。如果所有读写访问都要排序,还要把前后Entry的before/after拼接起来以在链表中删除掉自己,所以此时读操作也是线程不安全的了。

2.3 TreeMap

以红黑树实现,红黑树又叫自平衡二叉树:

对于任一节点而言,其到叶节点的每一条路径都包含相同数目的黑结点。

上面的规定,使得树的层数不会差的太远,使得所有操作的复杂度不超过 O(lgn),但也使得插入,修改时要复杂的左旋右旋来保持树的平衡。

支持iterator()时按Key值排序,可按实现了Comparable接口的Key的升序排序,或由传入的Comparator控制。可想象的,在树上插入/删除元素的代价一定比HashMap的大。

支持SortedMap接口,如firstKey(),lastKey()取得最大最小的key,或sub(fromKey, toKey), tailMap(fromKey)剪取Map的某一段。

2.4 EnumMap

EnumMap的原理是,在构造函数里要传入枚举类,那它就构建一个与枚举的所有值等大的数组,按Enum. ordinal()下标来访问数组。性能与内存占用俱佳。

美中不足的是,因为要实现Map接口,而 V get(Object key)中key是Object而不是泛型K,所以安全起见,EnumMap每次访问都要先对Key进行类型判断,在JMC里录得不低的采样命中频率。

2.5 ConcurrentHashMap

并发优化的HashMap。

在JDK5里的经典设计,默认16把写锁(可以设置更多),有效分散了阻塞的概率。数据结构为Segment[],每个Segment一把锁。Segment里面才是哈希桶数组。Key先算出它在哪个Segment里,再去算它在哪个哈希桶里。

也没有读锁,因为put/remove动作是个原子动作(比如put的整个过程是一个对数组元素/Entry 指针的赋值操作),读操作不会看到一个更新动作的中间状态。

但在JDK8里,Segment[]的设计被抛弃了,改为精心设计的,只在需要锁的时候加锁。

支持ConcurrentMap接口,如putIfAbsent(key,value)与相反的replace(key,value)与以及实现CAS的replace(key, oldValue, newValue)。

2.6 ConcurrentSkipListMap

JDK6新增的并发优化的SortedMap,以SkipList结构实现。Concurrent包选用它是因为它支持基于CAS的无锁算法,而红黑树则没有好的无锁算法。

原理上,可以想象为多个链表组成的N层楼,其中的元素从稀疏到密集,每个元素有往右与往下的指针。从第一层楼开始遍历,如果右端的值比期望的大,那就往下走一层,继续往前走。

[图片上传失败...(image-75b56a-1528867373278)]

典型的空间换时间。每次插入,都要决定在哪几层插入,同时,要决定要不要多盖一层楼。

它的size()同样不能随便调,会遍历来统计。


3.Set

所有Set几乎都是内部用一个Map来实现, 因为Map里的KeySet就是一个Set,而value是假值,全部使用同一个Object即可。

Set的特征也继承了那些内部的Map实现的特征。

HashSet:内部是HashMap。

LinkedHashSet:内部是LinkedHashMap。

TreeSet:内部是TreeMap的SortedSet。

ConcurrentSkipListSet:内部是ConcurrentSkipListMap的并发优化的SortedSet。

CopyOnWriteArraySet:内部是CopyOnWriteArrayList的并发优化的Set,利用其addIfAbsent()方法实现元素去重,如前所述该方法的性能很一般。

好像少了个ConcurrentHashSet,本来也该有一个内部用ConcurrentHashMap的简单实现,但JDK偏偏没提供。Jetty就自己简单封了一个,Guava则直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap()) 实现。


4.Queue

Queue是在两端出入的List,所以也可以用数组或链表来实现。

4.1 普通队列

4.1.1 LinkedList

是的,以双向链表实现的LinkedList既是List,也是Queue。

4.1.2 ArrayDeque

以循环数组实现的双向Queue。大小是2的倍数,默认是16。

为了支持FIFO,即从数组尾压入元素(快),从数组头取出元素(超慢),就不能再使用普通ArrayList的实现了,改为使用循环数组。

有队头队尾两个下标:弹出元素时,队头下标递增;加入元素时,队尾下标递增。如果加入元素时已到数组空间的末尾,则将元素赋值到数组[0],同时队尾下标指向0,再插入下一个元素则赋值到数组[1],队尾下标指向1。如果队尾的下标追上队头,说明数组所有空间已用完,进行双倍的数组扩容。

4.1.3 PriorityQueue

用平衡二叉最小堆实现的优先级队列,不再是FIFO,而是按元素实现的Comparable接口或传入Comparator的比较结果来出队,数值越小,优先级越高,越先出队。但是注意其iterator()的返回不会排序。

平衡最小二叉堆,用一个简单的数组即可表达,可以快速寻址,没有指针什么的。最小的在queue[0] ,比如queue[4]的两个孩子,会在queue[24+1] 和 queue[2(4+1)],即queue[9]和queue[10]。

入队时,插入queue[size],然后二叉地往上比较调整堆。

出队时,弹出queue[0],然后把queque[size]拿出来二叉地往下比较调整堆。

初始大小为11,空间不够时自动50%扩容。

4.2 线程安全的队列

4.2.1 ConcurrentLinkedQueue/Deque

无界的并发优化的Queue,基于链表,实现了依赖于CAS的无锁算法。

ConcurrentLinkedQueue的结构是单向链表和head/tail两个指针,因为入队时需要修改队尾元素的next指针,以及修改tail指向新入队的元素两个CAS动作无法原子,所以需要的特殊的算法。

4.3 线程安全的阻塞队列

BlockingQueue,一来如果队列已空不用重复的查看是否有新数据而会阻塞在那里,二来队列的长度受限,用以保证生产者与消费者的速度不会相差太远。当入队时队列已满,或出队时队列已空,不同函数的效果见下表:

| | 立刻报异常 | 立刻返回布尔 | 阻塞等待 | 可设定等待时间 | | 入队 | add(e) | offer(e) | put(e) | offer(e, timeout, unit) | | 出队 | remove() | poll() | take() | poll(timeout, unit) | | 查看 | element() | peek() | 无 | 无 |

4.3.1 ArrayBlockingQueue

定长的并发优化的BlockingQueue,也是基于循环数组实现。有一把公共的锁与notFull、notEmpty两个Condition管理队列满或空时的阻塞状态。

4.3.2 LinkedBlockingQueue/Deque

可选定长的并发优化的BlockingQueue,基于链表实现,所以可以把长度设为Integer.MAX_VALUE成为无界无等待的。

利用链表的特征,分离了takeLock与putLock两把锁,继续用notEmpty、notFull管理队列满或空时的阻塞状态。

4.3.3 PriorityBlockingQueue

无界的PriorityQueue,也是基于数组存储的二叉堆(见前)。一把公共的锁实现线程安全。因为无界,空间不够时会自动扩容,所以入列时不会锁,出列为空时才会锁。

4.3.4 DelayQueue

内部包含一个PriorityQueue,同样是无界的,同样是出列时才会锁。一把公共的锁实现线程安全。元素需实现Delayed接口,每次调用时需返回当前离触发时间还有多久,小于0表示该触发了。

pull()时会用peek()查看队头的元素,检查是否到达触发时间。ScheduledThreadPoolExecutor用了类似的结构。

4.4 同步队列

SynchronousQueue同步队列本身无容量,放入元素时,比如等待元素被另一条线程的消费者取走再返回。JDK线程池里用它。

JDK7还有个LinkedTransferQueue,在普通线程安全的BlockingQueue的基础上,增加一个transfer(e) 函数,效果与SynchronousQueue一样。


5. 参考文档

在博客上,这个扫可乐钱的二维码总是存在的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

【Java数据结构学习笔记之三】Java数据结构与算法之队列(Queue)实现

  本篇是数据结构与算法的第三篇,本篇我们将来了解一下知识点: 队列的抽象数据类型 顺序队列的设计与实现 链式队列的设计与实现 队列应用的简单举例 优先队列的设...

3647
来自专栏开发 & 算法杂谈

Python多进程、多线程、协程

在Unix/Linux中系统内核提供了fork系统调用来创建进程,根据不同的返回值来判断当前进程是子进程还是父进程,C语言代码示例如下:

2755
来自专栏张善友的专栏

c# 元组Tuple

Tuple类型像一个口袋,在出门前可以把所需的任何东西一股脑地放在里面。您可以将钥匙、驾驶证、便笺簿和钢笔放在口袋里,您的口袋是存放各种东西的收集箱。C# 4....

1788
来自专栏java架构师

Stream篇(1)

最近在看一个写的很好的博客,为了加深记忆,把自认为重要的东西,一边看,一边记在这里 一、什么是流、字节序列、字节 一条河中有一条鱼游过,这条鱼就是一个字节,这个...

2837
来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

2206
来自专栏mukekeheart的iOS之旅

No.014 Longest Common Prefix

14. Longest Common Prefix Total Accepted: 112204 Total Submissions: 385070 Diffi...

2156
来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

712
来自专栏Stone的专栏

一篇文章精通 VLOOKUP 函数

相信不少人看到标题,立即嗤之以鼻,VLOOKUP 谁不会?是的,大家都会,但用的好的人不多。相信我,这篇文章一定可以算得上通俗易懂,又有深度的一篇文章,熟练掌握...

1060
来自专栏大史住在大前端

野生前端的数据结构基础练习(2)——队列

循环队列书中并没有提及,它是一种特殊的队列。简单理解就是将基本队列只当做存储结构,而使用front和rear两个指针分别代表队列的头和尾,实际对外表现的队列是f...

1203
来自专栏CSDN技术头条

【问底】王帅:深入PHP内核(一)——弱类型变量原理探究

PHP是一门简单而强大的语言,提供了很多Web适用的语言特性,其中就包括了变量弱类型,在弱类型机制下,你能够给一个变量赋任意类型的值。 PHP的执行...

2185

扫码关注云+社区