Java 容器相关知识全面总结

澳门新浦京8455com 6

Java实用类库提供了一套相当完整的器皿来帮助大家消释广大切实可行难点。因为作者自身是一名Android开垦者,包罗自身在内相当多安卓开荒,最专长的便是ListView(RecycleView卡塔尔(قطر‎+Base艾达pter+ArrayList三杀手,
日常接触使用的器皿也只有ArrayList和HashMap。招致对于任何Java容器种类的左右和平运动用还停留在很浅的层面。省不足而思改良,那么随着自个儿来总结一下Java容器的连锁文化吧。

同步容器类

  • 联机容器类Vector 和 Hashtable ,以致一些由
    Collections.synchronizedXxx
    等工厂方法创设的。其底层的编写制定只是是用古板的synchronized
    关键字对每一个公用的点子都开展同步
    ,使得每趟只可以有三个线程访谈容器之处。那很明显不满足大家后天互连网时期的高并发的急需,在保障线程安全的同事,也亟必要有丰硕好的性质。

  • 同步类容器都是线程安全的,但在少数场景下须求加锁来保卫安全复合操作。复合操作满含:迭代(一再访问元素,直到遍历完容器中兼有因素)、跳转(依照钦点顺序找到当前成分的下三个要素)以致规范化运算。那么些复合操作在十二线程并发地矫正容器时,也许展销会现出意外的一颦一笑,最非凡的就是:ConcurrentModificationException
    原因是容器迭代的进度中,被冒出的改动了剧情,那是由于开始的一段时期迭代设计的时候并不曾思虑并发改善的标题。

  • 一起容器将享有对容器的景况的拜谒都串行话,以完毕他们的线程安全性。这种办法的代价是严重下跌并发性,当多少个线程竞争容器锁时,吞吐量将严重下滑。

    //-----------复合操作时,并不能保证线程安全性--------------------
    final Vector<String> tickets = new Vector<>();
    for(int i = 1; i<= 1000; i++){
      tickets.add("火车票"+i);
    }
    
    // 在迭代的过程中,被后面的线程并发的修改了迭代器中的内容,就会抛出 ConcurrentModificationException
    for (Iterator iterator = tickets.iterator(); iterator.hasNext(); ) {
      String string = (String) iterator.next();
      tickets.remove(20);
    }
    
    for(int i = 1; i <=10; i ++){
      new Thread("线程"+i){
        public void run(){
          while(true){
            if(tickets.isEmpty()) break;
            System.out.println(Thread.currentThread().getName() + "---" + tickets.remove(0));
          }
        }
      }.start();
    }
    

结构

  • java容器类的一而再结构
  • 具体介绍
    • 迭代器
    • Collection
      • List
      • Set
      • Queue
    • Map
  • 有的提出
  • 升级·并发容器
    • CopyOnWriteArrayList与Copy-On-Write策略
    • ConcurrentLinkedQueue
    • ConcurrentHashMap与锁分段本领
    • 窒碍队列

并发容器类

  • JDK1.5 提供了二种并发容器类来改正同步容器的习性。ConcurrentHashMap,
    用来代表同步且依据散列的Map(HashTable),並且在ConcurrentHashMap
    中,增添了一部分大规模复合操作的支撑(如:“若未有则增进,替换以致有标准删除等”)。以至CopyOnWriteArrayList
    ,用于遍历操作为重要操作的动静下代表同步的List(Voctor卡塔尔(قطر‎。
  • JDK1.5 还增添了二种新的容器类型: Queue 和 BlockingQueue, Queue
    用来一时保存一组等待管理的要素。

    • 高品质队列 ConcurrentLinkedQueue,那是多个金钱观的先进先出的体系。
    • 带事情发生前级的 PriorityQueue, 那是三个非并发预先队列
    • BlockingQueue 扩大了 Queue,
      扩展拉可阻塞的插入和获得成分等操作。假设队列为空,那么获取成分的操作将一贯不通,知道队列中现身四个可用的要素。
      若是队列已满(澳门新浦京8455com,对此有界队列来讲),那么插入成分的操作将直接不通,知道队列中冒出可用的上空。适用于生产者-消费者设计格局。
    • 其他实现Queue的类:
      • LinkedBlockingQueue
      • ArrayBlockingQueue
      • PriorityBlockingQueue
      • SynchronousQueue
  • Java6 引进了 ConcurrentSkipListMap、ConcurrentSkipListSet,
    分别作为一道的 SortedMap 和 SortedSet
    的并发替代品。举例用(synchronizedMap 包装的TreeMap 或 TreeSet)

java容器类的后续布局

Java容器类库定义了五个不等定义的器皿,Collection和Map

  • Collection 贰个独立成分的行列,这一个因素都信守一条或多条准则。List必需根据插入的次第保存成分。Set不能有双重成分。Queue根据相排版队法规来显著目的发生的相继。

澳门新浦京8455com 1

(文中Jdk源码版本无差距常表明均为jdk1.8.0_101)

    public interface Collection<E> extends Iterable<E> {
        int size();

        boolean isEmpty();

        boolean contains(Object o);

        Iterator<E> iterator();

        Object[] toArray();

        <T> T[] toArray(T[] a);

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(java.util.Collection<?> c);

        boolean addAll(java.util.Collection<? extends E> c);

        boolean removeAll(java.util.Collection<?> c);

        ... //省略了其他方法
    }

能够看看,java定义了Collection接口和中间聚焦的基本操作方法,Collection默许能够打开对集中末端添美成分,删除钦命元素等操作。List、Set、Queue接口都世袭自Collection并定义了个别分化的点子。

  • Map 一组合没错”键值对”对象,允许大家使用键来查找值。

澳门新浦京8455com 2

    public interface Map<K,V> {
        int size();

        boolean containsKey(Object key);

        boolean containsValue(Object value);

        V get(Object key);

        V put(K key, V value);

        V remove(Object key);

        void putAll(java.util.Map<? extends K, ? extends V> m);

        void clear();

        Set<K> keySet();

        Collection<V> values();

        Set<java.util.Map.Entry<K, V>> entrySet();

        interface Entry<K,V> {
            K getKey();

            V getValue();

            V setValue(V value);

            boolean equals(Object o);

            int hashCode();

            ...
        }

        boolean equals(Object o);

        int hashCode();

    }

Map内部接口Entry<K,V>对应着Map的键值对。

ConcurrentMap

  • ConcurrentMap 接口下有三个第一的贯彻:
    • ConcurrentHashMap
    • ConcurrentSkipListMap (辅助并发排序成效,弥补
      ConcurrentHashMap)
  • ConcurrentHashMap
    内部使用段(Segment)来表示那个不相同的有些,每一个段其实就是多少个小的HashTable,它们有和谐的锁。只要七个修正操作产生在分化的段上,它们就能够并发实行。把二个总体分成了15个段(Segment)。也便是参天帮助十六个线程的出现改善操作。那也是在三十二线程场景时减小锁的粒度从而跌落锁竞争的一种方案,而且代码中几近分享变量使用volatile关键字表明,指标是第有时间获取修改的原委。品质非常好。

现实介绍

Copy-On-Write容器

  • Copy-On-Write 简单称谓 COW,是一种用于程序设计中的优化战略。
  • JDK里的COW容器有三种: CopyOnWriteArrayList 和 CopyOnWriteArraySet,
    COW容器特别有用,能够在十分的多的并发场景中使用到
  • 什么是 CopyOnWrite 容器
    • CopyOnWrite 容器即 写时复制
      的器皿。通俗的精晓是当大家往四个器皿添日成分的时候,不直接往当前容器增多,而是先将近年来容器举行Copy,复制出一个新的容器。那样做的功利是大家可以对CopyOnWrite
      容器进行并发的读,而无需加锁,因为前段时间容器不会拉长此外因素。所以CopyOnWrite容器也是一种读写分离的合计,读和写在区别的容器中举办。
    • 当新容器完结写操作之后,会把原本容器的援引指向新的器皿上。

迭代器

先介绍一下迭代器。迭代器自个儿也是一种设计方式,设计的初志在于:容器的兑现由很各个,而作者辈想对容器举行遍历操作的话,首先不应有关爱容器达成的内幕,其次遍历操作应该是轻量级的。迭代器统一了对容器的拜谒格局,同不常候创设它的代价非常小。值得注意的是,Iterator只好单向移动。

    public interface Iterator<E> {
        boolean hasNext();

        E next();

        default void remove() {
            throw new UnsupportedOperationException("remove");
        }

        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
            }
    }

由此容器的iterator(卡塔尔(قطر‎方法得到容器的迭代器
迭代器的next(卡塔尔获取下叁个成分
hasNext(卡塔尔(قطر‎判别是还是不是还应该有成分
remove(State of Qatar删除钦点元素

ListIterator

ListIterator是Iterator的扩张之内,用于种种List类访谈,帮忙双向移动。

Collection

List

List
承诺可以将成分维护在特定的系列中.List接口在Collection的根基上加多了多量的必定要经过的道路,使得可以再List中间插入和移除成分。

    public interface List<E> extends Collection<E> {

        ...

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(Collection<?> c);

        boolean addAll(Collection<? extends E> c);

        boolean addAll(int index, Collection<? extends E> c);

        boolean removeAll(Collection<?> c);

        boolean retainAll(Collection<?> c);

        E get(int index);

        E set(int index, E element);

        void add(int index, E element);

        E remove(int index);

        int indexOf(Object o);

        int lastIndexOf(Object o);

        java.util.List<E> subList(int fromIndex, int toIndex);

        ...

    }

澳门新浦京8455com 3

有二种档案的次序的List,ArrayList和LinkedList

List类型 优点 缺点 底层实现
ArrayList 随机访问元素较快 中间元素的插入和删除较慢 数组
LinkedList 中间元素的插入和删除,顺序访问的优化 随机访问元素较慢 双向链表

Set

Set不保留重复的要素,常常用于快捷寻找成分。值得提的是,Set具备与Collection别无二致的接口,未有此外额外的职能。
存入的成分必得定义equals(卡塔尔国方法

Set类型 使用场景 底层实现
HashSet 快速查找,元素必须定义hashCode() 链表
TreeSet 保持次序,元素必须实现Comparable接口 红-黑树结构
LinkedHashSet 维护次序的HashSet, 元素必须定义hashCode() 链表

澳门新浦京8455com 4

Queue

除去并发应用,Queue唯有的几个落到实处是LinkedList和PriorityQueue,
个中LinkedList同期实现了List,
Deque接口。它们的不相同在于排序行为实际不是性质。

    public interface Queue<E> extends Collection<E> {
        boolean add(E e);

        boolean offer(E e);

        E remove();

        E poll();

        E element();

        E peek();
    }

澳门新浦京8455com 5

Map

Map类型 使用场景 底层实现
HashMap 快速查询 散列表
LinkedHashMap 迭代遍历具有顺序(插入顺序 or 最近最少使用) 链表
TreeMap 具有排序,唯一可以返回子树的Map(subMap()) 红-黑树结构
WeakHashMap 弱键映射,映射之外无引用的键,可以被垃圾回收 散列表
ConcurrentHashMap 线程安全的Map 链表
IdentityHashMap 使用==代替equals()对键进行排序,专位解决特殊问题 链表

澳门新浦京8455com 6

作者们能够手工业调解HashMap来调度品质,涉及到如体量、带头容量、尺寸、负载因子等概念。感兴趣的话能够看某些有关资料。

有个别建议

  • 永不采用老式的器皿 如Vector Enumeration Hashtable
    Stack(没有错,那就是java最先的倒霉设计,实际中动用栈的话推荐LinkedListState of Qatar

进级·并发容器

那边不商商酌的太紧密的兑现,仅仅简要介绍一下底蕴知识,感兴趣的能够翻阅《Java
并发编制程序的办法》那本书。

CopyOnWriteArrayList与Copy-On-Write策略

Copy-On-Write简单称谓COW,是一种用于程序设计中的优化战术。其基本思路是,从一早先大家都在分享同多少个内容,当某人想要改革那些剧情的时候,才会真的把内容Copy出去产生二个新的剧情然后再改,那是一种延时懒惰攻略。从JDK1.5带头Java并签发承包合约里提供了三个应用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器特别常有用,能够在老许多的并发场景中使用到。

CopyOnWrite容器即写时复制的容器。通俗的接头是当大家往叁个容器添比索素的时候,不直接往当前容器加多,而是先将近年来容器进行Copy,复制出一个新的容器,然后新的器皿里添韩成分,增多完成分之后,再将原容器的引用指向新的器皿。那样做的利润是大家得以对CopyOnWrite容器进行并发的读,而不需求加锁,因为眼前容器不会增加任何因素。所以CopyOnWrite容器也是一种读写分离的酌量,读和写不相同的容器。

CopyOnWrite容器只好保险数据的终极一致性,不可能保险数据的实时一致性。所以只要您愿意写入的的数码,立即能读到,请不要选择CopyOnWrite容器。

ConcurrentLinkedQueue

在现身编制程序中,有时候须要采纳线程安全的连串或列表。日常实现线程安全有两种方法,一种是运用堵塞算法,一种是运用非拥塞算法。非拥塞算法达成底工为循环CAS(Compare
and Swipe 比较和置换卡塔尔(قطر‎。

ConcurrentLinkedQueue技巧上的兑现与CopyOnWriteArrayList与Copy肖似,不过容器只有部分剧情并不是整套容器能够被复制和校勘。ConcurrentLinkedQueue有head节点和tail节点组成,种种节点由节点成分(item卡塔尔国和指向下三个结点(nextState of Qatar的援引组成。节点之间通过next关联起来,形成一张链表结构的队列。

ConcurrentHashMap与锁分段本事

ConcurrentHashMap是线程安全且十分的快的HashMap。四线程境况下,使用非线程安全的HashMap会招致死循环,而如小说中国建筑工程总公司议的那样,HashTable这种过时容器功效低下(使用synchronized来确定保证线程安全卡塔尔。ConcurrentHashMap使用锁分段本事,大大升高了产出使用的频率。

锁分段本领:
要是容器有多把锁,每一把锁用于锁容器当中一些多少,当多线程访问容器不相同数据段数据时,线程间就不设有锁竞争,进而巩固并发采访成效。

拥塞队列

JDK7 提供了7个闭塞队列,达成原理都是基于分娩-花销情势的等待通告机制。

阻塞队列类型 特点
ArrayBlockingQueue 由数组结构组成的有界阻塞队列
LinkedBlockingQueue 由链表结构组成的有界阻塞队列
PriorityBlockingQueue 支持优先级排序的无界阻塞队列
DelayQueue 使用优先级队列实现的无界阻塞队列
SynchronousQueue 不储存元素的阻塞队列
LinkedTransferQueue 由链表结构组成的无界阻塞队列
LinkedBlockingQueue 由链表结构组成的双向阻塞队列

多谢阅读~

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图