关于java:java集合概述

关系总览

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 别离提供队列头操作、对列尾操作，对于每个这样的操作，又别离提供抛出异样和返回指定值的办法，具体如下：

• Deque 被当作队列（先进先出 FIFO）应用时，在队列尾部增加元素，在队列头部获取元素，与 Queue 接口的办法有如下对应关系：

• Deque 被当作栈（后进先出 LIFO）应用时，在栈头部增加并获取元素，相似于类 Stack 的实现，与 Stack 接口的办法有如下对应关系：

• 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;
      }