共计 13436 个字符，预计需要花费 34 分钟才能阅读完成。
关系总览
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 别离提供队列头操作、对列尾操作，对于每个这样的操作，又别离提供抛出异样和返回指定值的办法，具体如下：
| First Element (Head) | Last Element (Tail) | |||
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
- Deque 被当作队列（先进先出 FIFO）应用时，在队列尾部增加元素，在队列头部获取元素，与 Queue 接口的办法有如下对应关系：
| Queue Method | Equivalent Deque Method |
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
- Deque 被当作栈（后进先出 LIFO）应用时，在栈头部增加并获取元素，相似于类 Stack 的实现，与 Stack 接口的办法有如下对应关系：
| Stack Method | Equivalent 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; }
