Java中的工具类-集合

分类: JVM 发布于:

Java的集合框架主要有Joshua Bloch实现。

以行为分，集合类的拓扑结构

List,Set,Queue 接口之间的区别

List 接口的设计目的

  • 是一个有序的集合。有序体现在 每个集合中的元素都有一个索引(index)

  • 可精确控制List[集合中]的元素，比如remove(), get(),全体迭代等。

  • 可使用索引查找集合中的元素，或者全体检索。

Set的设计目的

Set符合数学意上对结合的定义 {x 1,2,3,..N }
  • 不包含重复元素。更具体的说， 集合内部不存在两个元素使得 x.hashcode == y.hashcode 为true。

Queue的设计目的

  • 人如其名,它为队列的行为设计。在集合的基础上增加了 插入(insertion)、提取(extraction)、查看(inspections)操作。

  • 每个方法都有两种形式。 操作失败则抛出异常，另一个方法放回特定值。

  • 一般实现不允许null元素插入。

List的子类

ArrayList

  • 自动扩容， 默认容量 10

使用Arrays.copyOf方法 按照固定大小生成一个新的array。

  • get,set, iterator, listIterator 运行效率为O(1)

  • insert 操作运行效率O(N)

  • 所有操作没有使用同步方法(synchronized)

多线程场景下，创建方法

List list = Collections.synchronizedList(new ArrayList(…));

Vendor

  • 自增长的数组

  • 线程安全的数组操作。基本操作有synchronized修饰符。

  • 子类Stack实现了LIFO(后进先出)的操作方式(线程安全) pop, push, peek, search 。

AbstractSequentialList及其子类LinkedList

  • 双向链表，子类实现LinkedList实现没有线程安全

  • 实现顺序访问(List)， 顺序访问的含义是增删查操作 从头或者从尾部操作。

随机访问的列表， 随机表现在 在存储之前要先确定容量(分配内存)，分配完成后，把数据存储在特定位置。 顺序访问通过指针地址链起来，不需要实现确定容量。

Set接口实现以及abstractSet及其子类

  • 集合类最重要的行为是判断元素是否属于当前集合

  • HashSet 类是HashMap的子视图。何为子视图? 它是的实现基于HashMap的key，原因是hashMap的key 实现了去重、迭代器、常规增删查。

  • LinekdHashSet 是LinkedHashMap的子视图(设计模式中的适配器模式)。 而普通的HashSet是HashMap的子视图。

  • 允许空插入。是否允许空插入为什么特别强调? 因为空是判断集合完整性的重要特征。

  • 操作不是线程安全的。使用Collections类的包装器返回一个线程安全的实例:

Set s = Collections.synchronizedSet(new LinkedHashSet(…));

  • SortedSet 是支持排序的集合。

  • SortedSet 有四种构造形式: (1)、空构造器 (2)、携带一个比较器(实现Comparator接口)的构造器 (3) 以集合(Collection接口)子类为参数的构造。(4) 以自身类实例(SortedSet)为参数的构造。

  • TreeSet 的实现不是线程安全的。它把add、remove、contains操作的时间从原来的O(N)缩短为Log(n)。 类似hashSet, 它是适配完的TreeMap

  • 以上可见， Set子类的实现依托于Map类的实现。 原因是Map类的keys是一个集合的实现。 Map的本质是通过hashcode把一类集合(键keys) 映射到 另外一类(值values)集合。

ArrayList、LinkedList的增、删效率比较

    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        LinkedList linkedList = new LinkedList();

// ArrayList add
        long startTime = System.nanoTime();

        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }
        long endTime = System.nanoTime();
        long duration = endTime - startTime;
        System.out.println("ArrayList add:  " + duration);

// LinkedList add
        startTime = System.nanoTime();

        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList add: " + duration);

// ArrayList get
        startTime = System.nanoTime();

        for (int i = 0; i < 10000; i++) {
            arrayList.get(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("ArrayList get:  " + duration);

// LinkedList get
        startTime = System.nanoTime();

        for (int i = 0; i < 10000; i++) {
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList get: " + duration);


// ArrayList remove
        startTime = System.nanoTime();

        for (int i = 9999; i >=0; i--) {
            arrayList.remove(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("ArrayList remove:  " + duration);

// LinkedList remove
        startTime = System.nanoTime();

        for (int i = 9999; i >=0; i--) {
            linkedList.remove(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList remove: " + duration);
    }

运行时输出

ArrayList add:  47381357
LinkedList add: 6723342    # LinkedList 增加元素的效率大约是arraylist的7倍
ArrayList get:  33054261 # get的效率是linkedlist的9倍
LinkedList get: 376488900
ArrayList remove:  659588253
LinkedList remove: 185407357  # 删除效率是arrraylist的4倍

Process finished with exit code 0

为什么linkedlist的add、remove效率比arraylist高？

ArrayList的add方法定义

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

LinkedList的add方法定义

    /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

从定义来看 arraylist的add方法比linkedlist多了一步容量检查。

LinkedList的remove操作定义

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

ArrayList的remove操作定义

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArrayList的remove定义效率更底了， 使用System.arraycopy直接把移除元素后面的元素整体迁移。 LinkedList的移除方法效率是O(N)