关闭 x
IT技术网
    技 采 号
    ITJS.cn - 技术改变世界
    • 实用工具
    • 菜鸟教程
    IT采购网 中国存储网 科技号 CIO智库

    IT技术网

    IT采购网
    • 首页
    • 行业资讯
    • 系统运维
      • 操作系统
        • Windows
        • Linux
        • Mac OS
      • 数据库
        • MySQL
        • Oracle
        • SQL Server
      • 网站建设
    • 人工智能
    • 半导体芯片
    • 笔记本电脑
    • 智能手机
    • 智能汽车
    • 编程语言
    IT技术网 - ITJS.CN
    首页 » JAVA »Java集合的手抄笔记,初学者必备

    Java集合的手抄笔记,初学者必备

    2015-07-07 00:00:00 出处:马志宇的专栏
    分享

    微信扫一扫:分享

    Scan me!

    微信里点“发现”,扫一下

    二维码便可将本文分享至朋友圈。

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

    不断更新中,请尽量访问博客原文。

    List

    ArrayList

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

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

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

    LinkedList

    以双向链表实现。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。

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

    插入、删除元素时修改前后节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作–add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指针的移动。

    CopyOnWriteArrayList

    并发优化的ArrayList。用CopyOnWrite策略,在修改时先复制一个快照来修改,改完再让内部指针指向新数组。

    因为对快照的修改对读操作来说不可见,所以只有写锁没有读锁,加上复制的昂贵成本,典型的适合读多写少的场景。如果更新频率较高,或数组较大时,还是Collections.synchronizedList(list),对所有操作用同一把锁来保证线程安全更好。

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

    补充

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

    没有按元素值排序的SortedList,在线程安全类中也没有无锁算法的ConcurrentLinkedList,凑合着用Set与Queue中的等价类时,会缺少一些List特有的方法。

    Map

    HashMap

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

    插入元素时,如果两条Key落在同一个桶(比如哈希值1和17取模16后都属于第一个哈希桶),Entry用一个next属性实现多个Entry以单向链表存放,后入桶的Entry将next指向桶当前的Entry。

    查找哈希值为17的key时,先定位到第一个哈希桶,然后以链表遍历桶里所有元素,逐个比较其key值。

    当Entry数量达到桶数量的75%时(很多文章说使用的桶数量达到了75%,但看代码不是),会成倍扩容桶数组,并重新分配所有原来的Entry,所以这里也最好有个预估值。

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

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

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

    LinkedHashMap

    扩展HashMap增加双向链表的实现,号称是最占内存的数据结构。支持iterator()时按Entry的插入顺序来排序(但是更新不算, 如果设置accessOrder属性为true,则所有读写访问都算)。

    实现上是在Entry上再增加属性before/after指针,插入时把自己加到Header Entry的前面去。如果所有读写访问都要排序,还要把前后Entry的before/after拼接起来以在链表中删除掉自己。

    TreeMap

    以红黑树实现,篇幅所限详见入门教程。支持iterator()时按Key值排序,可按实现了Comparable接口的Key的升序排序,或由传入的Comparator控制。可想象的,在树上插入/删除元素的代价一定比HashMap的大。

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

    ConcurrentHashMap

    并发优化的HashMap,默认16把写锁(可以设置更多),有效分散了阻塞的概率,而且没有读锁。
    数据结构为Segment[],Segment里面才是哈希桶数组,每个Segment一把锁。Key先算出它在哪个Segment里,再算出它在哪个哈希桶里。

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

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

    ConcurrentSkipListMap

    JDK6新增的并发优化的SortedMap,以SkipList实现。SkipList是红黑树的一种简化替代方案,是个流行的有序集合算法,篇幅所限见入门教程。Concurrent包选用它是因为它支持基于CAS的无锁算法,而红黑树则没有好的无锁算法。

    很特殊的,它的size()不能随便调,会遍历来统计。

    补充

    关于null,HashMap和LinkedHashMap是随意的,TreeMap没有设置Comparator时key不能为null;ConcurrentHashMap在JDK7里value不能为null(这是为什么呢?),JDK8里key与value都不能为null;ConcurrentSkipListMap是所有JDK里key与value都不能为null。

    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()) 实现。

    Queue

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

    –普通队列–

    LinkedList

    是的,以双向链表实现的LinkedList既是List,也是Queue。它是唯一一个允许放入null的Queue。

    ArrayDeque

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

    普通数组只能快速在末尾添加元素,为了支持FIFO,从数组头快速取出元素,就需要使用循环数组:有队头队尾两个下标:弹出元素时,队头下标递增;加入元素时,如果已到数组空间的末尾,则将元素循环赋值到数组[0](如果此时队头下标大于0,说明队头弹出过元素,有空位),同时队尾下标指向0,再插入下一个元素则赋值到数组[1],队尾下标指向1。如果队尾的下标追上队头,说明数组所有空间已用完,进行双倍的数组扩容。

    PriorityQueue

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

    –线程安全的队列–

    ConcurrentLinkedQueue/ConcurrentLinkedDeque

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

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

    PriorityBlockingQueue

    无界的并发优化的PriorityQueue,也是基于二叉堆。使用一把公共的读写锁。虽然实现了BlockingQueue接口,其实没有任何阻塞队列的特征,空间不够时会自动扩容。

    DelayQueue

    内部包含一个PriorityQueue,同样是无界的。元素需实现Delayed接口,每次调用时需返回当前离触发时间还有多久,小于0表示该触发了。
    pull()时会用peek()查看队头的元素,检查是否到达触发时间。ScheduledThreadPoolExecutor用了类似的结构。

    –线程安全的阻塞队列–

    BlockingQueue的队列长度受限,用以保证生产者与消费者的速度不会相差太远,避免内存耗尽。队列长度设定后不可改变。当入队时队列已满,或出队时队列已空,不同函数的效果见下表:

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

    ArrayBlockingQueue

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

    LinkedBlockingQueue/LinkedBlockingDeque

    可选定长的并发优化的BlockingQueue,基于链表实现,所以可以把长度设为Integer.MAX_VALUE。利用链表的特征,分离了takeLock与putLock两把锁,继续用notEmpty、notFull管理队列满或空时的阻塞状态。

    补充

    JDK7有个LinkedTransferQueue,transfer(e)方法保证Producer放入的元素,被Consumer取走了再返回,比SynchronousQueue更好,有空要学习下。

    上一篇返回首页 下一篇

    声明: 此文观点不代表本站立场;转载务必保留本文链接;版权疑问请联系我们。

    别人在看

    抖音安全与信任开放日:揭秘推荐算法,告别单一标签依赖

    ultraedit编辑器打开文件时,总是提示是否转换为DOS格式,如何关闭?

    Cornell大神Kleinberg的经典教材《算法设计》是最好入门的算法教材

    从 Microsoft 下载中心安装 Windows 7 SP1 和 Windows Server 2008 R2 SP1 之前要执行的步骤

    Llama 2基于UCloud UK8S的创新应用

    火山引擎DataTester:如何使用A/B测试优化全域营销效果

    腾讯云、移动云继阿里云降价后宣布大幅度降价

    字节跳动数据平台论文被ICDE2023国际顶会收录,将通过火山引擎开放相关成果

    这个话题被围观超10000次,火山引擎VeDI如此解答

    误删库怎么办?火山引擎DataLeap“3招”守护数据安全

    IT头条

    平替CUDA!摩尔线程发布MUSA 4性能分析工具

    00:43

    三起案件揭开侵犯个人信息犯罪的黑灰产业链

    13:59

    百度三年开放2.1万实习岗,全力培育AI领域未来领袖

    00:36

    工信部:一季度,电信业务总量同比增长7.7%,业务收入累计完成4469亿元

    23:42

    Gartner:2024年全球半导体营收6559亿美元,AI助力英伟达首登榜首

    18:04

    技术热点

    iOS 8 中如何集成 Touch ID 功能

    windows7系统中鼠标滑轮键(中键)的快捷应用

    MySQL数据库的23个特别注意的安全事项

    Kruskal 最小生成树算法

    Ubuntu 14.10上安装新的字体图文教程

    Ubuntu14更新后无法进入系统卡在光标界面解怎么办?

      友情链接:
    • IT采购网
    • 科技号
    • 中国存储网
    • 存储网
    • 半导体联盟
    • 医疗软件网
    • 软件中国
    • ITbrand
    • 采购中国
    • CIO智库
    • 考研题库
    • 法务网
    • AI工具网
    • 电子芯片网
    • 安全库
    • 隐私保护
    • 版权申明
    • 联系我们
    IT技术网 版权所有 © 2020-2025,京ICP备14047533号-20,Power by OK设计网

    在上方输入关键词后,回车键 开始搜索。Esc键 取消该搜索窗口。