JAVA集合复习-接口

java集合

一：总览

上述类图中，实线边框的是实现类，比如ArrayList，LinkedList，HashMap等，折线边框的是抽象类，比如AbstractCollection，AbstractList，AbstractMap等，而点线边框的是接口，比如Collection，Iterator，List等。

主要接口：iterator，listiterator(图片有错误)，collection，map，list，set，queue，sortedmap，sortedset……

抽象类：abstractcollection，abstractlist，abstractset，abstractmap，abstractsequentiallist

实现类（主要掌握）：arraylist，linkedlist，hashset，treeset，linkedhashset，hashmap，treemap，linkedhashmap。

二：详解

接口

iterator接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}
//请求一个迭代器
Collection<String> c = . . .;
Iterator<String> iter = c.iteratorO；
while (iter.hasNextO)
{
String element = iter.next0；
do something with element
}
//使用for each 必须实现Iterable接口
for (String element : c)
{
do something with element
}
//使用lambda表达式
iterator.forEachRemaining(element -> dosomething with element);

• boolean hasNext()
如果存在可访问的元素， 返回 true。
• E next()
返回将要访问的下一个对象。 如果已经到达了集合的尾部， 将拋出一个 NoSuchElementException。
• void remove( )
删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后，集合已经发生了变化， 这个方法将抛出一个 IllegalStateException。

iterator 接口的 remove 方法将会删除上次调用 next 方法时返回的元素。

只能向前遍历，无法反向。

应该将 Java 迭代器认为是位于两个元素之间。 当调用 next 时，迭代器就越过下
一个元素，并返回刚刚越过的那个元素的引用。

Iterable接口

1
2
3

public interface Iterable<T> {
    Iterator<T> iterator();
}

所有的集合类（List、Set…）都实现自Collection 接口，而Collection 接口又继承于Iterable 接口，因此可以说所有的集合类（List、Set…）都实现了Iterable 接口。

当某个类实现Iterable接口时，我们就能称这个类是一个“可数”的类，也就是可以使用iterator()获取一个迭代器Iterator，然后使用这个Iterator实例去遍历这个类，因此所有的Collection类都能够使用迭代器Iterator来遍历。

如果某个类实现了Iterable 接口，那么他也需要创建一个内部类去实现一个Iterator 类，让调用Iterable 接口中的iterator() 时，能够获取到一个iterator 实例。

而再进一步说，当某个类能使用迭代器Iterator来遍历时，就能使用java提供的foreach语法糖来遍历此类（foreach语法糖其实就是简化的iterator()）

foreach实际上会被编译器编译成使用迭代器iterator()去遍历集合，因此能使用foreach的，都是得实现Iterable接口的集合类Collection们，像是List、Set

所以Map就没有办法直接使用foreach（因为Map没有实现Iterable接口），只有他的map.entrySet()、map.keySet()、map.values()这种返回一个集合类的方法，才能使用foreach。

• 为什么Iterator 要额外使用内部类去实现，而不是ArrayList 直接实现此接口 ?

  • 如果看过Collection类的源码（以ArrayList为例），可以发现ArrayList类并不是由ArrayList去实现Iterator接口，而是ArrayList有一个内部类Itr，专门去实现Iterator接口，而ArrayList的iterator()方法，只是去创建一个内部类ArrayList.Itr的实例而已

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    //ArrayList不實現Iterator接口，反而是由他的內部類進行實現 public class ArrayList<E> extends AbstractList<E> { //調用list.iterator()可以取得此list的迭代器 public Iterator<E> iterator() { return new Itr(); //實際上就是去創建一個內部類的實例 } //ArrayList中的內部類Itr，專門實現Iterator接口 private class Itr implements Iterator<E> { int cursor; //記錄當前迭代到哪裡 public boolean hasNext() { ... } public E next() { ... } public void remove() { ... } } }

  • 要这样设计是因为一个集合类可能同时有多个迭代器去遍历他，而每个迭代器遍历到集合的哪里，是每个迭代器自己的事情，彼此不互相干涉，因此才需要额外使用一个内部类去实现迭代器的Iterator 接口

    • 如此当需要用到Iterator来遍历集合时，只需要调用list.iterator()，就能取得一个全新的、不受别人影响的迭代器供自己使用，而迭代器彼此之间也不会互相干涉
    • 至于为什么要特别使用内部类来实现Iterator接口，而不是创建一个Iterator公共类来供所有集合一起使用，是因为迭代器需要知道集合的内部结构，他才能知道要怎么去实现hasNext()、next()、remove()方法，而使用内部类才能无条件的取用外部类的所有信息（包含private的变量和方法），因此才需要将Iterator提取成接口，让每个集合自己使用内部类去实现Iterator接口

• 为什么Iterator接口，只有hasNext()、next()、remove()方法，而没有add(E)方法?

  • 逻辑上来说，迭代器是一个一个去遍历集合中的元素，而当前iterator 停下的地方，就是迭代到一半的地方
    • 如果当迭代到一半时调用iterator.add()方法，理论上来说，应该是要在当前这个元素E1后面新增一个元素E2，使得下次遍历此集合时，E2一定会出现在E1后面，也就是[….E1 , E2, ….]
    • 假设add()方法是以这个语意为前提的话，那么迭代器不提供此方法是很合理的，对于有序的集合（像是ArrayList）来说，在此元素后面新增一个元素是一个很简单的事情，但是对于无序的集合（像是HashSet）来说，不能保证新插入的这个元素E2一定会在E1后面（因为还得计算HashCode），如此就违反了add()的语意了，这也就是为什么Iterator接口不提供add()方法
  • 另一个说法是，在使用迭代器时，通常就是“遍历”的场景，这种场景下很少会去使用add()方法，因此Iterator接口没必要提供这个方法

listiterator接口

参考：https://www.yiibai.com/java/java-listiterator.html

它从Java 1.2开始提供。

它扩展了Iterator接口。

它仅对List实现的类有用。

与Iterator不同，它支持所有四种操作：CRUD(CREATE，READ，UPDATE和DELETE)。支持add操作。add方法只依赖于迭代器的位置(在光标前插入)， 而 remove 方法依赖于迭代器的状态(删除刚刚越过的元素)。set 方法用一个新元素取代调用 next 或 previous 方法返回的上一个元素。

与Iterator不同，它支持正向和反向迭代。

它是一个双向迭代器。

它没有当前元素; 它的光标位置总是位于调用previous()返回的元素和调用next()返回的元素之间。

Java ListIterator接口具有以下方法。

RandomAccess接口

这个接口不包含任何方法， 不过可以用它来测试一个特定的集合是否支持高效的随机访问：

Collection 接口

详细可参考：https://www.jianshu.com/p/b878a4e1c762

• Iterator iterator()
返回一个用于访问集合中每个元素的迭代器。
• int size()
返回当前存储在集合中的元素个数。
• boolean isEmpty()
如果集合中没有元素， 返回 true。
• boolean contains(Object obj)
如果集合中包含了一个与 obj 相等的对象， 返回 true。
• boolean containsAl 1(Collection other) 如果这个集合包含 other 集合中的所有元素， 返回 trueo • boolean add(Object element) 将一个元素添加到集合中。如果由于这个调用改变了集合，返回 true。 • boolean addAl 1(Col 1 ection other) 将 other 集合中的所有元素添加到这个集合。 如果由于这个调用改变了集合， 返回 true。 • boolean remove(Object obj) 从这个集合中删除等于 obj 的对象。 如果有匹配的对象被删除， 返回 true。 • boolean removeAl 1(Col 1ection other)
从这个集合中删除 other 集合中存在的所有元素。如果由于这个调用改变了集合，返回 true。
• default boolean removelf(Predicate filter)8 从这个集合删除 filter 返回 true 的所有元素。 如果由于这个调用改变了集合， 则返回 true。 • void clear() 从这个集合中删除所有的元素。 • boolean retainAl 1(Collection other)
从这个集合中删除所有与 other 集合中的元素不同的元素。 如果由于这个调用改变了
集合， 返回 true。
• Object[]toArray()
返回这个集合的对象数组。
• T[]toArray(T[] arrayToFi11)
返回这个集合的对象数组。 如果 arrayToFill 足够大， 就将集合中的元素填入这个数组
中。剩余空间填补 null ; 否则， 分配一个新数组， 其成员类型与 arrayToFill 的成员类
型相同， 其长度等于集合的大小， 并填充集合元素。

list接口

在collection的基础上添加了扩展方法，

• ListIterator 1istIterator( )
返回一个列表迭代器， 以便用来访问列表中的元素。
• ListIterator 1istIterator(int index )
返回一个列表迭代器， 以便用来访问列表中的元素， 这个元素是第一次调用 next 返回的给定索引的元素。
• void add( int i ,E element )
在给定位置添加一个元素。
• void addAll ( int i ,Collection<? extends E> elements )
将某个集合中的所有元素添加到给定位置。
• E remove( int i )
删除给定位置的元素并返回这个元素。
• E get( int i )
获取给定位置的元素。
• E set(int i ,E element )
用新元素取代给定位置的元素， 并返回原来那个元素。
• int indexOf( Object element )
返回与指定元素相等的元素在列表中第一次出现的位置， 如果没有这样的元素将返回-1。
• int 1 astlndexOf(Object element)
返回与指定元素相等的元素在列表中最后一次出现的位置， 如果没有这样的元素将返
回 -U

set接口

参考：https://www.yiibai.com/java/java_set_interface.html

Set是一个不能包含重复元素的Collection。它模拟了数学集合抽象。

Set接口仅包含从Collection接口继承的方法，并添加禁止重复元素的限制。

Set还为equals和hashCode操作的行为添加了一个更强的规范，允许Set实例有意义地进行比较，即使它们的实现类型不同。

Set声明的方法如下表中所示 -

和list对比：

1、List 接口能直接设置或获取某个元素的值，而Set接口不能。

2、List 接口能直接在指定位置删除、增加元素，而Set接口不能。

3、List 接口有 listIterator 方法，可以获得 ListIterator 对象，而 Set 接口不能。Set 只能通过 iterator 迭代的方式获取元素。

sortedset接口

参考：https://www.yiibai.com/java/java_sortedset_interface.html

SortedSet接口扩展Set接口并声明按升序排序的集合的行为。除了Set定义的那些方法之外，SortedSet接口还声明了一些自己的方法。

SortedSet 和 SortedMap 接口会提供用于排序的比较器对象，这两个接口定义了可以得到
集合子集视图的方法。

当调用集中没有包含任何项时，有几种方法抛出NoSuchElementException异常。当对象与集合中的元素不兼容时，抛出ClassCastException异常。

如果尝试使用null对象并且集合中不允许null，则抛出NullPointerException异常。

NavigableSet接口

• E higher(E value)
• E lower(E value)
返回大于 value 的最小元素或小于 value 的最大元素，如果没有这样的元素则返回 null。
• E ceiling(E value)
• E floor(E value)
返回大于等于 vaiue 的最小元素或小于等于 value 的最大元素， 如果没有这样的元素
则返回 null。
• E pollFirst()
• E pollLast
删除并返回这个集中的最大元素或最小元素， 这个集为空时返回 null。
• Iterator descendingIterator()
返回一个按照递减顺序遍历集中元素的迭代器。

queue接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public interface Queue<E> extends Collection<E> {
    //....
    //extend correction 具有集合的基本功能
    // 添加一个元素到队列，在先进先出队列中，是添加到队列尾部
    // 如果由于容量不足插入失败，则抛出异常，不会返回false
    boolean add(E e);
    
    // 和add方法一样，不过不同之处在于，这个方法添加失败一般是返回false，而不是抛出异常
    boolean offer(E e);
    
    // 移除队列尾部的元素（最后进来的元素），如果队列为空，则抛出异常，不返回false
    E remove();

    // 和remove方法一样，不过这个方法在队列为空时会返回false，不抛出异常
    E poll();

    // 查看队列头部的元素（最先进来的元素），如果队列为空，则抛出异常，不返回null
    E element();
    
    // 和element方法一样，不过这个在队列为空时，返回null，不抛出异常
    E peek();
}

• boolean add(E element )
• boolean offer(E element )
如果队列没有满，将给定的元素添加到这个双端队列的尾部并返回 true。如果队列满
了，第一个方法将拋出一个 IllegalStateException, 而第二个方法返回 false。
• E remove( )
• E poll ( )
假如队列不空， 删除并返回这个队列头部的元素。 如果队列是空的，第一个方法抛出
NoSuchElementException, 而第二个方法返回 null。
• E element( )
• E peek( )
如果队列不空，返回这个队列头部的元素， 但不删除。 如果队列空，第一个方法将拋
出一个 NoSuchElementException, 而第二个方法返回 null。

在JDK里面没有一个队列的实现是仅仅实现Queue接口定义的功能。可能是因为具有基本功能的队列实现比较简单而且实际的用途有点少。队列的实现基本可以分为：1.并发队列(ConcurrentLinkedQueue); 2.阻塞队列（ArrayBlockingQueue， LinkedBlockingQueue）； 3.双端队列（Deque, ArrayDeque, LinkedList, ConcurrentLinkedDeque）; 4:优先级队列(PriorityQueue, PriorityBlockingQueue) 每种类型的队列都是针对不同的应用场景的，所以还是需要仔细区分来选择合适的队列实现。

deque接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public interface Deque<E> extends Queue<E> {
    // *** Deque methods ***
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
    
    // *** Queue methods ***
    boolean add(E e);
    boolean offer(E e);
    E remove();        
    E poll();
    E element();
    E peek();
    
    // *** Stack methods ***
    void push(E e);
    E pop();

    // *** Collection methods ***
    boolean remove(Object o);
    boolean contains(Object o);
    public int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

Deque表示双端队列。双端队列是在两端都可以进行插入和删除的队列。Deque是一个比Stack和Queue功能更强大的接口，它同时实现了栈和队列的功能。ArrayDeque和LinkeList实现了Deque接口。

注意：Deque既可以用作后进先出的栈，也可以用作先进先出的队列。

表：Deque接口方法表

表：Deque与Queue方法比较表

插入

addFirst和offerFirst在Deque实例头部插入元素。
addLast和offerLast在Deque实例尾部插入元素。
当Deque实现类为有限容量时，优先使用offerFirst和offerLast，因为addFirst在队列满的时候可能会插入失败而抛出异常。

删除

removeFirst和pollFirst从Deque实例头部移除元素。
removeLast和pollLast从Deque实例尾部移除元素。
当Deque为空时，pollFirst和pollLast将会返回null，而removeFirst和removeLast将会抛出异常。

检索

getFirst和peekFirst获取Deque实例的第一个元素，但是不会将元素从Deque实例中删除。类似地，getLast和peekLast获取最后一个元素。当Deque为空时，getFirst和getLast将会抛出异常，而peekFirst和peekLast将会返回null。

除了基本的插入、删除和检索方法外，还有两个预定义的方法：removeFirstOccurence和removeLastOccurence。这两个方法见名知意。返回true的时候表示元素存在于队列，并且已经被删除。返回false时表示元素不存在于队列中，并且队列没有改变。

map接口

Map集合的特点是：通过key值找到对应的value值，key值是唯一的，value可以重复。Map中的元素是无序的，但是也有实现了排序的Map实现类，如：TreeMap。

上面Map接口提供的方法大致可以分为下面几种：

1、put/putAll/remove/clear 增加删除 get/values 获取值

2、containKey/containValue 判断

3、entrySet/keySet 获取迭代

4、equals/hashcode 比较

基本上所有的 Map 接口实现类都使用 put() 方法存入数据、用get() 方法去除数据，使用 entrySet/keySet 迭代获取 Map 数据。

sortedmap接口

SortedSet 和 SortedMap 接口会提供用于排序的比较器对象，这两个接口定义了可以得到
集合子集视图的方法。

TreeMap实现了SortedMap接口，保证了有序性。默认的排序是根据key值进行升序排序，也可以重写comparator方法来根据value进行排序。

SortedMap接口扩展了Map接口，它确保条目按升序键维护。

当调用映射中没有项时，有几种方法会抛出NoSuchElementException异常。当对象与映射中的元素不兼容时，抛出ClassCastException异常。如果在映射中不允许null时，如果尝试使用null对象，则抛出NullPointerException异常。

SortedMap接口声明的方法如下表中所示 -

navigablemap接口

NavigableSet扩展了 SortedSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

SortedMap提供了获取最大值与最小值的方法，但对于一个已经排序的数据集，除了最大值与最小值之外，
我们还想对任何一个元素，找到比它小的值和比它大的值，还可以按照原有的顺序倒序排序等，
这时候就运用到NavigableMap接口提供的如下方法。

// 找到第一个比指定的key小的值
Map.Entry<K,V> lowerEntry(K key);

// 找到第一个比指定的key小的key
K lowerKey(K key);

// 找到第一个小于或等于指定key的值
Map.Entry<K,V> floorEntry(K key);

// 找到第一个小于或等于指定key的key
K floorKey(K key);

//  找到第一个大于或等于指定key的值
Map.Entry<K,V> ceilingEntry(K key);

//找到第一个大于或等于指定key的key
K ceilingKey(K key);

// 找到第一个大于指定key的值
Map.Entry<K,V> higherEntry(K key);

//找到第一个大于指定key的key
K higherKey(K key);

// 获取最小值
Map.Entry<K,V> firstEntry();

// 获取最大值
Map.Entry<K,V> lastEntry();

// 删除最小的元素
Map.Entry<K,V> pollFirstEntry();

// 删除最大的元素
Map.Entry<K,V> pollLastEntry();

//返回一个倒序的Map
NavigableMap<K,V> descendingMap();

// 返回一个Navigable的key的集合，NavigableSet和NavigableMap类似
NavigableSet<K> navigableKeySet();

// 对上述集合倒序
NavigableSet<K> descendingKeySet();