关系总览

java.util包下汇合类关系图如下，不蕴含concurrent包，斜体标识接口，粗体标识抽象类，红线标识继承或实现。

Collection

Collection提供以下接口办法及默认接口办法

AbstractCollcetion

概述

该类实现类Collection接口的大部分办法，其中提供实现的具体方法，大部分依赖于待子类实现的形象办法。

继承自该类的子类，按可变性来说，对子类要求如下：

  • 不可批改Collection：如果要实现一个不可批改的Collection，那么子类只须要实现iterator和size办法。iterator返回的迭代器，必须实现hasNext、next办法
  • 可批改Collection：如果要实现一个可批改的Collection，除了iterator和size办法，子类还须要笼罩add办法；iterator返回的迭代器，必须实现remove办法。
形象办法
  • iterator()：源自Iterable接口。返回迭代器对象。
  • size()：源自Collection接口。返回汇合元素数量。
具体方法
  • isEmpty()：判断汇合是否为空。具体实现依赖子类实现的size()，判断size()==0
  • contains(Object)：判断汇合是否蕴含指定元素。具体实现依赖子类实现的iterator()，通过迭代器遍历汇合中元素，若存在元素与参数对象相等(同为null，或者equals返回true)，返回true；否则返回false
  • toArray()：返回汇合元素组成的数组。具体实现依赖子类实现的iterator()和size()，通过size()构建对应长度的数组，通过迭代器遍历所有元素初始化数组
  • toArray(T[])：返回汇合元素组成的数组。具体实现依赖子类实现的iterator()和size()。如果参数传入的数组长度不能包容所有元素，则新创建一个更大的数组存储所有元素并返回。
  • add(E) : 默认抛出UnsupportedOperationException异样
  • remove(Object)：删除指定元素。具体实现依赖子类实现的iterator()。通过迭代器遍历汇合中元素，若存在元素与参数对象相等(同为null，或者equals返回true)，则调用迭代器的remove()，同时返回true；否则返回false
  • containsAll(Collection<?> )：如果参数汇合是以后汇合的子集，则返回true，否则返回false。具体实现是for循环遍历参数汇合中的元素，调用contains(Object)，如果有一个元素不蕴含在以后汇合，则返回false；如果均蕴含在以后汇合，返回true
  • addAll(Collection<?> )：将参数汇合中的所有元素退出到以后汇合。具体实现依赖add(E) 。具体实现是for循环遍历参数汇合中元素，一一调用add(E)，只有有一个增加胜利，则最终返回true
  • removeAll(Collection<?> )：删除以后汇合中与参数汇合中的元素相等的元素。具体实现依赖iterator()。通过迭代器遍历以后汇合中元素，若参数汇合蕴含该元素，则调用迭代器的remove()进行删除，若胜利删除过一个元素，则最终返回true。否则返回false。
  • retainAll(Collection<?> )：删除以后汇合中与参数汇合中的元素不相等的元素。具体实现依赖iterator()。通过迭代器遍历以后汇合中元素，若参数汇合不蕴含该元素，则调用迭代器的remove()进行删除，若胜利删除过一个元素，则最终返回true。否则返回false。
  • clear()：删除汇合所有元素。具体实现依赖iterator()。通过迭代器遍历以后汇合中元素，调用迭代器的remove()进行删除
  • toString()：打印出汇合中所有元素，元素两头用逗号分隔，两边用中括号。具体实现依赖iterator()。通过迭代器遍历以后汇合中的元素，实用StringBuilder进行拼接，最终返回所有元素组成的字符串。例如 [1,2,3,4,5]

Set

Set 接口笼罩了Collection接口的默认办法spliterator，指定characteristics为DISTINCT；除此之外，没有新增任何新办法。

AbstractSet

概述

AbstractSet继承AbstractCollcetion，实现Set接口。AbstractSet规定不容许子类增加雷同元素到汇合中，但具体逻辑中没有做相应管制，须要子类具体遵循该规定进行实现。AbstractSet笼罩了AbstractCollection的removeAll办法，同时实现了equals和hashCode办法，除此之外没有定义任何额定的形象办法。

形象办法
  • iterator()：源自Iterable接口。返回迭代器对象。
  • size()：源自Collection接口。返回汇合元素数量。
具体方法
  • equals(Object)：判断是否相等；若指向同一对象则返回true；若参数不是Set的实例则返回false；若参数是Set的实例，则比拟参数Set和以后Set的size()，如果不相等则返回false；如果相等，则调用父类实现的containsAll(Collection)返回后果。
  • hashCode()：计算hash值；该办法依赖于iterator()。通过迭代器遍历汇合中元素，将所有元素的hashCode累加并返回。
  • removeAll(Collection)：删除以后汇合中与参数汇合中的元素相等的元素。该办法笼罩了AbstractCollection的实现。通过size()和iterator()获取元素较少的汇合的迭代器，而后迭代出所有元素，如果调用较大汇合的contains(E)，如果蕴含则删除。如果删除过一个元素，则最终返回true

List

List接口笼罩了Collection接口的默认办法spliterator，指定characteristics为ORDERED；除此之外，新增了图中所圈的办法。

List接口新增办法简述：

  • 地位拜访操作（Postional Access Operations）

    • get(int): 按index查问元素
    • set(int,E): 按index批改元素
    • add(int, E): 按index减少元素
    • remove(int): 按index删除元素

  • 搜寻操作（Search Operations）

    判断相等的条件： o==null?get(i)==null:o.equals(get(i))

    • indexOf(Object): 返回列表中第一个等于参数元素的下标
    • lastIndexOf(Object): 返回列表中最初一个等于参数元素的下标

  • 列表迭代器（List Iterators）

    ListIterator是List接口提供非凡的Iterator，容许元素插入、替换操作，除了Iterator惯例的操作外还能够反对双向拜访。

    • listIterator():返回ListIterator对象，下标从第一个元素开始
    • listIterator(int)：返回ListIterator对象，下标从指定元素地位开始

  • 视图（View）

    • subList(int,int)：返回list中指定局部的视图，蕴含fromIndex，不蕴含toIndex，如果二者相等，则返回空。

AbstractList

概述

AbstractList继承抽象类AbstractCollection，实现了List接口中的大部分办法，反对随机拜访（random access），对于须要程序拜访（sequential access）的数据，优先用子类抽象类AbstractSequentialList的实例

  • 子类按可变性分类

    • 不可批改list：如果要实现一个不可批改的list，那么子类只须要实现get和size办法；
    • 可批改list：如果要实现一个可批改的的list，除了get和size办法，子类还须要笼罩set办法；如果可扭转的list是变长的，还须要笼罩add和remove办法。

  • 迭代器实现

    • Iterator

      对外提供hasNext、next、remove办法。remove办法不是线程平安的，但提供了根本的fast-fail性能，只管多线程下存在肯定缺点。具体如下：

      private class Itr implements Iterator<E> {        /**         * Index of element to be returned by subsequent call to next.         */        int cursor = 0;        /**         * Index of element returned by most recent call to next or         * previous.  Reset to -1 if this element is deleted by a call         * to remove.         */        int lastRet = -1;        /**         * The modCount value that the iterator believes that the backing         * List should have.  If this expectation is violated, the iterator         * has detected concurrent modification.         */        int expectedModCount = modCount;        public boolean hasNext() {            return cursor != size();        }        public E next() {            checkForComodification();            try {                int i = cursor;                E next = get(i);                lastRet = i;                cursor = i + 1;                return next;            } catch (IndexOutOfBoundsException e) {                checkForComodification();                throw new NoSuchElementException();            }        }        public void remove() {            if (lastRet < 0)                throw new IllegalStateException();            checkForComodification();            try {                AbstractList.this.remove(lastRet);                if (lastRet < cursor)                    cursor--;                lastRet = -1;                expectedModCount = modCount;            } catch (IndexOutOfBoundsException e) {                throw new ConcurrentModificationException();            }        }        final void checkForComodification() {            if (modCount != expectedModCount)                throw new ConcurrentModificationException();        }    }

      AbstractList 通过外部成员变量 modCount 来记录list的长度发生变化的次数，例如add和remove办法会扭转list的长度，modCount 的值会随之减少。

      Itr 通过成员变量expectedModCount来记录list以后的modCount值，调用next和remove办法时，首先会查看迭代器中的存储的expectedModCount是否等于以后list的modCount值：

      • 若不等于，阐明迭代器再操作list的过程中，list的长度产生了变动，并发批改list长度可能会引起数据的不统一，抛出ConcurrentModificationException
      • 若等于，则继续执行后续逻辑；但expectedModCount等于以后list的modCount未必就代表没有并发问题。例如，当程序执行到 AbstractList.this.remove(lastRet); 时，CPU工夫片到，切换到其它线程执行类remove或add操作，而后切换回以后线程的时候 执行了 expectedModCount = modCount; 此时并没有做到疾速失败。ListItr中的set和add办法存在相似问题。

      思考：为什么 Itr 不在迭代器中存储list的size，通过比拟迭代器中的size和内部size是否相等来进行fast-fail ？

      答复：因为存在ABA问题。相连的remove和add操作会导致最终size相等，然而list的长度已产生扭转。

    • ListIterator

      ListIterator继承自Iterator接口，提供add、set办法用于元素的插入、替换，通过hasPrevious、previous、nextIndex、previousIndex反对双向拜访。

形象办法
  • get(int) : 源自List接口。依据下标获取元素
  • size()：源自Collection接口。获取list元素数量
具体方法
  • add(E) : 调用add(size(), e)实现往list尾部增加元素；
  • add(int,E) ： 默认抛出UnsupportedOperationException异样
  • addAll(int,Collection)：从指定下标开始，调用add(int,E)将参数汇合的元素一一退出list
  • set(int,E) ： 默认抛出UnsupportedOperationException异样
  • remove(int)： 默认抛出UnsupportedOperationException异样
  • indexOf(Object)：应用迭代器listIterator，从list头部查问第一个相等元素的下标，object可为null
  • lastIndexOf(Object)：应用迭代器listIterator，从list尾部查问最初一个相等元素的下标，object可为null
  • clear()：调用removeRange(0,size())删除所有元素
  • iterator()：返回外部公有类Itr的实例
  • listIterator()： 返回外部公有类ListItr的实例，默认从list首部开始遍历
  • listIterator(int)：返回外部公有类ListItr的实例，参数指定了从list的开始遍历的地位
  • subList(int,int)：返回SubList类的实例，该实例外部存储了list的实例，用于查看或操作list的指定下标区间的元素
  • equals(Object)：判断是否相等；若指向同一对象则返回true；若参数不是List的实例则返回false；若参数是list，则程序比对两个list中对应地位的元素，如有一个equal为false则返回false，否则为true

  • hashCode()：计算形式如下

        /**     * Returns the hash code value for this list.     *     * <p>This implementation uses exactly the code that is used to define the     * list hash function in the documentation for the {@link List#hashCode}     * method.     *     * @return the hash code value for this list     */    public int hashCode() {        int hashCode = 1;        for (E e : this)            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());        return hashCode;    }
  • removeRange(int,int)：protected办法；删除指定区间内的元素

AbstractSequentialList

概述

该类反对程序拜访（sequential access），对于随机拜访（random access）的数据，应用父类AbstractList存储。

所有子类都必须实现ListIterator办法和size办法，按可变性来说，对子类要求如下：

  • 不可批改list：如果要实现一个不可批改的list，那么子类须要实现ListIterator中的hasNext、next、hasPrevious、previous、index办法；
  • 可批改list：如果要实现一个可批改的list，除不可批改中形容的办法外，还必须实现ListIterator中的set办法；如果list是变长的，还须要实现ListIterator中的add和remove办法。
形象办法

  • listIterator(int)：源自List接口。获取迭代器对象。此类的ListIterator实现与父类AbstractList中的ListIterator实现不同：

    • AbstractList提供了迭代器ListIterator的具体实现类ListItr，AbstractList的listIterator办法不是形象办法；而AbstractSequentialList不提供迭代器ListIterator的具体实现，须要子类必须实现
    • AbstractList提供的迭代器ListIterator默认实现ListItr中的next、set、add、remove办法依赖于AbstractList类的get、set、add、remove办法；
    • AbstractSequentialList中的提供的get、set、add、remove办法实现，依赖于ListIterator的next、set、add、remove办法
  • size()：源自Collection接口。获取list元素数量
具体方法
  • get(int) : 依据指定下标获取元素。该办法调用listIterator(int).next()实现
  • add(int,E) ：在指定下标后，增加元素。该办法调用listIterator(int).add(E)实现
  • addAll(int,Collection)：从指定下标后，增加汇合元素。调用listIterator(int)获取迭代器，而后遍历参数汇合，一一调用迭代器的add(E)办法增加汇合元素
  • set(int,E) ： 替换指定地位的元素。该办法调用listIterator(int).next()获取老值，调用listIterator(int).set(E)来实现替换
  • remove(int)： 删除指定地位的元素。该办法调用listIterator(int).next()获取老值，调用listIterator(int).remove()来实现删除

Queue

jdk1.5新增此接口，继承Collection接口的所有办法，另外新增下图中所圈的办法。

各个实现类的实现原理和用处

add(E): 在队列尾部新增元素。如果减少胜利就返回true；如果以后没有空间导致减少失败，抛出 IllegalStateException异样；

offer(E): 在队列尾部新增元素。如果减少胜利就返回true; 如果以后没有空间导致减少失败，返回false；

remove(): 获取并删除队列头部元素。如果队列为空，则抛出NoSuchElementException异样；

poll(): 获取并删除队列头部元素。如果队列为空，则返回null；

element(): 获取但不删除队列头部元素。如果队列为空，则抛出NoSuchElementException异样；

peek(): 获取但不删除队列头部元素。如果队列为空，则返回null。

AbstractQueue

概述

继承AbstractCollection类的抽象类，实现Queue接口，笼罩AbstractCollection的add(E)、clear()、addAll(Collection<? extends E>) 办法。

继承该类的子类，不容许往队列中插入null元素

没有实现Queue接口的offer(E)、poll()、peek()办法。

形象办法
  • offer(E)：源自Queue接口。在队列尾部新增元素。如果减少胜利就返回true; 如果以后没有空间导致减少失败，返回false
  • poll()：源自Queue接口。获取并删除队列头部元素。如果队列为空，则返回null；
  • peek()：源自Queue接口。获取但不删除队列头部元素。如果队列为空，则返回null。
  • size()：源自Collection接口。获取队列元素数量。
  • iterator()：源自Iterable接口。获取迭代器对象。
具体方法
  • add(E)：在队列尾部增加元素。具体实现依赖子类实现的offer(E)，如果offer(E)返回false，则抛出IllegalStateException异样
  • addAll(Collection<? extends E>) ：在队列尾部增加汇合。具体实现是遍历传入的汇合，调用add(E)增加汇合中的元素，增加结束后，如果有一个增加胜利就返回true。
  • remove()：获取并删除队列头部元素。具体实现依赖子类实现的poll()，如果poll()返回null，则抛出NoSuchElementException异样
  • element()：获取但不删除队列头部元素。具体实现依赖子类实现的peek()，如果peek()返回null，则抛出NoSuchElementException异样
  • clear()：删除队列中的所有元素。具体实现是循环调用poll()，直到poll()返回null

Deque

  • 双端队列，Deque来源于double ended queue的缩写，发音“deck”。
  • 不同于List，Deque不反对随机拜访；
  • 只管Deque接口没有禁止插入null，然而具体实现应该禁止插入null，因为Deque的办法返回null个别用来示意队列为空。
  • jdk1.6新增此接口，继承Queue接口的所有办法，另外新增下图中所圈的办法。

办法阐明

  • Deque接口对队列元素提供的插入、删除、查看操作，对于每种操作Deque别离提供队列头操作、对列尾操作，对于每个这样的操作，又别离提供抛出异样和返回指定值的办法，具体如下：
<caption>Summary of Deque methods</caption>
First Element (Head)Last Element (Tail)
Throws exceptionSpecial valueThrows exceptionSpecial value
InsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)
RemoveremoveFirst()pollFirst()removeLast()pollLast()
ExaminegetFirst()peekFirst()getLast()peekLast()
  • Deque被当作队列（先进先出 FIFO）应用时，在队列尾部增加元素，在队列头部获取元素，与Queue接口的办法有如下对应关系：
<caption>Comparison of Queue and Deque methods</caption>
Queue MethodEquivalent Deque Method
add(e)addLast(e)
offer(e)offerLast(e)
remove()removeFirst()
poll()pollFirst()
element()getFirst()
peek()peekFirst()
  • Deque被当作栈（后进先出 LIFO）应用时，在栈头部增加并获取元素，相似于类Stack的实现，与Stack接口的办法有如下对应关系：
<caption>Comparison of Stack and Deque methods</caption>
Stack MethodEquivalent Deque Method
push(e)addFirst(e) or push(e)
pop()removeFirst() or pop()
peek()peekFirst()
  • removeFirstOccurrence(Object）：从对队列头部删除第一个匹配元素。如果存在这样的元素被删除则返回true，否则返回false
  • removeLastOccurrence(Object）：从队列尾部删除第一个匹配元素。如果存在这样的元素被删除则返回true，否则返回false
  • descendingIterator()：返回反序的迭代器。iterator()返回的迭代器是从队列头到队列尾遍历，descendingIterator()返回的迭代器，是从队列尾到队列头遍历

Map

Map中存储键值对，键不能够反复，每一个键至少对应一个值。

如果将可变对象作为键，必须十分音讯。以后Map不容许将本身作为键，但能够将本身作为值。

办法阐明

Map接口办法如下（不蕴含默认办法）：

  • 查问操作（Query Operations）

    • size()：返回键值对的数量。
    • isEmpty()：如果Map中没有键值对，返回true。
    • containsKey(Object)：如果Map中蕴含指定Key，返回true。比拟Key相等条件：key==null ? k==null : key.equals(k)
    • containsValue(Object)：如果Map中蕴含一个或更多key对应指定Value，返回true。比拟Value相等条件：value==null ? v==null : value.equals(v)，对于大多数实现来说，这个操作可能须要基于size()的线性工夫
    • get(Object)：返回参数Key对应的Value，如果以后汇合不存在则返回null。如果参数Key为null，而具体实现不容许Key为null，则抛出NullPointerException

  • 批改操作（Modification Operations）

    • put(K , V )：将指定Key与指定Value相关联，如果以后Map中不存在该Key则插入，如果存在该Key，则替换对应的Value。如果参数Key为null，而具体实现不容许Key为null，则抛出NullPointerException
    • remove(Object)：删除以后Map中指定Key的键值对。

  • 批量操作（Bulk Operations）

    • putAll(Map<? extends K, ? extends V>)：将参数Map中的键值对，复制到以后Map。
    • clear()：删除所有键值对。

  • 视图（Views）

    • keySet()：返回以后Map所有Key组成的Set。Map中Key的扭转会影响到该Set，反之亦然。返回的Set反对remove操作，但不反对add或addAll操作。删除Set中的某个元素，会删除Map中该元素对应的键值对。
    • values()：返回以后Map所有Value组成的汇合。Map中Value的扭转会影响到该汇合，反之亦然。返回的汇合反对remove操作，但不反对add或addAll操作。删除汇合中的某个元素，会删除Map中该元素对应的键值对。
    • entrySet()：返回以后Map所有Entry组成的Set。Map中Entry的扭转会影响到该Set，反之亦然。返回的Set反对remove操作，但不反对add或addAll操作。删除Set中的某个元素，会删除Map中该元素对应的键值对。

  • 比拟和哈希（Comparison and hashing）

    • equals(Object)：如果两个Map相等则返回true。判断两个Map对象m1和m2相等的根据是m1.entrySet().equals(m2.entrySet())，这样的实现保障了即使是m1和m2的有具体不同的实现类，equels办法也能够比拟。
    • hashCode()：返回以后Map的哈希值。以后Map的哈希值，是entrySet()中元素的哈希值之和。

Entry

Entry是Map接口的内置接口，每对键值对应一个Entry对象。Map的entrySet()返回蕴含Entry对象的Set。通过Entry能够间接批改Map。

办法阐明（不含默认办法）
  • getKey()：返回以后Entry对应的Key。
  • getValue()：返回以后Entry对应的Value。
  • setValue()：替换以后Entry对应的Value。
  • equals(Object)：比拟以后Entry与参数对象是否相等。如果参数对象也是Entry，比拟形式：(e1.getKey()==null ? e2.getKey()==null : e1.getKey().equals(e2.getKey())) && (e1.getValue()==null ? e2.getValue()==null : e1.getValue().equals(e2.getValue()))
  • hashCode()：返回以后Entry的哈希值。计算形式：(e.getKey()==null ? 0 : e.getKey().hashCode()) ^(e.getValue()==null ? 0 : e.getValue().hashCode())

AbstractMap

概述

抽象类AbstractMap实现Map接口，所有具体方法均依赖形象办法entrySet()。

形象办法
  • entrySet：返回以后Map所有Entry组成的Set。Map中Entry的扭转会影响到该Set，反之亦然。返回的Set反对remove操作，但不反对add或addAll操作。删除Set中的某个元素，会删除Map中该元素对应的键值对。
具体方法

所有具体方法均依赖entrySet的实现。

  • keySet()：返回以后Map所有Key组成的Set。Map中Key的扭转会影响到该Set，反之亦然。返回的Set反对remove操作，但不反对add或addAll操作。删除Set中的某个元素，会删除Map中该元素对应的键值对。具体实现：外部结构一个AbstractSet对象，AbstractSet实现的新创建的iterator对象，实际操作的是entrySet返回的迭代器，具体代码如下：

        public Set<K> keySet() {        Set<K> ks = keySet;        if (ks == null) {            ks = new AbstractSet<K>() {                public Iterator<K> iterator() {                    return new Iterator<K>() {                        private Iterator<Entry<K,V>> i = entrySet().iterator();                        public boolean hasNext() {                            return i.hasNext();                        }                        public K next() {                            return i.next().getKey();                        }                        public void remove() {                            i.remove();                        }                    };                }                public int size() {                    return AbstractMap.this.size();                }                public boolean isEmpty() {                    return AbstractMap.this.isEmpty();                }                public void clear() {                    AbstractMap.this.clear();                }                public boolean contains(Object k) {                    return AbstractMap.this.containsKey(k);                }            };            keySet = ks;        }        return ks;    }

  • values()：返回以后Map所有Value组成的汇合。Map中Value的扭转会影响到该汇合，反之亦然。返回的汇合反对remove操作，但不反对add或addAll操作。删除汇合中的某个元素，会删除Map中该元素对应的键值对。具体实现：外部结构一个AbstractCollection对象，AbstractCollection实现的新创建的iterator对象，实际操作的是entrySet返回的迭代器，具体代码如下：

        public Collection<V> values() {        Collection<V> vals = values;        if (vals == null) {            vals = new AbstractCollection<V>() {                public Iterator<V> iterator() {                    return new Iterator<V>() {                        private Iterator<Entry<K,V>> i = entrySet().iterator();                        public boolean hasNext() {                            return i.hasNext();                        }                        public V next() {                            return i.next().getValue();                        }                        public void remove() {                            i.remove();                        }                    };                }                public int size() {                    return AbstractMap.this.size();                }                public boolean isEmpty() {                    return AbstractMap.this.isEmpty();                }                public void clear() {                    AbstractMap.this.clear();                }                public boolean contains(Object v) {                    return AbstractMap.this.containsValue(v);                }            };            values = vals;        }        return vals;    }