关系总览
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; }