Java编程笔记16：深入容器

图源：PHP中文网

填充容器

填充容器会有Java编程笔记15：数组 - 魔芋红茶’s blog (icexmoon.cn)种提到的填充数组同样的问题。

和数组类似，标准库提供一个方法Collections.fill用于向容器中填充元素：

package ch16.fill;

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

public class Main {
    public static void main(String[] args) {
        List nums = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            nums.add(i);
        }
        System.out.println(nums);
        Collections.fill(nums, Integer.valueOf(99));
        System.out.println(nums);
    }
}
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
// [99, 99, 99, 99, 99, 99, 99, 99, 99, 99]

但这个方法存在局限性：

只能向List类型的容器填充数据。所谓的填充是用指定元素覆盖已有元素，而非添加若干个指定元素。

同样的，这种方式填充的元素同样是同一个对象的引用：

package ch16.fill2;

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

import util.Fmt;

class AddrStr {
    private String str;

    public AddrStr(String str) {
        this.str = str;
    }

    @Override
    public String toString() {
        String addr = super.toString();
        return Fmt.sprintf("AddrStr(%s:%s)", addr, str);
    }
}

public class Main {
    public static void main(String[] args) {
        List strings = new ArrayList<>();
        String[] words = "abc".split("");
        for (String w : words) {
            strings.add(new AddrStr(w));
        }
        System.out.println(strings);
        Collections.fill(strings, new AddrStr("z"));
        System.out.println(strings);
    }
}
// [AddrStr(ch16.fill2.AddrStr@24d46ca6:a),
// AddrStr(ch16.fill2.AddrStr@6d311334:b),
// AddrStr(ch16.fill2.AddrStr@682a0b20:c)]
// [AddrStr(ch16.fill2.AddrStr@3d075dc0:z),
// AddrStr(ch16.fill2.AddrStr@3d075dc0:z),
// AddrStr(ch16.fill2.AddrStr@3d075dc0:z)]

使用Generator

很容易地，就会想到像在Java编程笔记15：数组 - 魔芋红茶’s blog (icexmoon.cn)中做过的那样，利用Generator接口实现将测试数据填充进容器：

package ch16.generator;

import java.util.ArrayList;
import java.util.List;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;

public class ListFiller {
    public static  List fill(List list, Generator gen, int num) {
        list.addAll(getList(gen, num));
        return list;
    }

    public static  List getList(Generator gen, int num) {
        List list = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            list.add(gen.next());
        }
        return list;
    }

    public static void main(String[] args) {
        List nums = new ArrayList<>();
        fill(nums, new CommonGenerator.IntGenerator(), 5);
        System.out.println(nums);
        List chars = new ArrayList<>(getList(new CommonGenerator.CharGenerator(), 5));
        System.out.println(chars);
        List strings = new ArrayList<>();
        strings.addAll(getList(new CommonGenerator.StringGenerator(), 5));
        System.out.println(strings);
    }
}
// [0, 1, 2, 3, 4]
// [a, b, c, d, e]
// [abcde, fghij, klmno, pqrst, uvwxy]

fill方法可以直接用指定的Generator对象填充List，而geList方法可以获取一个用来填充List的List，相对而言后者更灵活一些，可以用于在容器的构造器或者addAll方法中，main中的示例代码说明了这一点。

同样的，可以创建一个用来填充Map的工具类，只不过稍有些不同：

package ch16.generator;

import java.util.linkedHashMap;
import java.util.Map;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;

public class MapFiller {
    public static class Entry {
        public final K key;
        public final V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static  Map fill(Map map, Generator> gen, int num) {
        for (int i = 0; i < num; i++) {
            Entry entry = gen.next();
            map.put(entry.key, entry.value);
        }
        return map;
    }

    public static  Map fill(Map map, Generator keyGen, Generator valueGen, int num) {
        for (int i = 0; i < num; i++) {
            map.put(keyGen.next(), valueGen.next());
        }
        return map;
    }

    public static  Map getMap(Generator> gen, int num) {
        Map map = new linkedHashMap<>();
        fill(map, gen, num);
        return map;
    }

    public static  Map getMap(Generator kGen, Generator vGen, int num) {
        Map map = new linkedHashMap<>();
        fill(map, kGen, vGen, num);
        return map;
    }

    public static void main(String[] args) {
        Map map = getMap(new CommonGenerator.IntGenerator(), new CommonGenerator.CharGenerator(),
                5);
        System.out.println(map);
    }
}
// {0=a, 1=b, 2=c, 3=d, 4=e}

静态内部类Entry是为了方便某些以键值对方式产生元素的Generator使用的，可以用一个单独的例子说明：

package ch16.generator;

import java.util.Map;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;
import ch16.generator.MapFiller.Entry;

class IntCharGenerator implements Generator> {
    Generator kGen = new CommonGenerator.IntGenerator();
    Generator vGen = new CommonGenerator.CharGenerator();

    @Override
    public Entry next() {
        Integer key = kGen.next();
        Character value = vGen.next();
        Entry entry = new Entry<>(key, value);
        return entry;
    }

}

public class Main {
    public static void main(String[] args) {
        Map map = MapFiller.getMap(new IntCharGenerator(), 5);
        System.out.println(map);
    }
}
// {0=a, 1=b, 2=c, 3=d, 4=e}

这里的IntCharGenerator只是简单用于举例，事实上可以通过策略模式来编写一个更通用的KeyValueGenerator类作为产生Entry元素的生成器，可以分别将产生键和值的生成器作为策略进行绑定。

这里使用的Generator以及CommonGenerator等组件都是在Java编程笔记15：数组 - 魔芋红茶’s blog (icexmoon.cn)中定义的，没印象的可以翻翻之前的笔记。

Abs类

标准库中的容器组件包含一些抽象类，比如AbstractMap等，可以通过继承这些类来实现自定义容器。

当然一般来说我们不会有类似的需求，标准库已经提供大量丰富可靠的容器，但就产生测试数据这个问题来说，完全可以利用容器的抽象类，来产生一些专门用于测试数据填充和展示的容器：

package ch16.abs;

import java.util.AbstractList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;

class SampleList extends AbstractList {
    private final int size;
    private Generator gen;
    private Map items = new HashMap<>();

    public SampleList(Generator gen) {
        this(gen, 10);
    }

    public SampleList(Generator gen, int size) {
        this.gen = gen;
        if (size < 0) {
            size = 0;
        }
        this.size = size;
    }

    @Override
    public E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (!items.containsKey(index)) {
            E item = gen.next();
            items.put(index, item);
        }
        return items.get(index);
    }

    @Override
    public int size() {
        return size;
    }

}

public class Main {
    public static void main(String[] args) {
        List sl = new SampleList<>(new CommonGenerator.IntGenerator());
        System.out.println(sl);
    }
}
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

类似的，可以编写适用于Map的版本：

package ch16.abs2;

import java.util.AbstractMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;

class SampleMap extends AbstractMap {
    private int size;
    private Generator kGen;
    private Generator vGen;
    private Set> entries = new HashSet<>();

    public SampleMap(Generator kGen, Generator vGen, int size) {
        this.kGen = kGen;
        this.vGen = vGen;
        if (size < 0) {
            size = 0;
        }
        this.size = size;
        for (int i = 0; i < size; i++) {
            entries.add(newEntry());
        }
    }

    public SampleMap(Generator kGen, Generator vGen) {
        this(kGen, vGen, 10);
    }

    @Override
    public Set> entrySet() {
        return entries;
    }

    private Entry newEntry() {
        return new Entry() {

            @Override
            public K getKey() {
                return kGen.next();
            }

            @Override
            public V getValue() {
                return vGen.next();
            }

            @Override
            public V setValue(V value) {
                throw new UnsupportedOperationException();
            }

        };
    }

}

public class Main {
    public static void main(String[] args) {
        Map map = new SampleMap(new CommonGenerator.IntGenerator(),
                new CommonGenerator.CharGenerator());
        System.out.println(map);
    }
}
// {0=a, 1=b, 2=c, 3=d, 4=e, 5=f, 6=g, 7=h, 8=i, 9=j}

需要说明的是，上边的两个示例为了更通用，使用了泛型+Generator接口的实现方式，但实际上你可以通过继承容器的抽象类编写任意实现的容器，甚至是内部不包含任何存储单元，只用游标或者别的什么来临时产生元素：

package ch16.abs3;

import java.util.AbstractList;
import java.util.List;

class SampleList2 extends AbstractList {
    private final int size;

    public SampleList2(int size) {
        if (size < 0) {
            size = 0;
        }
        this.size = size;
    }

    public SampleList2() {
        this(10);
    }

    @Override
    public Integer get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return Integer.valueOf(index);
    }

    @Override
    public int size() {
        return size;
    }

}

public class Main {
    public static void main(String[] args) {
        List list = new SampleList2();
        System.out.println(list);
    }
}
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

最后介绍一个稍微复杂的例子：

package ch16.abs4;

import java.util.AbstractList;
import java.util.AbstractMap;
import java.util.Iterator;
import java.util.linkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Students {
    private static String[][] info = { { "Han Meimei", "19" }, { "Li Lei", "20" }, { "Jack Chen", "15" },
            { "Brus Lee", "11" } };

    private static class NameList extends AbstractList {

        @Override
        public String get(int index) {
            return info[index][0];
        }

        @Override
        public int size() {
            return info.length;
        }

    }

    private static class AgeList extends AbstractList {

        @Override
        public Integer get(int index) {
            return Integer.valueOf(info[index][1]);
        }

        @Override
        public int size() {
            return info.length;
        }

    }

    private static class StudentMap extends AbstractMap {
        private static class StudentEntry implements Entry {
            private int index = -1;

            public StudentEntry() {
            }

            @Override
            public String getKey() {
                return info[index][0];
            }

            @Override
            public Integer getValue() {
                return Integer.valueOf(info[index][1]);
            }

            @Override
            public Integer setValue(Integer value) {
                throw new UnsupportedOperationException();
            }

        }

        private static class StudentEntrySet extends linkedHashSet> {
            private StudentEntry se = new StudentEntry();

            @Override
            public Iterator> iterator() {
                return new Iterator>() {

                    @Override
                    public boolean hasNext() {
                        if (se.index >= info.length - 1) {
                            return false;
                        }
                        return true;
                    }

                    @Override
                    public Entry next() {
                        se.index++;
                        return se;
                    }

                };
            }
        }

        @Override
        public Set> entrySet() {
            return new StudentEntrySet();
        }

    }

    public static Map studentMap() {
        return new StudentMap();
    }

    public static List names() {
        return new NameList();
    }

    public static List ages() {
        return new AgeList();
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println(Students.studentMap());
        System.out.println(Students.names());
        System.out.println(Students.ages());
    }
}
// {Han Meimei=19, Li Lei=20, Jack Chen=15, Brus Lee=11}
// [Han Meimei, Li Lei, Jack Chen, Brus Lee]
// [19, 20, 15, 11]

这个例子中，真正的学生信息由一个String二维数组info保存，通过定义内嵌类StudentMap、NameList、AgeList，可以将信息分别以Map、姓名组成的List、年龄组成的List这三种方式组成。

一般来说这种效果需要切实创建三个容器，分别从数组录入数据，但示例利用继承抽象容器，并修改容器的遍历和数据读取逻辑，让容器看起来是一个普通容器，但实际却是从数组读取数据，并不单独存储数据。

这种将一份数据在多个对象之间分享的技术称作享元。

这个示例看起来颇为复杂，实际上可以用适配器模式进行简化，其核心无非是让多个容器分享同一个数组的数据，那么完全可创建多个将数组适配为相应容器的适配器，这样做反而更具备重用性，并且代码结构也更为清晰，当然这只是我在参考《Java编程思想》完成这个示例后的个人想法。

我同样编写的相应的示例进行了验证，有兴趣的可以自行前往Github查看，java-notebook/Main.java at main · icexmoon/java-notebook (github.com)。

最后要提醒的是，上面这种用数组来“模拟”容器的方式是存在问题的，比如用二维数组模拟Map，我们知道Map中的Key必须是唯一的，但二维数组中的元素显然无法保证这一点，所以如果不做特殊处理，就可能会出现一些奇怪的现象。所以上边的示例是无法直接在实际编程中使用的“玩具例子”，如果你需要用到类似的东西，需要付出额外的努力解决这些问题。

Collection

在Java编程笔记9：容器（下） - 魔芋红茶’s blog (icexmoon.cn)的最后，我绘制了一副容器的类图，通过类图可以清晰地发现，Java标准库的容器可以分为Collection和Map两大类，而List和Set两个类型都继承自Collection，也就是说它们都具备Collection接口中定义的方法。

需要说明的是，Collection中定义的方法并不需要被全部实现，有一些是可选的。

理论上我们可以通过实现Collection接口创建一个与List或Set类似的自定义容器，虽然一般情况下我们并不需要这么做，但这可以帮助我们梳理那些方法是可选的，哪些是必须实现的：

package ch16.collection;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

class MyCollection implements Collection {
    private E[] items;

    public MyCollection(E[] arr) {
        items = arr;
    }

    @Override
    public int size() {
        return items.length;
    }

    @Override
    public boolean isEmpty() {
        return items.length == 0;
    }

    @Override
    public boolean contains(Object o) {
        for (E item : items) {
            if (item.equals(o)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Iterator iterator() {
        return new Iterator() {
            private int index = -1;

            @Override
            public boolean hasNext() {
                return index < items.length - 1;
            }

            @Override
            public E next() {
                if (!hasNext()) {
                    throw new IndexOutOfBoundsException();
                }
                index++;
                return items[index];
            }

        };
    }

    @Override
    public Object[] toArray() {
        return items;
    }

    @Override
    @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        return (T[]) items;
    }

    @Override
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean containsAll(Collection c) {
        for (Object target : c) {
            if (!contains(target)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException();
    }

}

public class Main {
    public static void main(String[] args) {
        String[] arr = "a b c d e".split(" ");
        Collection collection = new MyCollection<>(arr);
        for (String item : collection) {
            System.out.print(item + " ");
        }
        System.out.println();
        System.out.println(collection.contains("a"));
        System.out.println(collection.containsAll(Arrays.asList("a", "b", "c")));
        System.out.println(collection.contains("g"));
        System.out.println(collection.containsAll(Arrays.asList("a", "z")));
    }
}
// a b c d e
// true
// true
// false
// false

示例中凡是没有具体实现，直接抛出UnsupportedOperationException异常的方法，都是可选方法。剩余的方法必须被实现。

总的来说，涉及向容器中“添加”、“删除”元素的方法都被视作可选方法，而必须实现的方法是一些遍历元素，或者比对元素等“只读”用途的方法。

事实上，像上面这样，只实现了Collection接口必须方法的类，可以看做是一个“不可修改的容器”，类似于Java编程笔记8：容器（上） - 魔芋红茶’s blog (icexmoon.cn)中提到的“不可修改的List”。

这里的MyCollection和之前介绍享元时编写的将二维数组转化为List的适配器颇为相似，只不过两者实现方式不同，这里是直接实现了Collection接口。

之所以标准库中的Collection接口被设计成了现在这样，而不是将必须实现的方法和非必须方法拆分成多个接口，是因为出于“避免创建过多接口”的考量。

不可修改的List

除了Arrays.asList可以产生“不可修改的List”以外，Collections.unmodifiableList方法同样可以产生一个“不可修改的List”，只不过前者像是在一个数组上建立一个"List视图"，后者则是基于一个指定List。

下面用一个示例来说明这两种方式产生的List与普通List在Collection接口的可选方法调用上的差别：

package ch16.collection2;

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

import ch15.test2.ArrayFiller;
import ch15.test2.CommonGenerator;
import ch15.test2.Generator;
import ch16.generator.ListFiller;

public class Main {
    public static void main(String[] args) {
        String[] arr = "abcdefg".split("");
        List list1 = new ArrayList<>(Arrays.asList(arr));
        List list2 = Arrays.asList(arr);
        List list1Copy = new ArrayList<>(list1);
        List list3 = Collections.unmodifiableList(list1Copy);
        Generator gen = new CommonGenerator.StringGenerator();
        test("normal list", list1, gen);
        test("asList", list2, gen);
        test("unmodifiableList", list3, gen);
    }

    public static  void test(String msg, List list, Generator gen) {
        System.out.println("===========" + msg + "==============");
        Collection collection = list;
        Collection other = new ArrayList<>(list.subList(0, 2));
        try {
            collection.remove(gen.next());
        } catch (Exception e) {
            System.out.println("remove():" + e);
        }
        try {
            collection.removeAll(other);
        } catch (Exception e) {
            System.out.println("removeAll():" + e);
        }
        try {
            collection.retainAll(other);
        } catch (Exception e) {
            System.out.println("retainAll():" + e);
        }
        try {
            collection.clear();
        } catch (Exception e) {
            System.out.println("clear():" + e);
        }
        try {
            collection.add(gen.next());
        } catch (Exception e) {
            System.out.println("add():" + e);
        }
        try {
            collection.addAll(other);
        } catch (Exception e) {
            System.out.println("addAll():" + e);
        }
        try {
            list.set(0, gen.next());
        } catch (Exception e) {
            System.out.println("set():" + e);
        }
    }
}
// ===========normal list==============
// ===========asList==============
// removeAll():java.lang.UnsupportedOperationException: remove
// retainAll():java.lang.UnsupportedOperationException: remove
// clear():java.lang.UnsupportedOperationException
// add():java.lang.UnsupportedOperationException
// addAll():java.lang.UnsupportedOperationException
// ===========unmodifiableList==============
// remove():java.lang.UnsupportedOperationException
// removeAll():java.lang.UnsupportedOperationException
// retainAll():java.lang.UnsupportedOperationException
// clear():java.lang.UnsupportedOperationException
// add():java.lang.UnsupportedOperationException
// addAll():java.lang.UnsupportedOperationException
// set():java.lang.UnsupportedOperationException

可以看到，比较奇怪的是虽然asList和unmodifiableList方法产生的List在绝大多数方法调用时都表现一致，即调用Collection的可选方法时抛出UnsupportedOperationException异常，但差别在于前者可以调用List.set方法，而后者不可以。

这在某种方面体现了这种借口设计的灵活性，即你可以自行选择实现哪些可选方法。

Set和存储顺序

在Java编程笔记9：容器（下） - 魔芋红茶’s blog (icexmoon.cn)中我们提到了几种Set接口的实现，事实上这几种实现功能上的区别是由于其实现机制的不同导致的，而实现机制的不同也决定了它们对元素类型的要求也不同。

简单地说，它们有以下区别：

HashSet作为最基础和常用的Set，基于散列（哈希）算法实现，所以元素必须实现hashCode方法。TreeSet基于“二叉排序树”创建，因此所有元素必须能够进行比较大小，即要实现Comparable接口。linkedHashSet，基于一个链表（linkedList）和HashSet创建，因此同样需要实现hashCode方法。

最后，所有的Set类型都必须实现equals方法，因为Set本身要求去重。

这些要求可以用下表来表示：

Set类型	equals方法	hashCode方法	Comparable接口
HashSet	√	√	×
TreeSet	√	×	√
linkedHashSet	√	√	×

这里的×指的实际上是非必须实现的意思，事实上如果可以的话，你完全可以让打算用Set存储的类型同时实现equals方法、hashCode方法、Comparable接口，这样就可以使用任意一种Set容器进行存储。

下面用一个示例说明使用Set容器时实现这些方法和接口的重要性：

package ch16.set;

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

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;
import ch15.test2.RandomGenerator;
import util.Fmt;

class Student {
    protected int id = 0;
    protected String name;
    protected int age;

    public Student(String name, int age) {
        this.name = name;
        if (age <= 0) {
            age = 1;
        }
        this.age = age;
    }

    public Student(String name, int age, int id) {
        this(name, age);
        if (id <= 0) {
            id = 0;
        }
        this.id = id;
    }

    public static Generator generator() {
        return new Generator() {
            private Generator nameGen = new RandomGenerator.StringGenerator();
            private Generator ageGen = new RandomGenerator.IntGenerator(30);
            private Generator idGen = new CommonGenerator.IntGenerator();

            @Override
            public Student next() {
                return new Student(nameGen.next(), ageGen.next(), idGen.next());
            }

            @Override
            public void reset() {
                idGen = new CommonGenerator.IntGenerator();
            }

        };
    }

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

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Student) {
            Student other = (Student) obj;
            if (this.id == other.id) {
                return true;
            }
        }
        return false;
    }
}

class HashableStudent extends Student {

    public HashableStudent(Student student) {
        super(student.name, student.age, student.id);
    }

    @Override
    public int hashCode() {
        return Integer.valueOf(id).hashCode();
    }

    public static Generator generator() {
        return new Generator() {
            private Generator sGen = Student.generator();

            @Override
            public Student next() {
                return new HashableStudent(sGen.next());
            }

            @Override
            public void reset() {
                sGen.reset();
            }

        };
    }

}

class ComparableStudent extends Student implements Comparable {

    public ComparableStudent(Student student) {
        super(student.name, student.age, student.id);
    }

    @Override
    public int compareTo(Student o) {
        if (equals(o)) {
            return 0;
        } else if (id < o.id) {
            return -1;
        } else {
            return 1;
        }
    }

    public static Generator generator() {
        return new Generator() {
            private Generator sGen = Student.generator();

            @Override
            public Student next() {
                return new ComparableStudent(sGen.next());
            }

            @Override
            public void reset() {
                sGen.reset();
            }

        };
    }

}

public class Main {
    public static void main(String[] args) {
        test(new HashSet<>(), HashableStudent.generator());
        test(new TreeSet<>(), ComparableStudent.generator());
        test(new linkedHashSet<>(), HashableStudent.generator());
        test(new HashSet<>(), Student.generator());
        test(new TreeSet<>(), Student.generator());
        test(new linkedHashSet<>(), Student.generator());
    }

    private static  void test(Set set, Generator gen) {
        System.out.println(set.getClass().getSimpleName() + " test");
        try {
            fill(set, gen);
            gen.reset();
            fill(set, gen);
        } catch (Exception e) {
            System.out.println(e);
        }
        System.out.println(set);
    }

    private static  void fill(Set set, Generator gen) {
        for (int i = 0; i < 3; i++) {
            set.add(gen.next());
        }
    }
}
// HashSet test
// [Student(0#xiusx,8), Student(1#xpxhc,8), Student(2#rerdp,11)]
// TreeSet test
// [Student(0#zzbau,4), Student(1#ilmpr,13), Student(2#mhfwj,9)]
// linkedHashSet test
// [Student(0#rgsyv,4), Student(1#rocon,10), Student(2#liapq,4)]
// HashSet test
// [Student(0#bfqqj,18), Student(2#unflr,24), Student(1#ltjbd,3), Student(2#mflmw,5), Student(1#bgzds,13), Student(0#qbjmt,16)]
// TreeSet test
// java.lang.ClassCastException: class ch16.set.Student cannot be cast to class java.lang.Comparable (ch16.set.Student is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
// []
// linkedHashSet test
// [Student(0#ozork,19), Student(1#zqwsk,24), Student(2#ktcuy,6), Student(0#fvhzn,14), Student(1#sfbbu,12), 
// Student(2#eohtq,8)]

这里的Student类虽然拥有三个属性，但只依赖id来判断是否重复或者进行比较。

HashableStudent是一个装饰器类，可以将一个普通的Student对象转换为实现了hashCode方法的Student对象。ComparableStudent的作用类似。

为了方便测试数据批量生成，这里为不同的Student类创建了静态方法generator以生成相应的Generator。为了能测试id重复的Student对象能否添加进Set，我不得不修改了Generator接口的定义，添加了一个reset方法，用于重置Generator：

package ch15.test2;

public interface Generator {
    T next();

    default void reset() {
        throw new UnsupportedOperationException();
    }
}

为了不让已有代码出错，这里选择用默认方法进行实现，并且默认实现只是抛出UnsupportedOperationException异常，这也是标准库类似情况的常规做法。

从最终的测试结果可以看到，实现了合适方法和接口的对象可以正常添加到相应类型的Set，但普通的Student在插入时出现了问题，即使它实现了equals方法。

我们甚至可以看到HashSet中插入了多个id相同的普通Student对象，这说明默认的hashCode实现导致了这一结果，HashSet甚至没有调用equals方法进行去重检查。而TreeSet直接抛出了异常，因为普通的Student对象并没有实现Comparable接口。

SortedSet

实际上TreeSet和Set之间还有一个接口：SortedSet。就像字面意思那样，它代表有序的Set。

下面简单演示下这个接口的用途：

package ch16.sorted_set;

import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

import ch15.test2.CommonGenerator;
import ch16.generator.ListFiller;

public class Main {
    public static void main(String[] args) {
        List list = ListFiller.getList(new CommonGenerator.IntGenerator(), 10);
        SortedSet set = new TreeSet<>(list);
        System.out.println(set);
        System.out.println(set.first());
        System.out.println(set.last());
        System.out.println(set.subSet(Integer.valueOf(3), Integer.valueOf(7)));
        System.out.println(set.headSet(3));
        System.out.println(set.tailSet(6));
    }
}
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
// 0
// 9
// [3, 4, 5, 6]
// [0, 1, 2]
// [6, 7, 8, 9]

这些方法的用途一目了然，这里不详细解释。

SortedSet的comparator方法会返回一个用于排序的Comparator对象，如果是null，表示使用默认的自然排序。

队列

在Java编程笔记9：容器（下） - 魔芋红茶’s blog (icexmoon.cn)中已经介绍过队列了，在了解泛型和Comparable等接口后，我们可以回头再理解一下队列。

package ch16.queue;

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

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;
import ch15.test2.RandomGenerator;

public class Main {
    public static void main(String[] args) {
        test(new linkedList(), new CommonGenerator.IntGenerator());
        test(new linkedList(), new CommonGenerator.CharGenerator());
        test(new PriorityQueue<>(), new RandomGenerator.IntGenerator());
    }

    private static  void test(Queue queue, Generator gen) {
        for (int i = 0; i < 10; i++) {
            queue.add(gen.next());
        }
        do {
            T item = null;
            try {
                item = queue.remove();
            } catch (NoSuchElementException e) {
                break;
            }
            System.out.print(item + " ");
        } while (true);
        System.out.println();
    }
}
// 0 1 2 3 4 5 6 7 8 9
// a b c d e f g h i j
// 31 36 41 42 47 48 59 77 78 81

上边的示例说明了linkedList实现的队列符合队列的基本概念——FIFO（先进先出）。有意思的是Queue的另一个实现PriorityQueue并不是如此，其输出结果更像是排序后的结果而非添加顺序。这是因为PriorityQueue是一种优先级队列。

需要注意peek和remove方法的区别，“peek”这个单词的意思是“偷窥”，在这里意味着查看队列中下个可以出队的元素，如果没有，返回null。remove则是直接执行出队操作，如果没有可出队的元素，抛出NoSuchElementException异常。

优先级队列

实际上优先级队列有很多用途，比如我们需要用一个队列存放系统消息，该消息由其他系统来读取并进行相应的处理，不同的是我们需要让消息具备不同的优先级，这样就可以让某些消息优先获得处理。

package ch16.queue2;

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

import ch16.queue2.Message.Priority;
import util.Fmt;

class Message implements Comparable {
    public static enum Priority {
        LOW, MEDIUM, HIGH;
    }

    private String msg = "";
    private Priority priorityFirst;
    private Priority prioritySecond;

    public Message(String msg, Priority priorityFirst, Priority prioritySecond) {
        this.msg = msg;
        this.priorityFirst = priorityFirst;
        this.prioritySecond = prioritySecond;
    }

    public Message(String msg, Priority priorityFirst) {
        this(msg, priorityFirst, Priority.LOW);
    }

    public Message(String msg) {
        this(msg, Priority.LOW);
    }

    @Override
    public int compareTo(Message o) {
        int pfCompare = this.priorityFirst.compareTo(o.priorityFirst);
        if (pfCompare > 0) {
            return 1;
        } else if (pfCompare < 0) {
            return -1;
        } else {
            int psCompare = this.prioritySecond.compareTo(o.prioritySecond);
            if (psCompare > 0) {
                return 1;
            } else if (psCompare < 0) {
                return -1;
            } else {
                return 0;
            }
        }
    }

    @Override
    public String toString() {
        return Fmt.sprintf("Msg(%s,%s,%s)", msg, priorityFirst, prioritySecond);
    }
}

public class Main {
    public static void main(String[] args) {
        Queue msgs = new PriorityQueue<>(Collections.reverseOrder());
        msgs.add(new Message("hello"));
        msgs.add(new Message("world", Priority.MEDIUM));
        msgs.add(new Message("How", Priority.HIGH));
        msgs.add(new Message("are", Priority.HIGH, Priority.HIGH));
        msgs.add(new Message("you", Priority.LOW, Priority.HIGH));
        while (msgs.peek() != null) {
            Message msg = msgs.remove();
            System.out.print(msg + " ");
        }
        System.out.println();
    }
}
// Msg(are,HIGH,HIGH) Msg(How,HIGH,LOW) Msg(world,MEDIUM,LOW) Msg(you,LOW,HIGH)
// Msg(hello,LOW,LOW)

和SortedSet类似，PriorityQueue同样需要一个排序算法来决定优先级高低，同样可以由插入元素实现Comparable接口或者指定一个Comparator来提供排序算法。

示例中Message作为消息载体，用两个Priority属性来分别代表主优先级与副优先级，compareTo方法中先比较主优先级，再比较副优先级。因为Priority本身是枚举类型，枚举默认实现了Comparable接口（与定义顺序相同），所以无需重复实现。

因为默认排序是自然排序，而这里显然要让高优先级的先出，所以在创建PriorityQueue对象时，指定一个Collections.reverseOrder()返回的逆序Comparator。

双向队列

默认的队列只能从队列的一端出队，从另一端入队，但双向队列的两头都可以执行入队和出队操作。

在标准库中，代表双向队列的接口是java.util.Deque，有多个容器实现了这个接口，最常见的是linkedList：

package ch16.queue3;

import java.util.Deque;
import java.util.linkedList;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;

public class Main {
    public static void main(String[] args) {
        test(new linkedList<>(), new CommonGenerator.IntGenerator());
    }

    private static  void test(Deque deque, Generator gen) {
        fillDeque(deque, gen);
        while (deque.peekFirst() != null) {
            T item = deque.removeFirst();
            System.out.print(item + " ");
        }
        System.out.println();
        deque.clear();
        gen.reset();
        fillDeque(deque, gen);
        while (deque.peekLast() != null) {
            T item = deque.removeLast();
            System.out.print(item + " ");
        }
        System.out.println();
    }

    private static  void fillDeque(Deque deque, Generator gen) {
        for (int i = 0; i < 5; i++) {
            deque.addFirst(gen.next());
        }
        for (int i = 0; i < 5; i++) {
            deque.addLast(gen.next());
        }
    }
}
// 4 3 2 1 0 5 6 7 8 9 
// 9 8 7 6 5 0 1 2 3 4

双向队列的使用场景并不如普通的队列或者优先级队列那么多。

Map

要理解Map，必须先理解散列，关于散列，可以阅读Java编程笔记番外1：浅谈散列 - 魔芋红茶’s blog (icexmoon.cn)。

大多数的Map容器都是基于散列实现的，但也不全是，比如TreeMap是基于红黑树实现的。而前者肯定是需要实现散列算法，即要存储的对象必须实现hashCode方法才可以。这里集中总结几种主要的Map容器的原理和需要：

HashMap，基于散列实现。linkedHashMap，在HashMap的基础上，额外用一个linkedList保存元素的插入顺序，添加新元素的性能略微低于HashMap，但遍历顺序略快，因为直接使用linkedList进行遍历。TreeMap，基于红黑树实现，内部的键值对是有序的。WeakHashMap，在HashMap基础上，键用弱引用实现。ConcurrentHashMap，线程安全的HashMap，可以用于多线程。IdentityHashMap，使用==而非equals方法比较键，用于解决特殊问题。

相应的，使用这些Map的类型也要实现相应的方法或接口：

Map类型	equals方法	hashCode方法	Comparable接口
HashMap	√	√	×
linkedHashMap	√	√	×
TreeMap	√	×	√
WeakHashMap	√	√	×
ConcurrentHashMap	√	√	×
IdentityHashMap	×	√	×

这里的×意思是非必须实现。

SortedMap

因为大多数Map是基于散列实现的，所以遍历顺序是无法保证的，这和HashSet是类似的。同样的，Map中有一个可以将内部元素排序的类型，即SortedMap，这个接口有两个实现：TreeMap和ConcurrentSkipListMap。

就像SortedSet那样，SortedMap因为内部是有序二叉树，所以提供一些方法可以“切分”出一些子SortedMap：

package ch16.sorted_map;

import java.util.SortedMap;
import java.util.TreeMap;

import ch15.test2.Generator;
import ch15.test2.RandomGenerator;

public class Main {
    public static void main(String[] args) {
        test(new TreeMap<>(), new RandomGenerator.IntGenerator(), new RandomGenerator.CharGenerator());
    }

    private static  void test(SortedMap map, Generator genKey, Generator genVal) {
        for (int i = 0; i < 10; i++) {
            map.put(genKey.next(), genVal.next());
        }
        System.out.println(map);
        System.out.println(map.firstKey());
        System.out.println(map.lastKey());
        System.out.println(map.subMap(25, 75));
        System.out.println(map.headMap(50));
        System.out.println(map.tailMap(50));
    }
}
// {32=z, 51=a, 60=j, 63=x, 71=s, 72=y, 79=s, 86=i}
// 32
// 86
// {32=z, 51=a, 60=j, 63=x, 71=s, 72=y}
// {32=z}
// {51=a, 60=j, 63=x, 71=s, 72=y, 79=s, 86=i}

linkedHashMap

linkedHashMap可以保留插入顺序，并且以这样的顺序进行遍历。此外，linkedHashMap还可以提供一种LRU（最近最少使用）算法进行遍历。

package ch16.linked_map;

import java.util.linkedHashMap;

import ch15.test2.CommonGenerator;
import ch15.test2.Generator;

public class Main {
    public static void main(String[] args) {
        linkedHashMap lhm = new linkedHashMap<>(30, 0.75f, true);
        Generator genKey = new CommonGenerator.IntGenerator();
        Generator genVal = new CommonGenerator.CharGenerator();
        for (int i = 0; i < 10; i++) {
            lhm.put(genKey.next(), genVal.next());
        }
        System.out.println(lhm);
        lhm.get(3);
        lhm.get(4);
        lhm.get(5);
        System.out.println(lhm);
    }
}
// {0=a, 1=b, 2=c, 3=d, 4=e, 5=f, 6=g, 7=h, 8=i, 9=j}
// {0=a, 1=b, 2=c, 6=g, 7=h, 8=i, 9=j, 3=d, 4=e, 5=f}

linkedHashMap默认的遍历顺序是插入顺序，可以通过一个构造器创建以“访问顺序”进行遍历的实例：

    ...
    public linkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    ...

这个构造器需要三个参数：

initialCapacity，初始容量，实际上就是散列表的容量，容量大了会浪费空间，容量小了可能需要频繁扩容。loadFactor，负载因子，指真实容量达到最大容量的多少比例时进行扩容。accessOrder，是否使用访问顺序遍历，false表示使用插入顺序。

初始没有访问过的Map遍历会是插入顺序，当使用get方法获取元素时，刚访问过的元素将会在遍历时的位置变为尾部，也就是最早访问的元素先遍历，最新访问的元素最后遍历。

这种Map的用途是，可以根据访问状况，在内存不够时将最近没有访问过的元素进行删除。事实上这也是操作系统管理内存的常见策略。

Collections

之前已经有使用过部分Collections的工具方法，实际上Collections的作用类似于Arrays，用于提供一组服务于Collection类型的容器类的工具方法。

其主要包含的方法有：

checkedXXX，将一个容器转换为可以动态类型检查的版本，如checkedList(List,Class)可以将给定的List转换为按照给定Class对象进行动态类型检查的List。这个方法在某些无法使用正常方式创建静态类型检查的泛型版本容器时会很有用。

package ch16.collections;

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

public class Main {
    public static void main(String[] args) {
        testCheckedXXX();
    }

    @SuppressWarnings("unchecked")
    private static void testCheckedXXX() {
        List list = new ArrayList();
        list.add("string");
        List checkedList = Collections.checkedList(list, Integer.class);
        try {
            checkedList.add("string");
        } catch (ClassCastException e) {
            System.out.println(e);
            // java.lang.ClassCastException: Attempt to insert class java.lang.String
            // element into collection with element type class java.lang.Integer
        }
    }
}

在上边这个示例中，list是一个非泛型的原生List句柄，所以不会检查添加添加的元素是否类型正确，但经过checkedList获取的新List具备类型检查的能力。

max和min，获取Collection类型容器中最大和最小的元素。显然该方法依赖于元素的Comparable接口，也可以额外指定一个Comaprator对象。

    ...
	private static void testMaxMin() {
        List list = new linkedList<>();
        ListFiller.fill(list, new RandomGenerator.IntGenerator(), 10);
        System.out.println(list);
        System.out.println(Collections.min(list));
        System.out.println(Collections.max(list));
        System.out.println(Collections.max(list, Collections.reverseOrder()));
        // [5, 60, 36, 93, 52, 9, 87, 51, 92, 39]
        // 5
        // 93
        // 5
    }
	...

indexOfSubList方法可以查询某个List中子串第一次出现的位置，相应的，lastIndexOfSubList可以查询最后一次出现的位置。

private static void testIndexOf() {
        Integer[] nums = new Integer[10];
        ArrayFiller.fill(nums, new CommonGenerator.IntGenerator());
        ArrayFiller.fillTail(nums, new CommonGenerator.IntGenerator(), 5);
        List list1 = new ArrayList<>(Arrays.asList(nums));
        List list2 = new ArrayList<>(Arrays.asList(nums).subList(1, 3));
        System.out.println(list1);
        System.out.println(list2);
        System.out.println(Collections.indexOfSubList(list1, list2));
        System.out.println(Collections.lastIndexOfSubList(list1, list2));
        // [0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
        // [1, 2]
        // 1
        // 6
    }

replaceAll方法的作用很简单：将容器中指定的某个元素用一个新元素替换：

  private static void testReplaceAll() {
        List list = new ArrayList<>();
        ListFiller.fill(list, new CommonGenerator.IntGenerator(), 3);
        ListFiller.fill(list, new CommonGenerator.IntGenerator(), 6);
        System.out.println(list);
        Collections.replaceAll(list, 0, 99);
        System.out.println(list);
        // [0, 1, 2, 0, 1, 2, 3, 4, 5]
        // [99, 1, 2, 99, 1, 2, 3, 4, 5]
    }

reverse方法的功能同样简单：将指定List倒序：

    private static void testReverse() {
        List list = new ArrayList<>();
        ListFiller.fill(list, new CommonGenerator.IntGenerator(), 10);
        System.out.println(list);
        Collections.reverse(list);
        System.out.println(list);
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    }
	...

reverseOrder方法会返回一个逆自然排序的Comparator，这在之前已经多次演示过，其实它还有一个重载版本，可以接受一个Comparator，并返回一个对应的逆序版本：

	...
	private static void testReverseOrder() {
        List list = new ArrayList<>(Arrays.asList("absdfdsfSDFNWER".split("")));
        Collections.sort(list);
        System.out.println(list);
        Collections.sort(list, Collections.reverseOrder());
        System.out.println(list);
        Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
        System.out.println(list);
        Collections.sort(list, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
        System.out.println(list);
        // [D, E, F, N, R, S, W, a, b, d, d, f, f, s, s]
        // [s, s, f, f, d, d, b, a, W, S, R, N, F, E, D]
        // [a, b, d, d, D, E, f, f, F, N, R, s, s, S, W]
        // [W, s, s, S, R, N, f, f, F, E, d, d, D, b, a]
    }
	...

示例中的Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER)实际上是一个字符串大小写不敏感的逆序排序的Comprator，reverseOrder的这种使用方式其实起到一个“装饰器函数”的用途，这在Python编程中相当常见。

rotate方法的用途是将List中的元素“轮转”：

	...
    private static void testRotate() {
        List list = new linkedList<>();
        ListFiller.fill(list, new CommonGenerator.IntGenerator(), 10);
        System.out.println(list);
        Collections.rotate(list, 1);
        System.out.println(list);
        Collections.rotate(list, 3);
        System.out.println(list);
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        // [9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
        // [6, 7, 8, 9, 0, 1, 2, 3, 4, 5]
    }
	...

实际上Linux的日志系统就是以这种“轮转”方式运行的，每次添加日志时，所有日志都会进行位移为1的轮转，这样就会空出第一个位置，用来保存最新的日志，同时，最老的日志会自动被丢弃掉。

shuffle方法的用途就像它的名称那样，就是将List中的元素打乱。默认的shuffle方法使用默认的随机数产生器来“洗牌”，你还可以指定一个随机数产生器。

	...
    private static void testShuffle() {
        List list = new linkedList<>();
        ListFiller.fill(list, new CommonGenerator.IntGenerator(), 10);
        System.out.println(list);
        Collections.shuffle(list);
        System.out.println(list);
        Collections.shuffle(list, new Random(17));
        System.out.println(list);
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        // [6, 7, 2, 5, 0, 1, 3, 8, 4, 9]
        // [9, 2, 6, 8, 4, 0, 7, 1, 5, 3]
    }
	...

sort可以对List中的元素进行排序，它还有一个支持指定Comparator对象的版本。

	...
    private static void testSort() {
        List list = new linkedList<>();
        ListFiller.fill(list, new RandomGenerator.IntGenerator(), 10);
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
        Collections.sort(list, Collections.reverseOrder());
        System.out.println(list);
        // [70, 50, 18, 89, 82, 5, 61, 26, 83, 64]
        // [5, 18, 26, 50, 61, 64, 70, 82, 83, 89]
        // [89, 83, 82, 70, 64, 61, 50, 26, 18, 5]
    }
	...

copy方法可以将一个List拷贝到另一个List中，并覆盖目标List中对应位置的元素：

	...
    private static void testCopy() {
        List source = new ArrayList<>();
        List target = new ArrayList<>();
        ListFiller.fill(source, new RandomGenerator.IntGenerator(), 5);
        ListFiller.fillBySame(target, null, 10);
        System.out.println(source);
        System.out.println(target);
        Collections.copy(target, source);
        System.out.println(source);
        System.out.println(target);
        // [96, 84, 79, 72, 69, 45, 44, 39, 27, 24]
        // [54, 27, 24, 62, 5]
        // [null, null, null, null, null, null, null, null, null, null]
        // [54, 27, 24, 62, 5]
        // [54, 27, 24, 62, 5, null, null, null, null, null]
    }
	...

需要注意的是，源List中的元素个数必须要小于等于目标List中的元素个数，否则拷贝会产生一个异常。

swap方法可以将List指定位置的两个元素交换位置：

	...
    private static void testSeap() {
        List list = new ArrayList<>();
        ListFiller.fill(list, new CommonGenerator.IntGenerator(), 10);
        System.out.println(list);
        Collections.swap(list, 3, 6);
        System.out.println(list);
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        // [0, 1, 2, 6, 4, 5, 3, 7, 8, 9]
    }
	...

fill方法可以用一个指定元素替换List中的所有元素：

	...
    private static void testFill() {
        List list = ListFiller.getList(new CommonGenerator.IntGenerator(), 10);
        System.out.println(list);
        Collections.fill(list, 99);
        System.out.println(list);
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        // [99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
    }
	...

nCopies方法可以返回一个用指定对象填充n次后的List，不过该List是不能修改的（Unmodifieable List）：

	...
    private static void testNCopies() {
        List list = Collections.nCopies(10, Integer.valueOf(99));
        System.out.println(list);
        try {
            list.set(0, 0);
        } catch (Exception e) {
            System.out.println(e);
        }
        // [99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
        // java.lang.UnsupportedOperationException
    }
	...

disjoint方法可以用于判断两个Collection对象中是否不包含相同的元素，用集合运算的说法就是是否不相交（dis join）：

	...
    private static void testDisJoin() {
        List list1 = new linkedList<>(Arrays.asList(1, 2, 3));
        List list2 = new linkedList<>(Arrays.asList(4, 5, 6));
        System.out.println(Collections.disjoint(list1, list2));
        list1 = new linkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6));
        list2 = new linkedList<>(Arrays.asList(2, 3, 4));
        System.out.println(Collections.disjoint(list1, list2));
        // true
        // false
    }
	...

frequency方法可以检索指定元素在Collection对象中出现的次数：

	...
    private static void testFrequency() {
        List nums = ListFiller.getList(new RandomGenerator.IntGenerator(10), 10);
        Integer target = nums.get(0);
        int times = Collections.frequency(nums, target);
        System.out.println(nums);
        Fmt.printf("find %s in list %d times", target, times);
        // [3, 0, 1, 3, 9, 0, 7, 4, 2, 0]
        // find 3 in list 2 times
    }
	...

单词“frequency”的意思正是“频率”。

emptyList可以返回空的List，该方法是泛型方法，可以根据需要的类型参数进行返回，同时返回的List是不可修改的List。类似的还有两个方法：emptySet和emptyMap。

	...
    private static void testEmptyXXX() {
        List emptyList = Collections.emptyList();
        Set emptySet = Collections.emptySet();
        Map emptyMap = Collections.emptyMap();
        try {
            emptyList.add(1);
        } catch (Exception e) {
            System.out.println(e);
        }
        try {
            emptySet.add(1);
        } catch (Exception e) {
            System.out.println(e);
        }
        try {
            emptyMap.put(1, "hello");
        } catch (Exception e) {
            System.out.println(e);
        }
        // java.lang.UnsupportedOperationException
        // java.lang.UnsupportedOperationException
        // java.lang.UnsupportedOperationException
    }
	...

singleton方法可以产生一个仅由一个指定元素填充的Set，singletonList和singletonMap的作用类似，需要注意的是返回的容器同样是不可修改的：

	...
    private static void testSingletonXXX() {
        Set set = Collections.singleton(Integer.valueOf(99));
        List list = Collections.singletonList(Integer.valueOf(99));
        Map map = Collections.singletonMap(99, "hello");
        System.out.println(set);
        System.out.println(list);
        System.out.println(map);
        // [99]
        // [99]
        // {99=hello}
    }
	...

排序和查询

Collections.sort可以对List进行排序，这点前边已经演示过了。除此之外，Collections同样有一个binarySearch方法，可以通过二分插在在已经排序的List中查找对象，并返回其位置。

package ch16.sort;

import java.util.Collections;
import java.util.linkedList;
import java.util.List;
import java.util.Random;

import ch15.test2.RandomGenerator;
import ch16.generator.ListFiller;
import util.Fmt;

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

    public static void main(String[] args) {
        List list = new linkedList<>();
        ListFiller.fill(list, new RandomGenerator.IntGenerator(), 10);
        test(list);
    }

    private static > void test(List list) {
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
        T key = list.get(random.nextInt(list.size()));
        int index = Collections.binarySearch(list, key);
        Fmt.printf("find %s in list, index is %d", key, index);
    }
}
// [20, 22, 90, 95, 56, 83, 16, 7, 50, 18]
// [7, 16, 18, 20, 22, 50, 56, 83, 90, 95]
// find 50 in list, index is 5

相关方法的名称用法都和对数组的操作类似。

不可修改的Collection

前边我们已经遇到过“不可修改的List”，比如Arrays.asList返回的就是。除了标准库的方法可能会返回不可修改的容器，我们自己编写程序的时候可能也会遇到此类需要。

比如说下面这个例子：

package ch16.unmodieable;

import java.util.ArrayList;
import java.util.List;

import ch15.test2.Generator;
import ch15.test2.RandomGenerator;
import ch16.generator.ListFiller;

class RandomIntList {
    private static List list = new ArrayList<>();
    private static Generator gen = new RandomGenerator.IntGenerator();

    public static List get(int num) {
        if (list.size() == num) {
            return list;
        }
        list = new ArrayList<>();
        ListFiller.fill(list, gen, num);
        return list;
    }
}

public class Main {
    public static void main(String[] args) {
        List list = RandomIntList.get(10);
        System.out.println(list);
        list.set(0, -1);
        System.out.println(RandomIntList.get(10));
    }
}
// [71, 34, 48, 6, 85, 51, 10, 44, 54, 97]
// [-1, 34, 48, 6, 85, 51, 10, 44, 54, 97]

这个示例中RandomIntList的get方法负责产生一个“随机的整数List”。为了效率考虑，每次产生的List对象会保存在静态属性中，如果下次调用get方法时要获取同样长度的List对象，直接返回“缓存”的List对象。

但这个例子存在一个问题，如果客户端代码（这里是main方法）获取到List后进行了修改，比如说示例中将第一个元素修改为-1，下次调用get就会出现奇怪的结果。

这个问题的关键在于RandomIntList产生的List应当只作为一组数据提供给客户端代码使用，而客户端代码应当无权修改原始数据才对。

Collections就提供一组方法，可以很容易地将普通的Collection容器转换为不可修改的版本：

...
class RandomIntList {
	...
    public static List get(int num) {
		...
        list = Collections.unmodifiableList(list);
        return list;
    }
}

public class Main {
    public static void main(String[] args) {
        ...
    }
}
// [22, 77, 38, 54, 16, 23, 23, 21, 65, 89]
// Exception in thread "main" java.lang.UnsupportedOperationException
// at
// java.base/java.util.Collections$UnmodifiableList.set(Collections.java:1323)
// at ch16.unmodieable2.Main.main(Main.java:30)

除了unmodifiableList，还有UnmodifiableSortedSet等方法，对应不同类型的Collection容器。实际上这组方法同样可以看作是“装饰器方法”。

同步的Collection

学习过多线程编程（异步编程），就知道普通的组件或容器在多线程下是不能使用的，会出现一些奇怪的问题。因此会为多线程编程准备可以多线程编程的版本，这种组件通常被称作“同步的XXX”（sychronized xxx）或“线程安全的XXX”。

Collections同样提供一组方法可以将普通的容器转换为线程安全的容器：

package ch16.synchronize;

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

public class Main {
    public static void main(String[] args) {
        List list = new ArrayList<>();
        list = Collections.synchronizedList(list);
        list.addAll(Arrays.asList(1, 2, 3, 4, 5));
        System.out.println(list);
        Map map = new HashMap<>();
        map = Collections.synchronizedMap(map);
        map.put(1, "hello");
        map.put(2, "world");
        System.out.println(map);
    }

}
// [1, 2, 3, 4, 5]
// {1=hello, 2=world}

快速报错

即使是单线程编程，在使用容器时也存在一些问题，比如在遍历容器的时候，另一段代码修改了容器中的元素，就可能导致遍历出现问题。对于这个问题，Java采取的策略是在没有完成遍历时，如果容器内部的元素被修改，就直接报错：

package ch16.error;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import ch15.test2.CommonGenerator;
import ch16.generator.ListFiller;

public class Main {
    public static void main(String[] args) {
        List list = ListFiller.getList(new CommonGenerator.IntGenerator(), 10);
        Iterator iterator = list.iterator();
        list.remove(0);
        do {
            try {
                Integer num = iterator.next();
            } catch (NoSuchElementException e) {
                break;
            }
        } while (true);
    }
}
// Exception in thread "main" java.util.ConcurrentModificationException
// at
// java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
// at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
// at ch16.error.Main.main(Main.java:17)

弱引用

弱引用在很多领域都有应用，最常见的是安卓开发中，处于后台的Service要使用前台UI中的数据，就需要使用弱引用，原因在于APP的前端页面生命周期是不确定的，很容易被用户切换到后台，进入“假死”状态，甚至是直接被系统垃圾回收。如果这种数据引用是普通的引用，那就意味着存在引用关系而无法进行回收。对于移动开发来说是不会被允许的。

因此弱引用意味着这么一种情况：获取一个数据的引用，并可以通过该引用访问到数据，但允许系统在需要的时候对原始数据进行垃圾回收。

Java中的弱引用主要由三种类构成：SoftReference、WeakReference、PhantomReference。三者的区别在于数据的“可访问性”由强到弱，其中SoftReference会建立对原始数据的高速缓存，也就是说即使原始数据被垃圾回收，依然可以访问到缓存的数据。WeakReference和其它语言中常见的弱引用类似，可以看做是标准的“弱引用”的实现。

package ch16.ref;

import java.lang.ref.WeakReference;
import java.util.Iterator;
import java.util.linkedList;
import java.util.List;

import util.Fmt;

class Student {
    private static int counter = 0;
    private int id = ++counter;

    @Override
    public String toString() {
        return Fmt.sprintf("Student(%d)", id);
    }
}

public class Main {
    public static void main(String[] args) {
        final int SIZE = 10;
        List> list = new linkedList<>();
        List students = new linkedList<>();
        for (int i = 0; i < SIZE; i++) {
            Student s = new Student();
            students.add(s);
            list.add(new WeakReference(s));
        }
        System.out.println("init list=================");
        System.out.println(students);
        printWeakList(list);
        Iterator iterator = students.iterator();
        int index = 0;
        while (iterator.hasNext()) {
            iterator.next();
            if (index % 2 == 0) {
                iterator.remove();
            }
            index++;
        }
        System.out.println("items deleted=============");
        System.out.println(students);
        printWeakList(list);
        System.gc();
        System.out.println("gc is executed============");
        printWeakList(list);
    }

    private static  void printWeakList(List> list) {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (WeakReference wf : list) {
            T obj = wf.get();
            if (obj == null) {
                sb.append("null");
            } else {
                sb.append(obj.toString());
            }
            sb.append(", ");
        }
        sb.delete(sb.length() - 2, sb.length());
        sb.append("]");
        String str = sb.toString();
        System.out.println(str);
    }
}
// init list===============
// [Student(1), Student(2), Student(3), Student(4), Student(5), Student(6), Student(7), Student(8), Student(9), Student(10)]
// [Student(1), Student(2), Student(3), Student(4), Student(5), Student(6), Student(7), Student(8), Student(9), Student(10)]
// items deleted=============
// [Student(2), Student(4), Student(6), Student(8), Student(10)]
// [Student(1), Student(2), Student(3), Student(4), Student(5), Student(6), Student(7), Student(8), Student(9), Student(10)]
// gc is executed============
// [null, Student(2), null, Student(4), null, Student(6), null, Student(8), null, Student(10)]

这个示例中用两个List保存Student对象的引用，一个是传统的引用，一个是弱引用。之后使用一个Iterator将传统引用的List中位于奇数位置的对象引用删除，此时打印结果可以发现，弱引用的List依然可以获取到持有的对象，这是因为虽然被删除引用的对象已经处于可以被垃圾回收的状态，但是垃圾回收本身也是相当耗费性能的，并不会频繁执行垃圾回收，所以当前并没有真的被垃圾回收，所以若引用组成的List依然可以访问到完整数据。但是手动执行System.gc()后，就可以看到弱引用中相应的引用已经访问不到了（null）。

WeakHashMap

WeakHashMap与普通的Map区别在于，其键是弱引用，这意味着键对应的原始数据如果被垃圾回收，WeakHashMap中相应的键值对就会被删除。

package ch16.ref2;

import java.util.linkedList;
import java.util.List;
import java.util.WeakHashMap;

import util.Fmt;

class Student {
    private static int counter = 0;
    private int id = ++counter;

    @Override
    public String toString() {
        return Fmt.sprintf("Student(%d)", id);
    }

    @Override
    public int hashCode() {
        return Integer.valueOf(id).hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Student) {
            if (this.id == ((Student) obj).id) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        WeakHashMap whm = new WeakHashMap<>();
        List students = new linkedList<>();
        for (int i = 0; i < 10; i++) {
            Student s = new Student();
            if (i > 5) {
                students.add(s);
            }
            Integer num = Integer.valueOf(i);
            whm.put(s, num);
        }
        System.out.println(whm);
        System.gc();
        System.out.println(students);
        System.out.println(whm);
    }
}
// {Student(10)=9, Student(9)=8, Student(8)=7, Student(7)=6, Student(6)=5, Student(5)=4, Student(4)=3, Student(3)=2, Student(2)=1, Student(1)=0}
// [Student(7), Student(8), Student(9), Student(10)]
// {Student(10)=9, Student(9)=8, Student(8)=7, Student(7)=6}

示例中填充WeakHashMap时，将索引值大于5的Student对象用一个额外的List保存，因此在System.gc被执行后，WeakHashMap中只会出现保存在List中的那些键值对。

参考资料

SortedMap (Java Platform SE 8 ) (oracle.com)linkedHashMap (Java Platform SE 8 ) (oracle.com)

Java编程笔记16：深入容器

Java相关栏目本月热门文章