3-2-集合

发表于 更新于

集合

介绍标准库中的集合类

Java集合类库也将接口(interface)与实现(implementation)分离

集合接口

队列接口指出可以在队列的尾部添加元素，在队列的头部删除元素，并且可以插在队列中元素的个数。

当需要收集对象，同时按照"先进先出"原则检索对象时，这个时候就应该使用队列

给出一个最简单形式的队列 接口(interface)

1
2
3
4
5
6
//给出一个最简单形式的循环数组队列
public interface Queue<E>{
    void add(E element);
    E remove();
    int size();
}

队列通常有两种实现方式：一种是使用循环数组。另外一种是使用链表

可以看Java.util包中给出的Queue接口

1
2
3
4
5
6
7
8
9
10
package java.util;

public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

在程序中使用队列时可以使用接口类型来存放集合引用。这样，一旦程序员改变了想法，想要改用另外一种不同的实现，就可以很轻松的切换过去，只有做出一点点修改

1
2
Queue<Customer> expresslane = new CirrularArrayQueue<>(100);
expresslane.add(new Customer("Herry"));

例如当程序员想要换为链表的实现时，只需一点改动：

1
2
Queue<Customer> expresslane = new LinkListQueue<>(100);
expresslane.add(new Customer("Herry"));

循环数组要比链表更高效，大多数人会优先选择循环数组。但这也需要付出一定的代价。所以也会存在切换为链表实现的情况。

Collection接口

Java类库中，集合类的基本接口是Collection接口。Java集合类库中，除Map结尾的类之外，其他的类都实现了Collection接口

1
2
3
4
5
public interface Collection<E>{
    boolean add(E element);
    Interator<E> iterator();
    ...
}

这里介绍其中的两个方法。

add方法用于向集合中添加元素。如果添加元素确实改变了集合就返回true；如果集合没有发生变化就返回false。

例如，当我们试图向集合(set)中添加一个对象，而这个对象已经在集中存在，集合中不允许存在重复的对象，所以就返回false

iterator方法用于返回一个实现了Iterator接口的对象。可以使用这个迭代器对象来依次访问集合中的元素。

迭代器

迭代器接口Iterator包含4个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//类型参数<E>
//迭代器的接口
public interface Iterator<E>{
E next();
boolean hasNext();
void remove();

/**
对剩余的每个元素执行给定的操作，直到所有元素都已处理或操作引发异常。
如果指定了迭代顺序，则按迭代顺序执行操作。操作引发的异常被中继到调用方。
如果操作以任何方式修改集合（甚至通过调用remove方法或迭代器子类型的其他mutator方法），迭代器的行为是未指定的，除非重写类指定了并发修改策略。
如果操作引发异常，则未指定迭代器的后续行为。
参数: action–为每个元素执行的操作
抛出: NullPointerException–如果指定的操作为null
实施要求： 默认实现的行为类似于： while（hasNext（））
行动。接受（下一步（））； 自：
*/
default void forEachRemaining(Comsumer<? super E> action);
}

通过反复调用next()方法来逐个访问集合中的每个元素，所以称为迭代器：

如果到达了集合的末尾，next()方法将抛出一个 NoSuchElementException.

因此，在调用next()方法之前，需要调用hasNext方法.

如果迭代器对象还有多个可以访问的元素，逐个方法就返回true.

如果想要查看集合中的所有元素，就请求一个迭代器，当hasNext返回true时就反复地调用next方法.

下面给出原始的一个示例：

1
2
3
4
5
6
7
8
Collection<String> c = ...;
//c返回一个iterator，赋值给iter，然后准备循环访问
Iterator<String> iter = c.iterator();
//循环访问，先hasNext()，后next
while(iter.hasNext()){
    String element = iter.next();
    //do something with element
}

而我们平常一般使用foreach循环来实现上面的操作，因为编译器会简单地将“foreach”循环转换为带有迭代器的循环。

1
2
3
4
Collection<String> c = ...;
for(String element;c){
    //do something with element
}

事实上foreach循环能够处理任何实现了Iterable接口的对象，这个接口只包含一个抽象方法：

1
2
3
4
public interface Iterable<E>{
    //返回一个迭代器
    Iterable<E> iterator();
}

Collection接口扩展了Iterable接口。因此，所有标准类库中的集合都可以使用foreach循环

另外一种方法时使用forEachRemaining方法并提供一个lambda表达式.

将对迭代器的每一个元素调用这个lambda表达式，直到没有元素为止；

1
2
3
4
Collection<String> c = ...;
//c返回一个iterator，赋值给iter，然后准备访问
Iterator<String> iter = c.iterator();
iter.forEachRemaining(element -> {do something with element});

访问元素的顺序取决于集合的类型，如果对ArrayList进行迭代，迭代器会从索引0开始，每迭代一次，索引值加1.

而访问HashSet中的元素，则会按照一种基本上随机的顺序获得元素。

由此可见，虽然可以在迭代过程中遍历集合中的所有元素，但是无法预知访问各元素的顺序。但这也不要紧，因为对于计算总和或者统计匹配之类的计算，顺序并不重要。

C++与Java中迭代器的区别

传统集合类库，如C的标准模板库中，迭代器是根据数组的索引建模的。即知道了数组索引i，通过i就能访问元素。

但Java中不是这样处理的。查找操作和位置操作是紧密耦合的，即查找一个元素的唯一方法是调用next(),而执行查找操作的同时，迭代器的位置就会随之向前移动。

因此可以认为Java迭代器_位于两个元素之间_,通过调用next,迭代器会不断的前进，即自动越过下一个元素，并返回刚刚越过的那个元素的引用。

于是就有了一个推论，Java中迭代器的Iterator.next与InputStream.read可以看成等效的。即当从数据流中读取一个字节时，会自动的"消耗掉"这个字节。下一次调用read时，又会消耗并返回一个字节.同样的方式，反复调用next就可以读取集合中的所有元素。

基于这样的设计，Iterator接口中的remove方法将会删除上次调用next方法时返回的元素。就是说你想删除某个元素之前，要先"看看"这个元素是什么，你需要越过这个元素，知道返回的这个元素是什么，然后才去删除他。例如：

1
2
3
Iterator<String> it = c.iterator();
it.next();//越过这个元素，将迭代器向前进一位
it.remove();//删除你刚刚越过的元素

这样，我们能看出，next方法和remove方法存在依赖性.调用remove方法时肯定要和next方法合用，不然你的语句是不合法的。

编译器会抛出一个IllegalStateException异常.

即如果想要删除两个相邻的元素，不能这样调用

1
2
3
it.remove();
it.remove();
//ERROR

正确的做法应该是这样:

1
2
3
4
5
6
it.next();
it.remove();

it.next();
it.remove();
//ok

泛型实用方法

由于Collection与Iterator都是泛型接口，你可以使用处理泛型接口的方式来处理他们。编写出处理任何集合类型的实用方法

例如Collection接口中就有一个contains泛型方法，留给设计者来实现这个实用方法

他的形式如下：

1
2
3
4
5
6
public static <E> boolean contaions(Collection<E> c,Object obj){
    for(E element:c){
        if(element.equals(obj))
            return true;
    }
}

AbstractCollection抽象类，它保持了基础方法size和iterator仍为抽象方法，但是其他的实用方法都提供了例行方法，可以让实现者更容易地实现这个接口。

这样，具体的集合类可以扩展AbstractCollection抽象类来提供具体实现.当然，具体的集合类如果有更叫高效的contains方法，完全可以覆盖AbstractCollection类里的例行方法

在Java某个版本后，提供了一种更好的办法，就是接口中允许有默认方法，但这种新的解决方案大都应用在Collection中与流有关的部分方法。

另外，还有一个很有用的方法：

1
2
3
// 谓语 Predicate
// 过滤器 filter
default boolean removeIf(Predicate<? super E> filter)

这个方法用于删除满足某个条件的元素

List接口

List是一个有序集合。元素会增加到容器中的特定位置。于是我们就有两种访问元素的方式，随机访问(random access)和迭代器访问(iterator)

随机访问是指使用一个整数索引来访问，只要知道首地址i,就可以按照任意顺序访问。

迭代器访问必须顺序地访问元素

为了避免对链表进行随机访问（因为这真的很慢），java1.4引入了一个标记接口RandomAccess 。

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

1
2
3
4
5
6
if(c instanceof RandomAccess){
    use random access
}
else{
    use sequential access
}

集接口（Set）

集（set）的add方法更严谨，它不允许增加重复的元素。

除此之外，在定义集的equals方法时要注意，只要两个集包含同样的元素就应当认为他们是相等的，不要求这些元素有同样的顺序。

hasCode方法的定义要保证包含相同元素的两个集会得到相同的散列码。

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

链表 LinkedList<T>

Java中的链表是双向链表，即每个链接还存放着其前驱的引用。

链表与泛型集合(Collection<T>)的一个重要区别是，链表是一个有序集合.每个对象的位置十分重要。

LinkedList.add方法将对象添加到链表的尾部。但是，常常需要将元素添加到链表的中间。这时候就需要一个依赖于位置的add方法

之前我们学过，迭代器描述了集合中的位置，依赖于位置的的集合方法都该用迭代器负责。但Iterator接口中并没有add方法。所以为了处理链表，Iterator接口提供一个子接口ListIterator，其中包含处理链表中带位置的add方法。

1
2
3
4
5
public interface ListIterator<E> extends Iterator<E> {
    // Query Operations
    boolean hasNext();
    void add(E element);
    ...

与Collection.add不同，这个add方法不返回boolean类型的值。因为它假定add操作总会改变链表。

当我们想要反向遍历链表时，可以使用ListIterator接口提供的两个方法

1
2
boolean hasPrevious();
E previous();

与next方法一样，previous方法返回越过的对象。

LinkedList类的listIterator方法返回越过实现了ListIterator接口的迭代器对象。

1
2
LinkList staff = ...;
ListIterator iter = staff.listIterator();

add方法在迭代器位置之前添加一个新对象，假如迭代器现在越过了第一个元素，在第二个元素的位置，那么新增加的元素就在第二个元素之前，夹在了第一个和第二个元素之间。

于是我们就发现，如果现在迭代器正好指向链表表头，那么调用add操作时，新添加的元素将变成链表的新表头。

而当迭代器越过了链表的最后一个元素时(即hasNext返回false)，添加的元素将变成列表的新表尾。

如果链表有n个元素，那么会有n+1个位置可以添加新元素。这些位置与迭代器的n+1个可能的位置相对应。

|ABC

A|BC

AB|C

ABC|

  • 用光标来类比时需要注意，remove和Backspace键的工作方式不太一样

    next与remove连用，remove会删除左侧的元素，这与Backspace键一样

    但previous与remove连用，remove会删除右侧的元素

    除此之外，remove不能连续两次调用，中间一定要有previous或者next。

    add方法只依赖于迭代器的位置，而remove方法不同，它还依赖于迭代器的状态(即正向遍历next还是反向遍历previous)

set方法用一个新元素来替换调用next或者previous方法返回的上一个元素。

如果一个迭代器发现它的集合被另外一个迭代器修改了，或是被该集合自身的方法修改了，就会抛出一个ConcurrentModificationException异常。

具体的实现上，每个迭代器都为它负责的更改操作维护了一个单独的更改操作数。而集合本身也有维护一个跟踪更改操作数。

于是在迭代器方法开始时，比对两个操作数是否相等就可以知道集合是否被其他的操作更改了。不一致时，就会抛出一个ConcurrentModificationException异常。

Java中的链表不支持快速随机访问，这是因为要查看链表中的第n个元素，就必须先调用迭代器，越过n-1个元素，没有捷径可走，很明显这十分缓慢。

所以当我们需要按整数索引来访问元素时，通常不要使用链表。

要注意，使用链表的唯一理由就是尽可能的减少在列表中插入或者删除元素的开销。如果列表只有很少几个元素，就完全可以使用ArrayList。

建议避免使用以整数索引表示链表中位置的所有方法。更好的做法是换用数组或者ArrayList，而不是使用链表。

下面的println方法会自动调用AbstractCollection类中的toString方法打印出来链表a的所有元素:
1-基础知识-3-images

1
2
LinkedList a;
System.out.println(a);

数组列表ArrayList

数组列表ArrayList也实现了List接口，ArrayList封装了一个动态再分配的对象数组。

ArrayList方法不是同步的，而Vector类的所有方法都是同步的。

常见情况下，我们只希望从一个线层访问动态数组的元素，这种情况下，Vector对象的代码会在同步操作上白白浪费大量的时间。

Map 映射关系

通常，我们知道某些关键信息，希望查找与之关联的元素。映射(map)数据结构就是为此设计的。

映射用来存放建/值对。如果提供了键，就能出查找到值。

例如键为员工ID，值为Employee对象。

基本映射操作

Java类库为映射提供了两个通用的实现：HashMap和TreeMap.

这两个类都实现了Map接口。

  • 应该选择散列映射还是树映射呢？与集一样，选择散列稍微快一些。如果不需要按照有序的顺序访问键，最好选择散列映射。

下面举例，使用一个散列映射存储员工信息:

src/v1ch09/map

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
package map;

import java.util.*;

/**
 * This program demonstrates the use of a map with key type String and value type Employee.
 * 这个程序演示了使用键类型String和值类型Employee的映射
 * @author Cay Horstmann
 * @version 1.12 2015-06-21
 */
public class MapTest {
    public static void main(String[] args) {
        var staff = new HashMap<String, Employee>();
        staff.put("144-25-5464", new Employee("Amy Lee"));
        staff.put("567-24-2546", new Employee("Harry Hacker"));
        staff.put("157-62-7935", new Employee("Gary Cooper"));
        staff.put("456-62-5527", new Employee("Francesca Cruz"));

        // print all entries
        // 打印所有条目
        System.out.println(staff);

        // remove an entry
        //remove an entry
        staff.remove("567-24-2546");

        // replace an entry
        // 替换条目
        staff.put("456-62-5527", new Employee("Francesca Miller"));

        // look up a value
        // 查找值
        System.out.println(staff.get("157-62-7935"));

        // iterate through all entries
        // 遍历所有条目
        staff.forEach((k, v) ->
                System.out.println("key=" + k + ", value=" + v));
    }
}

每当往映射中添加一个对象时，必须同时提供一个建。

对应的，要检索一个对象，必须使用键。所以要记住键。

检索get方法

如果映射中没有存储给定键的对应信息，get方法将会返回null。

1
2
var id = "987-98-9996";
Employee e = staff.get(id);

也可以指定一个好的默认值，在没有键时可以返回这个默认值,这时候使用 getOrDefault()方法

1
2
3
Map<String,Integer> scores = ...;
//get 0 if the id is not present
int score = scores.getOrDefault(id,0);

键必须是唯一的。不能对同一个键存放两个值。如果对同一个键调用两次put方法，第二个值就会取代第一个值。

实际上put将返回与这个键参数关联的上一个值(被取代的那个值).

remove方法

remove方法从映射中删除给定键对应的元素。

size方法

size方法返回映射中的元素数。

要迭代处理映射的键和值，最容易的方法是使用foreach方法。可以提供一个接收键和值的lambda表达式。映射中的每一项会依序调用这个表达式。

1
2
score.forEach((k,v) ->
    System.out.println("key+" + k + ",value" + v));

Map类方法

java.util.Map<K,V> 备注
V get(Object key)

树

排序和查找