Java编程笔记9：容器（下）

本篇文章是Java编程笔记8：容器（上） - 魔芋红茶's blog (icexmoon.xyz)的下篇。

Set

Set也是一种常见的数据类型，很多编程语言都会提供这种容器。它的主要用途有两个：

提供一个可供查询的去重容器。
进行集合运算。

在Java中，Set是一个继承自Collection的接口：

public interface Set<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
    ...
    @SuppressWarnings("varargs")
    static <E> Set<E> of(E... elements) {
        switch (elements.length) { // implicit null check of elements
            case 0:
                @SuppressWarnings("unchecked")
                var set = (Set<E>) ImmutableCollections.EMPTY_SET;
                return set;
            case 1:
                return new ImmutableCollections.Set12<>(elements[0]);
            case 2:
                return new ImmutableCollections.Set12<>(elements[0], elements[1]);
            default:
                return new ImmutableCollections.SetN<>(elements);
        }
    }
    @SuppressWarnings("unchecked")
    static <E> Set<E> copyOf(Collection<? extends E> coll) {
        if (coll instanceof ImmutableCollections.AbstractImmutableSet) {
            return (Set<E>)coll;
        } else {
            return (Set<E>)Set.of(new HashSet<>(coll).toArray());
        }
    }
}

如果仔细对比Set与Java编程笔记8：容器（上） - 魔芋红茶's blog (icexmoon.xyz)中介绍的Collection就能发现，其实Set与Collection的方法几乎一摸一样，它并没有像List那样添加额外方法。所以Set与Collection在用法上是完全相同的，不同的是Set被定义为”一种去重容器“。

标准库主要提供三种实现了Set接口的容器：

package ch9;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new TreeSet<>();
        Set<Integer> set3 = new LinkedHashSet<>();
    }
}

它们的区别是：

HashSet，最常用的Set，采用哈希算法实现，有最快的查询效率。
TreeSet，采用树作为底层数据结构，会将元素以一定规则进行排序，查询效率不如HashSet。
LinkedHashSet，同样用哈希算法实现，有较快查询效率，同时用链表保留元素添加顺序。

用一个简单的例子说明这几种Set的区别：

package ch9.set2;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    private static Random random = new Random();

    private static void fillSet(Set<Integer> set) {
        for (int i = 0; i < 10; i++) {
            set.add(random.nextInt(100));
        }
    }

    private static void printSet(Set<Integer> set) {
        for (Integer integer : set) {
            System.out.print(integer + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new TreeSet<>();
        Set<Integer> set3 = new LinkedHashSet<>();
        fillSet(set1);
        printSet(set1);
        fillSet(set2);
        printSet(set2);
        set3.add(1);
        set3.add(2);
        set3.add(3);
        printSet(set3);
        // 96 64 33 97 82 2 8 41 42 79 
        // 38 47 49 53 55 57 66 70 92
        // 1 2 3
    }
}

TreeSet默认会以自然排序由大大小排列元素。之所以要进行排序，是因为排序后的元素可以利用类似二分查找的方式进行查找，这样查询效率不会太慢。

TreeSet还支持一个接收Comprator类型参数的构造函数，可以通过这个构造函数来改变排序规则：

package ch9.set3;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.Collection;
import java.util.Comparator;
import java.util.Collections;

public class Main {
    private static Random random = new Random();

    private static void fillSet(Set<Integer> set) {
        for (int i = 0; i < 10; i++) {
            set.add(random.nextInt(100));
        }
    }

    private static void printSet(Set<Integer> set) {
        for (Integer integer : set) {
            System.out.print(integer + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>(new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                int a = o1.intValue();
                int b = o2.intValue();
                if (a < b) {
                    return 1;
                } else if (a == b) {
                    return 0;
                } else {
                    return -1;
                }
            }

        });
        fillSet(set);
        printSet(set);
        // 83 79 73 72 67 58 29 17 5 
        set = new TreeSet<>(Collections.reverseOrder());
        fillSet(set);
        printSet(set);
        // 72 69 67 59 55 42 23 21 20 12
    }
}

上边示例中分别通过两种方式指定Comparator，分别是用匿名类自己实现和使用Collections.reverseOrder()方法返回的预定义Comparator。两者效果是一样的，都实现了对Integer类型Set的逆序排列。

对于内置类型，如Integer、Character，都实现了Comparable接口，所以可以直接使用TreeSet，但对于自定义类型，则必须实现Comparable接口或者给TreeSet指定一个Comparator：

package ch9.set4;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import util.Fmt;

import java.util.Collection;
import java.util.Comparator;
import java.util.Collections;

class Student {
    private int age;
    private String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return Fmt.sprintf("Student(name:%s,age:%d)", name, age);
    }
}

public class Main {

    public static void main(String[] args) {
        // class ch9.set4.Student cannot be cast to class java.lang.Comparable ...
        Set<Student> students = new TreeSet<>();
        students.add(new Student(19, "Li Lei"));
        students.add(new Student(15, "Zhang San"));
        students.add(new Student(20, "Han Meimei"));
    }
}

上面代码无法通过编译，原因很明确：Student没有实现Comparable接口。

package ch9.set5;

import java.util.Set;
import java.util.TreeSet;

import util.Fmt;

class Student implements Comparable<Student> {
    private int age;
    private String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return Fmt.sprintf("Student(name:%s,age:%d)", name, age);
    }

    @Override
    public int compareTo(Student s) {
        return Integer.compare(this.age, s.age);
    }
}

public class Main {

    public static void main(String[] args) {
        Set<Student> students = new TreeSet<>();
        students.add(new Student(19, "Li Lei"));
        students.add(new Student(15, "Zhang San"));
        students.add(new Student(20, "Han Meimei"));
        for (Student s : students) {
            System.out.print(s + " ");
        }
        System.out.println();
        // Student(name:Zhang San,age:15) Student(name:Li Lei,age:19) Student(name:Han
        // Meimei,age:20)
    }
}

当然，换用Comparator效果也是一样的：

package ch9.set6;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

import util.Fmt;

class Student {
    ...
    public static Comparator<Student> comparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student o1, Student o2) {
                return Integer.compare(o1.age, o2.age);
            }

        };
    }
}

public class Main {

    public static void main(String[] args) {
        Set<Student> students = new TreeSet<>(Student.comparator());
        students.add(new Student(19, "Li Lei"));
        students.add(new Student(15, "Zhang San"));
        students.add(new Student(20, "Han Meimei"));
        for (Student s : students) {
            System.out.print(s + " ");
        }
        System.out.println();
        // Student(name:Zhang San,age:15) Student(name:Li Lei,age:19) Student(name:Han
        // Meimei,age:20)
    }
}

Map

Map是一种映射类型，可以保存“键值对”，其用途与其它语言中的映射类型几乎一致。不过因为Java不像Python或者Go那样，直接在语言层面支持映射，无法通过类似map[key] = value;这样的方式方便地赋值或者遍历。

Java中Map是一个接口，下面是摘抄自Java源码的Map定义：

public interface Map<K, V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getKey().compareTo(c2.getKey());
        }
        public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getValue().compareTo(c2.getValue());
        }
        public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
        }
        public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
        }
    }
    boolean equals(Object o);

    int hashCode();

    default V getOrDefault(Object key, V defaultValue) {
        V v;
        return (((v = get(key)) != null) || containsKey(key))
            ? v
            : defaultValue;
    }

    default void forEach(BiConsumer<? super K, ? super V> action) {
        Objects.requireNonNull(action);
        for (Map.Entry<K, V> entry : entrySet()) {
            K k;
            V v;
            try {
                k = entry.getKey();
                v = entry.getValue();
            } catch (IllegalStateException ise) {
                // this usually means the entry is no longer in the map.
                throw new ConcurrentModificationException(ise);
            }
            action.accept(k, v);
        }
    }

    default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Objects.requireNonNull(function);
        for (Map.Entry<K, V> entry : entrySet()) {
            K k;
            V v;
            try {
                k = entry.getKey();
                v = entry.getValue();
            } catch (IllegalStateException ise) {
                // this usually means the entry is no longer in the map.
                throw new ConcurrentModificationException(ise);
            }

            // ise thrown from function is not a cme.
            v = function.apply(k, v);

            try {
                entry.setValue(v);
            } catch (IllegalStateException ise) {
                // this usually means the entry is no longer in the map.
                throw new ConcurrentModificationException(ise);
            }
        }
    }

    default V putIfAbsent(K key, V value) {
        V v = get(key);
        if (v == null) {
            v = put(key, value);
        }

        return v;
    }

    default boolean remove(Object key, Object value) {
        Object curValue = get(key);
        if (!Objects.equals(curValue, value) ||
            (curValue == null && !containsKey(key))) {
            return false;
        }
        remove(key);
        return true;
    }

    default boolean replace(K key, V oldValue, V newValue) {
        Object curValue = get(key);
        if (!Objects.equals(curValue, oldValue) ||
            (curValue == null && !containsKey(key))) {
            return false;
        }
        put(key, newValue);
        return true;
    }

    default V replace(K key, V value) {
        V curValue;
        if (((curValue = get(key)) != null) || containsKey(key)) {
            curValue = put(key, value);
        }
        return curValue;
    }

    default V computeIfAbsent(K key,
            Function<? super K, ? extends V> mappingFunction) {
        Objects.requireNonNull(mappingFunction);
        V v;
        if ((v = get(key)) == null) {
            V newValue;
            if ((newValue = mappingFunction.apply(key)) != null) {
                put(key, newValue);
                return newValue;
            }
        }

        return v;
    }

    default V computeIfPresent(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        Objects.requireNonNull(remappingFunction);
        V oldValue;
        if ((oldValue = get(key)) != null) {
            V newValue = remappingFunction.apply(key, oldValue);
            if (newValue != null) {
                put(key, newValue);
                return newValue;
            } else {
                remove(key);
                return null;
            }
        } else {
            return null;
        }
    }

    default V compute(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        Objects.requireNonNull(remappingFunction);
        V oldValue = get(key);

        V newValue = remappingFunction.apply(key, oldValue);
        if (newValue == null) {
            // delete mapping
            if (oldValue != null || containsKey(key)) {
                // something to remove
                remove(key);
                return null;
            } else {
                // nothing to do. Leave things as they were.
                return null;
            }
        } else {
            // add or replace old mapping
            put(key, newValue);
            return newValue;
        }
    }

    default V merge(K key, V value,
            BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        Objects.requireNonNull(remappingFunction);
        Objects.requireNonNull(value);
        V oldValue = get(key);
        V newValue = (oldValue == null) ? value :
                   remappingFunction.apply(oldValue, value);
        if (newValue == null) {
            remove(key);
        } else {
            put(key, newValue);
        }
        return newValue;
    }

    @SafeVarargs
    @SuppressWarnings("varargs")
    static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
        if (entries.length == 0) { // implicit null check of entries array
            @SuppressWarnings("unchecked")
            var map = (Map<K,V>) ImmutableCollections.EMPTY_MAP;
            return map;
        } else if (entries.length == 1) {
            // implicit null check of the array slot
            return new ImmutableCollections.Map1<>(entries[0].getKey(),
                    entries[0].getValue());
        } else {
            Object[] kva = new Object[entries.length << 1];
            int a = 0;
            for (Entry<? extends K, ? extends V> entry : entries) {
                // implicit null checks of each array slot
                kva[a++] = entry.getKey();
                kva[a++] = entry.getValue();
            }
            return new ImmutableCollections.MapN<>(kva);
        }
    }

    static <K, V> Entry<K, V> entry(K k, V v) {
        // KeyValueHolder checks for nulls
        return new KeyValueHolder<>(k, v);
    }

    @SuppressWarnings({"rawtypes","unchecked"})
    static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) {
        if (map instanceof ImmutableCollections.AbstractImmutableMap) {
            return (Map<K,V>)map;
        } else {
            return (Map<K,V>)Map.ofEntries(map.entrySet().toArray(new Entry[0]));
        }
    }
}

整理一下，主要方法有：

int size();，返回键值对个数。
boolean isEmpty();，映射是否为空。
boolean containsKey(Object key);，是否包含某个key。
boolean containsValue(Object value);，是否包含某个值。
V get(Object key);，根据给定的键获取对应的值，如果不存在，返回null。
V put(K key, V value);，设置键和值。
V remove(Object key);，将指定的键移除，并返回对应的值。
void putAll(Map<? extends K, ? extends V> m);，将指定映射的键值对添加到当前映射。
void clear();，清空映射。
Set<K> keySet();，返回由键组成的Set。
Collection<V> values();，返回由值组成的Collection。
Set<Map.Entry<K, V>> entrySet();，返回由Map.Entry组成的Set。
boolean equals(Object o);，比较。
int hashCode();，返回哈希值。
V getOrDefault(Object key, V defaultValue)，如果匹配到给定的key，返回对应的值，否则返回指定的默认值。
void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)，用指定的函数对所有的键值对进行处理（这应当是JavaSE8引入函数式编程后添加的方法）。
V putIfAbsent(K key, V value)，如果指定的键不存在或者对应的值为null，用给定的键值对进行设置。
boolean remove(Object key, Object value)，如果Map存在指定的键和值，则删除。
boolean replace(K key, V oldValue, V newValue)，如果Map存在指定的键和值（oldValue），则用指定的新值（newValue）替换。
V replace(K key, V value)，如果指定的key存在，使用value进行替换。
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)，如果指定的键不存在或者对应的值为null，用给定的函数处理后生成对应的值。
V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)，如果指定的键存在，且值不为null，使用给定的函数处理后生成新值。

类似于List，Map同样包含两个用于生成不可修改的映射的静态方法：

static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map)
static <K, V> Map<K, V> of(K k1, V v1)

生成的“不可修改的映射”中，键和值都不能包含null。

实际上of函数同样有多组重载方法，但因为是键值对这种形式的参数，所以没法使用可变参数列表。

Map接口包含一个嵌套接口Entry<k,V>，其作用是充当一种键值对类型，作为Map.entrySet方法返回的Set的元素类型，用于对Map的遍历。这个接口包含以下主要方法：

K getKey();，返回键。
V getValue();，返回值。
V setValue(V value);，设置值。
boolean equals(Object o);，比较。
int hashCode();，返回当前Entry的哈希值。

还包含几个静态方法：

comparingByKey()，返回对Entry键进行自然排序的comparator。
comparingByValue()，返回对Entry值进行自然排序的comparator。
comparingByKey(Comparator<? super K> cmp)，指定一个Comparator，并返回对Entry的键进行排序的Comparator。
comparingByValue(Comparator<? super V> cmp)，指定一个Comparator，并返回对Entry的值进行排序的Comparator。

篇幅关系，省略返回值类型。

Map最常见的用途是统计键出现的频率，用一个简单示例说明：

package ch9.map2;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> counter = new HashMap<>();
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            int num = random.nextInt(10) + 1;
            int oldTimes = counter.getOrDefault(num, 0);
            counter.put(num, oldTimes + 1);
        }
        System.out.println(counter);
        // {1=12, 2=11, 3=11, 4=8, 5=6, 6=8, 7=8, 8=13, 9=5, 10=18}
    }
}

这个程序循环100次，每次产生1~10的随机数，并利用Map统计随机数出现的频率。

需要注意的是，Java的Map其键和值都必须是对象，所以如果尝试访问一个不存在的键，Map.get返回的值是null，而非你期望的相应“零值”，这点和Go或Python之类的语言有很大不同。

所以在上面的示例中使用counter.getOrDefault(num, 0)这样的方式来避免额外的初始化语句，如果不这么做的话，可能需要进行额外的初始化工作：

package ch9.map3;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> counter = new HashMap<>();
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            int num = random.nextInt(10) + 1;
            if (!counter.containsKey(num)) {
                counter.put(num, 0);
            }
            int oldTimes = counter.get(num);
            counter.put(num, oldTimes + 1);
        }
        System.out.println(counter);
        // {1=12, 2=11, 3=11, 4=8, 5=6, 6=8, 7=8, 8=13, 9=5, 10=18}
    }
}

当然也可以使用putIfAbsent方法，这样可以省略一个if语句，但依然不如getOrDefault简洁。

Map可以和其它容器结合使用，以构建更复杂的数据结构：

package ch9.map;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import ch8.collection.Collection;
import util.Fmt;

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Person) {
            Person p = (Person) obj;
            if (this.name == p.name && this.age == p.age) {
                return true;
            }
        }
        return super.equals(obj);
    }

    @Override
    public String toString() {
        return Fmt.sprintf("Person(name:%s,age:%d)", name, age);
    }
}

class Pet {
    private String type;

    public Pet(String type) {
        this.type = type;
    }

    @Override
    public String toString() {
        return Fmt.sprintf("Pet(%s)", type);
    }
}

public class Main {
    public static void main(String[] args) {
        Map<Person, List<Pet>> persons = new HashMap<>();
        List<Pet> pets1 = new ArrayList<Pet>();
        Collections.addAll(pets1, new Pet("bird"), new Pet("dog"));
        persons.put(new Person("Li Lei", 19), pets1);
        List<Pet> pets2 = new ArrayList<Pet>();
        Collections.addAll(pets2, new Pet("cat"));
        persons.put(new Person("Han Meimei", 15), pets2);
        for (Person p : persons.keySet()) {
            System.out.println(p);
            for (Pet pet : persons.get(p)) {
                System.out.print(pet + " ");
            }
            System.out.println();
        }
        // Person(name:Han Meimei,age:15)
        // Pet(cat) 
        // Person(name:Li Lei,age:19)
        // Pet(bird) Pet(dog)
    }
}

在这个示例中，使用了先获取键组成的Set，再遍历这个Set以获取值。这种方式不仅“笨拙”，而且因为需要再次利用Map.get()查询索引，性能也较差。

所以，如果需要在遍历Map的时候同时访问键和值，通常需要用以下方式：

...
public class Main {
    public static void main(String[] args) {
        ...
        for (Map.Entry<Person, List<Pet>> entry : persons.entrySet()) {
            Person person = entry.getKey();
            List<Pet> pets = entry.getValue();
            System.out.println(person);
            for (Pet pet : pets) {
                System.out.print(pet + " ");
            }
            System.out.println();
        }
        // Person(name:Han Meimei,age:15)
        // Pet(cat)
        // Person(name:Li Lei,age:19)
        // Pet(bird) Pet(dog)
    }
}

这正是利用了之前我们所说的Map.Entry这个嵌套接口。

除了常用的HashMap之外，和List类似，还有TreeMap和LinkedHashMap两种标准库的Map实现，这里不再详细说明。

Queue

队列（queue）同样是种非常有用的数据结构，尤其是在多线程编程中，利用队列可以安全地在多个线程之间传递消息。对此，熟悉Go的开发者一定不会陌生，在Go中，通道（channel）就是类似的用途。

队列本身的规则很简单：FIFO（first in first out，即先进先出）。

Queue在Java中是一个继承自Collection的接口：

public interface Queue<E> extends Collection<E> {
    ...
}

先来看Queue接口包含哪些主要方法：

boolean add(E e);，如果允许的话，向队列中立即添加一个元素。成功返回true，如果空间不够，抛出IllegalStateException异常。
boolean offer(E e);，如果队列的空间允许，向队列中添加一个元素。成功返回true，失败返回false。对有限空间的队列，该方法比add更好用。
E remove();，从队列头部移除一个元素并返回，如果队列为空，抛出一个NoSuchElementException异常。
E poll();，从队列头部移除一个元素并返回，如果队列为空，返回null。
E element();，将队列头部的元素返回（不移除）。如果队列为空，抛出NoSuchElementException异常。
E peek();，将队列头部的元素返回。如果队列为空，返回null。

之前在Java编程笔记8：容器（上） - 魔芋红茶's blog (icexmoon.xyz)中我们也提到了，LinkedList类提供了栈和队列等需要的方法，所以利用LinkedList可以实现队列。不过不同的是，因为Java提供了一个队列接口Queue，并且LinkedList实现了该接口，所以我们可以直接将一个LinkedList实例向上转型为Queue来使用，而不需要像Stack那样单独创建类：

package ch9.queue;

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

import util.Fmt;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= 10; i++) {
            queue.offer(i);
            Fmt.printf("%d in queue\n", i);
            Fmt.printf("now queue: %s\n", queue);
        }
        System.out.println("starting queue out operation.");
        do {
            try {
                int num = queue.remove();
                Fmt.printf("%d is queue out.\n", num);
                Fmt.printf("now queue: %s\n", queue);
            } catch (NoSuchElementException e) {
                break;
            }
        } while (true);
        System.out.println("queue is cleared.");
        // 1 in queue
        // now queue: [1]
        // 2 in queue
        // now queue: [1, 2]
        // 3 in queue
        // now queue: [1, 2, 3]
        // 4 in queue
        // now queue: [1, 2, 3, 4]
        // 5 in queue
        // now queue: [1, 2, 3, 4, 5]
        // 6 in queue
        // now queue: [1, 2, 3, 4, 5, 6]
        // 7 in queue
        // now queue: [1, 2, 3, 4, 5, 6, 7]
        // 8 in queue
        // now queue: [1, 2, 3, 4, 5, 6, 7, 8]
        // 9 in queue
        // now queue: [1, 2, 3, 4, 5, 6, 7, 8, 9]
        // 10 in queue
        // now queue: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        // starting queue out operation.
        // 1 is queue out.
        // now queue: [2, 3, 4, 5, 6, 7, 8, 9, 10]
        // 2 is queue out.
        // now queue: [3, 4, 5, 6, 7, 8, 9, 10]
        // 3 is queue out.
        // now queue: [4, 5, 6, 7, 8, 9, 10]
        // 4 is queue out.
        // now queue: [5, 6, 7, 8, 9, 10]
        // 5 is queue out.
        // now queue: [6, 7, 8, 9, 10]
        // 6 is queue out.
        // now queue: [7, 8, 9, 10]
        // 7 is queue out.
        // now queue: [8, 9, 10]
        // 8 is queue out.
        // now queue: [9, 10]
        // 9 is queue out.
        // now queue: [10]
        // 10 is queue out.
        // now queue: []
        // queue is cleared.
    }
}

这个示例可以说明Queue的确是按照FIFO的方式运行。

PriorityQueue

优先级队列（PriorityQueue）也是我们可能会用到的一种队列。普通的队列是完全按照FIFO的方式运行，这样会产生一个后果，在某些时候，我们可能需要一个后加入的元素能够“优先”出队列，就无法实现。而优先级队列就是为了解决这一问题。

优先级队列可以按照给定的优先级规则，将进入队列的元素进行排序，并按照排序后的结果执行“出队列”的操作。

下面是一个优先级队列的示例：

package ch9.queue2;

import java.util.Collections;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;

enum MsgPriority {
    HIGH, MIDDLE, LOW;

    public static int compare(MsgPriority o1, MsgPriority o2) {
        if (o1 == o2) {
            return 0;
        } else if (o1 == HIGH) {
            return 1;
        } else if (o2 == HIGH) {
            return -1;
        } else if (o1 == MIDDLE) {
            return 1;
        } else if (o2 == MIDDLE) {
            return -1;
        } else {
            ;
        }
        return 0;
    }
}

class Message implements Comparable<Message> {
    private String msg;
    private MsgPriority priority;

    public Message(String msg, MsgPriority priority) {
        this.msg = msg;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return msg;
    }

    @Override
    public int compareTo(Message o) {
        return MsgPriority.compare(this.priority, o.priority);
    }
}

public class Main {
    public static void main(String[] args) {
        Queue<Message> msgs = new PriorityQueue<>();
        msgs.offer(new Message("hello", MsgPriority.LOW));
        msgs.offer(new Message("world", MsgPriority.MIDDLE));
        msgs.offer(new Message("How are you.", MsgPriority.HIGH));
        msgs.offer(new Message("middle msg", MsgPriority.MIDDLE));
        do {
            try {
                Message msg = msgs.remove();
                System.out.println(msg);
            } catch (NoSuchElementException e) {
                break;
            }
        } while (true);
        // hello
        // middle msg
        // world
        // How are you.
    }
}

可以看到，输出结果的确是经过排序了，midle msg这条消息被插入到了第二条，但是结果并不是如我们期望的那样按照Msg的priority属性的优先级从大到小排列。这是因为Java标准库中所有的容器排序（如果有的话）都是按照从小到大的方式进行排序。而在创建MsgPriority枚举的比较规则的时候我很自然地用了优先级大小比较的方式，所以结果与预期不符。

难道要达到预期要修改MsgPriority的比较,算法？其实是不必要的，只要使用一个预定义比较器初始化优先级队列即可：

...
public class Main {
    public static void main(String[] args) {
        Queue<Message> msgs = new PriorityQueue<>(Collections.reverseOrder());
        ...
        // How are you.
        // middle msg
        // world
        // hello
    }
}

只修改了一行代码，结果就符合预期了。

在枚举类型MsgPriority中，我并没有让其实现Comparable接口，原因是enum作为一种特殊的类，其能实现的接口相当有限，这其中并不包含Comparable接口。所以选择直接让其实现一个compare静态方法。

foreach和迭代器

在Java编程笔记8：容器（上） - 魔芋红茶's blog (icexmoon.xyz)中我们已经看到了迭代器模式在容器遍历中的威力，因为Collection扩展了Iterable接口，所以拥有iterator方法并可以返回一个迭代器。而Java的foreach语法可以接受任何实现了Iterable接口的对象，并进行遍历。

但是比较奇怪的是，foreach并不能接受一个迭代器（实现了Iterator接口的对象），这导致对于Iterator和Iterable我们要区别对待：

package ch9.foreach;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class Main {
    private static void foreachIterator(Iterator iterator) {
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + ", ");
        }
        System.out.println();
    }

    private static void foreachIterable(Iterable iterable) {
        for (Object object : iterable) {
            System.out.print(object + ", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, 1, 2, 3, 4, 5, 6);
        foreachIterable(list);
        foreachIterator(list.iterator());
        // 1, 2, 3, 4, 5, 6, 
        // 1, 2, 3, 4, 5, 6,
    }
}

之所以会有这样的问题，是因为Java的Iterator接口没有扩展Iterable接口。

或许这样说很抽象，很难理解。实际上Iterator的定义中应当包含iterator方法：

interface MyIterator<T> extends Iterable<T>, Iterator<T> {
    @Override
    default Iterator<T> iterator() {
        return this;
    }
}

内容也很简单，就是返回自己，毕竟自己就是一个Iterator。

这样做的好处在于，一个Iterator对象必然是一个Iterable对象，所以自然可以用foreach语法进行迭代。

这在道理上也说的通，毕竟Iterator拥有全部迭代所需的功能。

事实上Python的迭代机制就是这么设计的，关于Python的迭代器相关内容可以阅读Python学习笔记31：迭代技术 - 魔芋红茶's blog (icexmoon.xyz)。

还有需要说明的是，Java中的数组虽然同样是类，但是并没有实现Iterable接口，自然也没有一个返回Iterator对象的iterator方法，之所以可以用foreach语法进行遍历，是因为语言底层的支持，所以是不能将一个数组作为Iterable类型进行参数传递的：

...
public class Main {
    ...
    public static void main(String[] args) {
        ...
        // The method foreachIterable(Iterable) in the type Main is not applicable for
        // the arguments (Integer[])
        Integer[] array = new Integer[] { 1, 2, 3 };
        foreachIterable(array);
    }
}

这里的代码无法通过编译。

asList

在上篇和本篇笔记中，大量使用Arrays.asList方法产生List来填充相关容器。需要注意的是，Arrays.asList虽然返回的是一个List对象，但其底层的存储依然是使用的原数组，所以对该List的修改会影响到原始数组：

package ch9.aslist;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Integer[] array = new Integer[] { 1, 2, 3, 4, 5, 6 };
        List<Integer> list = Arrays.asList(array);
        Collections.shuffle(list);
        System.out.println(list);
        System.out.println(Arrays.toString(array));
        // [2, 4, 3, 1, 6, 5]
        // [2, 4, 3, 1, 6, 5]
        array = new Integer[] { 1, 2, 3, 4, 5, 6 };
        list = new ArrayList<>(Arrays.asList(array));
        Collections.shuffle(list);
        System.out.println(list);
        System.out.println(Arrays.toString(array));
        // [6, 2, 3, 5, 1, 4]
        // [1, 2, 3, 4, 5, 6]

    }
}

如果查看底层Arrays.asList的实现就能发现，其实其调用的是内部类Arrays$ArrayList<>(T[] array)构造函数，这个构造函数会利用传入的数组创建一个固定大小并共享底层数组的ArrayList。

这里的ArrayList是一个Arrays的内部类，而非java.util.ArrayList。

而java.util.ArrayList的构造方法ArrayList(Collection c)则是通过拷贝的方式利用传入的Collection对象创建一个全新的ArrayList，所以自然不会对原始数据产生影响。

最后我用EA绘制了上篇和本篇笔记涉及到的相关接口和类的UML类图，已上传到Github仓库，可以通过java-notebook/Java.pdf at main · icexmoon/java-notebook (github.com)连接进行下载查阅。

如果有安装EA的话，可以在同目录找到工程文件，可以直接用EA加载。

谢谢阅读。

参考资料

Java遍历Map集合的四种方式 (biancheng.net)

本作品采用知识共享署名 4.0 国际许可协议进行许可

Set

Map

Queue

PriorityQueue

foreach和迭代器

asList

参考资料

文章评论