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): 返回列表中最后一个等于参数元素的下标
【java集合概述】列表迭代器（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 { /** * 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. * * 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) 方法。
继承该类的子类，不允许往队列中插入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) ：在队列尾部添加集合。具体实现是遍历传入的集合，调用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分别提供队列头操作、对列尾操作，对于每个这样的操作，又分别提供抛出异常和返回指定值的方法，具体如下：

Summary of Deque methods
	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接口的方法有如下对应关系：

Comparison of Queue and Deque methods
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接口的方法有如下对应关系：

Comparison of Stack and Deque methods
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=https://www.it610.com/article/=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)：将参数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 keySet() { Set ks = keySet; if (ks == null) { ks = new AbstractSet() { public Iterator iterator() { return new Iterator() { private Iterator> 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 values() { Collection vals = values; if (vals == null) { vals = new AbstractCollection() { public Iterator iterator() { return new Iterator() { private Iterator> 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; }