Java Collection Framework概述

小说来源:听云博客

Collection概述

Java
collection是java提供的工具包,包蕴了常用的数据结构:集合、链表、队列、栈、数组、映射等。

Java集合首要能够分开为两个部分:List列表、Set集合、Map映射、工具类(Iterator、Arrays和Collections)。

Java
collection 结构图

图片 1 

因此上图大家能够见到

  • Collection是一个interface 

Collection有List和Set两大分支。

List<E>是三个系列,依照下标索引,第一个成分的下标是0,List的落到实处类有LinkedList,
ArrayList, Vector,
Stack。List是有序的队列,List中能够有双重的值。

Set<E>是3个会面,SET中的值是唯一的,大家平时会遭逢List去重的难点,把List转为SET就足以便捷完毕Set的达成类有HastSet和TreeSet。HashSet。在那之中TreeSet是稳步的。

  • Ma<K,V>是五个interface,即key-value键值对。Map中的每3个因素包罗“三个key”和“key对应的value”。 

AbstractMap是个抽象类,它已毕了Map接口中的大多数API。而HashMap,TreeMap,WeakHashMap都是后续于AbstractMap。

  • Iterator。它是遍历集合的工具,我们常常使用Iterator迭代器来遍历集合。Collection的兑现类都要落到实处iterator()函数,重临2个Iterator对象。

  • 抽象类AbstractCollection、AbstractList、AbstractSet、AbstractMap是抽象类,他们都完成了独家的大部方式,大家一直接轨Abstract类就能够节省重复编码相同的办法
    。PS当时来面试的时候被问到那些标题甚至一下没想起来。

List简介

一、List
是一个接口,它两次三番于Collection的接口。它代表着平稳的行列。

二、AbstractList
是七个抽象类,它继续于AbstractCollection。AbstractList完毕List接口中除size()、get(int
location)之外的函数。

三、AbstractSequentialList
是叁个抽象类,它继续于AbstractList。AbstractSequentialList
达成了“链表中,依据index索引值操作链表的漫天函数”。 

四、ArrayList,
LinkedList, Vector, Stack是List的四个落实类。

ArrayList
是2个数组成代表队列。它由数组完毕,实现了RandomAccess, Cloneable,
java.io.Serializable接口,所以能够不管访问,克隆,种类化,随机走访成效高,随机插入、随机删除功用低。

LinkedList
是贰个双向链表。它也足以被作为储藏室、队列或双端队列举行操作。LinkedList随机访问功效低,但随便插入、随机删除效能低。

Vector
是矢量队列,和ArrayList一样,它也是多个动态数组,由数组达成。不过ArrayList是非线程安全的,而Vector是线程安全的。

Stack
是栈,继承于Vector。栈的风味是:先进后出(First In Last Out)。

List和Vector差别,ArrayList中的操作不是线程安全的!所以,建议在单线程中才使用ArrayList,而在三十二线程中能够接纳Vector大概CopyOnWriteArrayList。

List的使用

一、要是涉嫌到“栈”、“队列”、“链表”等操作,应该想念用List,具体的接纳哪个List,根据上面包车型大巴行业内部来选用。

二、对于急需火速插入,删除成分,应该使用LinkedList。

3、对于供给飞快随机走访成分,应该选取ArrayList。

四、对于“单线程环境”
可能“二十多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类(如ArrayList)。

5、对于“二十多线程环境,且List大概同时被多个线程操作”,此时,应该利用同步的类(如Vector)。

Fail-Fast

fail-fast
机制是java集合(Collection)中的1种错误机制。当三个线程遍历某集合时,这些集合的值被此外线程改变,该线程就会抛出ConcurrentModificationException很是。

fail-fast示例。

package Test;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class FastFailEX {

    private static List<Integer> list = new ArrayList<Integer>();

    public static void main(String[] args) {

        //使用两个线程操作list
        new ThreadA().start();
        new ThreadB().start();
    }
     private static void print() {
        System.out.println("");
        Integer value = null;
        Iterator<Integer> iter = list.iterator();
        while(iter.hasNext()) {
            value = (Integer)iter.next();
            System.out.print(value+", ");
        }
    }

    //向list添加元素
    private static class ThreadA extends Thread {
        public void run() {
            for(int i=0;i<10;i++){
                 list.add(i);
                 print();
            }
        }
    }
    //向list添加元素
    private static class ThreadB extends Thread {
        public void run() {
            for(int i=10;i<20;i++){
                list.add(i);
               print();
            }
        }
    }

}

运行结果:

图片 2 

结果表明:

当某多少个线程遍历list的经过中,list的始末被此外三个线程所改变了;就会抛出ConcurrentModificationException极度,产生fail-fast事件。

ConcurrentModificationException是在操作Iterator时抛出的那叁个。大家先看看Iterator的源码。在AbstractList.java中

图片 3 

图片 4

图片 5 

透过上述代码段大家来看两点

一、执行next()时,要先判断iterator重回的目的中的modCount”和“当前的modCount”是还是不是等于

2、要是不对等,则抛回相当

接下去大家要通晓在怎么意况下
modCount!= expectedModCount

笔者们来看ArrayList.java中的代码

图片 6 

 图片 7

图片 8

图片 9

图片 10

图片 11

图片 12 

大家明天清楚,只要修改集合中的成分个数时,都会变动modCount的值。

添加时在决定是还是不是扩空list前改动modCount,删除成分时直接修改

从那之后,大家就完全了然了fail-fast是如何爆发的。

即,当多少个线程对同1个集结举办操作的时候,某线程访问集合的历程中,该集合的始末被别的线程所改变(即其余线程通过add、remove、clear等方法,改变了modCount的值);这时,就会抛出ConcurrentModificationException格外,发生fail-fast事件。

解决fail-fast

使用CopyOnWriteArrayList
就不会发生fail-fast

上源码

图片 13

图片 14  

从中,我们得以观察:

CopyOnWriteArrayList是上下一心实现了Iterator
 为COWIterator。

ArrayList的Iterator调用next()时,会调用checkForComodification()相比较expectedModCount和modCount的深浅;CopyOnWriteArrayList的Iterator达成类中,没有checkForComodification(),所以不会抛出ConcurrentModificationException非常。 

Map简介

Map是什么:public
interface Map<K,V> { }

Map
是一个键值对(key-value)映射接口。Map映射中不能够包罗重复的键;种种键最四只好照射到二个值。

Map
接口提供三种collection
视图,允许以键集、值集或键-值映射关系集的样式查看有些映射的始末。

Map
映射顺序。有个别实现类,能够分明有限帮忙其顺序,如
TreeMap;另1部分炫耀完成则不有限匡助顺序,如 HashMap 类。

Map
的兑现类应该提供3个“标准的”构造方法:第贰个,void(无参数)构造方法,用于创建空映射;第二个,带有单个
Map
类型参数的构造方法,用于成立3个与其参数具有相同键-值映射关系的新映射。实际上,后3个构造方法允许用户复制任意映射,生成所需类的三个等价映射。就算不能强制执行此建议(因为接口无法包含构造方法),不过JDK 中全数通用的映照达成都遵守它。

Map体系

1、Map
是炫耀接口,Map中贮存的始末是键值对(key-value)。

二、AbstractMap
是后续于Map的抽象类,它完成了Map中的大部分API。别的Map的贯彻类能够因而持续AbstractMap来压缩重复编码。

三、SortedMap
是后续于Map的接口。SortedMap中的内容是排序的键值对,排序的章程是经过比较器(Comparator)。

4、NavigableMap
是后续于SortedMap的接口。相比较于SortedMap,NavigableMap有一多级的领航方法;如”获取超越/等于某指标的键值对”、“获取小于/等于某目的的键值对”等等。 

五、TreeMap
继承于AbstractMap,且实现了NavigableMap接口;因而,TreeMap中的内容是“有序的键值对”,
它是因而红黑树完成的。它一般用于单线程中储存有序的照耀。

陆、HashMap
继承于AbstractMap,没实现SortedMap或NavigableMap接口;因而,HashMap的内容是严节的键值对。

七、Hashtable继承于Dictionary(Dictionary也是键值对的接口),完成Map接口;因而,Hashtable的内容也是“键值对,是冬天的”。
Hashtable是线程安全的。 

八、WeakHashMap
继承于AbstractMap。它和HashMap的键类型不相同,WeakHashMap的键是“弱键”,
当“弱键”被GC回收时,它对应的键值对也会被从WeakHashMap中删除。JVM提供的弱引用

Set简介

Set
是继承于Collection的接口。它是三个不容许有再一次成分的集AbstractSet
是二个抽象类,它两次三番于AbstractCollection,AbstractCollection完成了Set中的绝半数以上函数,为Set的贯彻类提供了造福。

HastSet
和 TreeSet 是Set的多个达成类。

HashSet中的成分是冬辰的。

TreeSet中的元素是雷打不动的,不协助快速随机遍历,只可以通过迭代器举行遍历。

Iterator和Enumeration

在Java集合中,我们平日都经过
“Iterator(迭代器)” 或 “Enumeration(枚举类)” 去遍历集合

Enumeration是3个接口,它的源码如下

图片 15 

Iterator也是三个接口,它的源码如下:

图片 16 

1、函数接口不一样

Enumeration惟有1个函数接口。通过Enumeration,大家只可以读取集合的数量,而不能对数据开始展览改动。

Iterator唯有三个函数接口。Iterator除了能读取集合的多寡之外,也能数据开始展览删减操作。

2、Iterator支持fail-fast机制,而Enumeration不支持。

Iterator和Enumeration质量比较

package
Test;

import
java.util.Enumeration;

import
java.util.Hashtable;

import
java.util.Iterator;

import
java.util.Map.Entry;

import
java.util.Random;

public class IteratorEnumerationEX {

    public static void main(String[] args) {
        int val;
        Random r = new Random();
        Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
        for (int i=0; i<100000; i++) {
            val = r.nextInt(100);
            table.put(i, val);
        }
        iterateHashtable(table) ;
        enumHashtable(table);
    }

    private static void iterateHashtable(Hashtable<Integer, Integer> table) {
        long startTime = System.currentTimeMillis();
        Iterator<Entry<Integer, Integer>> iter = table.entrySet().iterator();
        while(iter.hasNext()) {
            iter.next();
        }
        long endTime = System.currentTimeMillis();
        countTime("iterate",startTime, endTime);
    } 

    private static void enumHashtable(Hashtable<Integer, Integer> table) {
        long startTime = System.currentTimeMillis();
        Enumeration<Integer> enu = table.elements();
        while(enu.hasMoreElements()) {
            enu.nextElement();
        }

        long endTime = System.currentTimeMillis();
        countTime("enum",startTime, endTime);
    }

    private static void countTime(String type,long start, long end) {
        System.out.println(type+":"+(end-start)+"ms");
    }
}

出口结果

图片 17 

因为Iterator扶助fail-fast所以做操作多1些特性也相对慢一些

 

原稿链接:http://blog.tingyun.com/web/article/detail/268

相关文章