图源:
填充容器
填充容器会有种提到的填充数组同样的问题。
和数组类似,标准库提供一个方法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<Integer> 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<AddrStr> 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
很容易地,就会想到像在中做过的那样,利用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 <T> List<T> fill(List<T> list, Generator<T> gen, int num) {
list.addAll(getList(gen, num));
return list;
}
public static <T> List<T> getList(Generator<T> gen, int num) {
List<T> list = new ArrayList<>();
for (int i = 0; i < num; i++) {
list.add(gen.next());
}
return list;
}
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>();
fill(nums, new CommonGenerator.IntGenerator(), 5);
System.out.println(nums);
List<Character> chars = new ArrayList<>(getList(new CommonGenerator.CharGenerator(), 5));
System.out.println(chars);
List<String> 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<K, V> {
public final K key;
public final V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
public static <K, V> Map<K, V> fill(Map<K, V> map, Generator<Entry<K, V>> gen, int num) {
for (int i = 0; i < num; i++) {
Entry<K, V> entry = gen.next();
map.put(entry.key, entry.value);
}
return map;
}
public static <K, V> Map<K, V> fill(Map<K, V> map, Generator<K> keyGen, Generator<V> valueGen, int num) {
for (int i = 0; i < num; i++) {
map.put(keyGen.next(), valueGen.next());
}
return map;
}
public static <K, V> Map<K, V> getMap(Generator<Entry<K, V>> gen, int num) {
Map<K, V> map = new LinkedHashMap<>();
fill(map, gen, num);
return map;
}
public static <K, V> Map<K, V> getMap(Generator<K> kGen, Generator<V> vGen, int num) {
Map<K, V> map = new LinkedHashMap<>();
fill(map, kGen, vGen, num);
return map;
}
public static void main(String[] args) {
Map<Integer, Character> 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<MapFiller.Entry<Integer, Character>> {
Generator<Integer> kGen = new CommonGenerator.IntGenerator();
Generator<Character> vGen = new CommonGenerator.CharGenerator();
@Override
public Entry<Integer, Character> next() {
Integer key = kGen.next();
Character value = vGen.next();
Entry<Integer, Character> entry = new Entry<>(key, value);
return entry;
}
}
public class Main {
public static void main(String[] args) {
Map<Integer, Character> map = MapFiller.getMap(new IntCharGenerator(), 5);
System.out.println(map);
}
}
// {0=a, 1=b, 2=c, 3=d, 4=e}
这里的IntCharGenerator
只是简单用于举例,事实上可以通过策略模式来编写一个更通用的KeyValueGenerator<K,V>
类作为产生Entry
元素的生成器,可以分别将产生键和值的生成器作为策略进行绑定。
这里使用的
Generator
以及CommonGenerator
等组件都是在中定义的,没印象的可以翻翻之前的笔记。
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<E> extends AbstractList<E> {
private final int size;
private Generator<E> gen;
private Map<Integer, E> items = new HashMap<>();
public SampleList(Generator<E> gen) {
this(gen, 10);
}
public SampleList(Generator<E> 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<Integer> 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<K, V> extends AbstractMap<K, V> {
private int size;
private Generator<K> kGen;
private Generator<V> vGen;
private Set<Entry<K, V>> entries = new HashSet<>();
public SampleMap(Generator<K> kGen, Generator<V> 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<K> kGen, Generator<V> vGen) {
this(kGen, vGen, 10);
}
@Override
public Set<Entry<K, V>> entrySet() {
return entries;
}
private Entry<K, V> newEntry() {
return new Entry<K, V>() {
@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<Integer, Character> map = new SampleMap<Integer, Character>(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<Integer> {
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<Integer> 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<String> {
@Override
public String get(int index) {
return info[index][0];
}
@Override
public int size() {
return info.length;
}
}
private static class AgeList extends AbstractList<Integer> {
@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<String, Integer> {
private static class StudentEntry implements Entry<String, Integer> {
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<Entry<String, Integer>> {
private StudentEntry se = new StudentEntry();
@Override
public Iterator<Entry<String, Integer>> iterator() {
return new Iterator<Map.Entry<String, Integer>>() {
@Override
public boolean hasNext() {
if (se.index >= info.length - 1) {
return false;
}
return true;
}
@Override
public Entry<String, Integer> next() {
se.index++;
return se;
}
};
}
}
@Override
public Set<Entry<String, Integer>> entrySet() {
return new StudentEntrySet();
}
}
public static Map<String, Integer> studentMap() {
return new StudentMap();
}
public static List<String> names() {
return new NameList();
}
public static List<Integer> 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查看,。
最后要提醒的是,上面这种用数组来“模拟”容器的方式是存在问题的,比如用二维数组模拟Map
,我们知道Map
中的Key
必须是唯一的,但二维数组中的元素显然无法保证这一点,所以如果不做特殊处理,就可能会出现一些奇怪的现象。所以上边的示例是无法直接在实际编程中使用的“玩具例子”,如果你需要用到类似的东西,需要付出额外的努力解决这些问题。
Collection
在的最后,我绘制了一副容器的类图,通过类图可以清晰地发现,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<E> implements Collection<E> {
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<E> iterator() {
return new Iterator<E>() {
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> 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<? extends E> 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<String> 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
接口必须方法的类,可以看做是一个“不可修改的容器”,类似于中提到的“不可修改的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<String> list1 = new ArrayList<>(Arrays.asList(arr));
List<String> list2 = Arrays.asList(arr);
List<String> list1Copy = new ArrayList<>(list1);
List<String> list3 = Collections.unmodifiableList(list1Copy);
Generator<String> gen = new CommonGenerator.StringGenerator();
test("normal list", list1, gen);
test("asList", list2, gen);
test("unmodifiableList", list3, gen);
}
public static <E> void test(String msg, List<E> list, Generator<E> gen) {
System.out.println("===========" + msg + "==============");
Collection<E> collection = list;
Collection<E> 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
和存储顺序
在中我们提到了几种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<Student> generator() {
return new Generator<Student>() {
private Generator<String> nameGen = new RandomGenerator.StringGenerator();
private Generator<Integer> ageGen = new RandomGenerator.IntGenerator(30);
private Generator<Integer> 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<Student> generator() {
return new Generator<Student>() {
private Generator<Student> sGen = Student.generator();
@Override
public Student next() {
return new HashableStudent(sGen.next());
}
@Override
public void reset() {
sGen.reset();
}
};
}
}
class ComparableStudent extends Student implements Comparable<Student> {
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<Student> generator() {
return new Generator<Student>() {
private Generator<Student> 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 <E> void test(Set<E> set, Generator<E> 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 <E> void fill(Set<E> set, Generator<E> 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> {
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<Integer> list = ListFiller.getList(new CommonGenerator.IntGenerator(), 10);
SortedSet<Integer> 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
,表示使用默认的自然排序。
队列
在中已经介绍过队列了,在了解泛型和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<Integer>(), new CommonGenerator.IntGenerator());
test(new LinkedList<Character>(), new CommonGenerator.CharGenerator());
test(new PriorityQueue<>(), new RandomGenerator.IntGenerator());
}
private static <T> void test(Queue<T> queue, Generator<T> 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<Message> {
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<Message> 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 <T> void test(Deque<T> deque, Generator<T> 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 <T> void fillDeque(Deque<T> deque, Generator<T> 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
,必须先理解散列,关于散列,可以阅读。
大多数的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 <V> void test(SortedMap<Integer, V> map, Generator<Integer> genKey, Generator<V> 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<Integer, Character> lhm = new LinkedHashMap<>(30, 0.75f, true);
Generator<Integer> genKey = new CommonGenerator.IntGenerator();
Generator<Character> 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<T>,Class<T>)
可以将给定的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<Integer>(); 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<Integer> 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<Integer> list1 = new ArrayList<>(Arrays.asList(nums)); List<Integer> 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<Integer> 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<Integer> 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<String> 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<Integer> 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<Integer> 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<Integer> 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<Integer> source = new ArrayList<>(); List<Integer> 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<Integer> 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<Integer> 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<Integer> 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<Integer> list1 = new LinkedList<>(Arrays.asList(1, 2, 3)); List<Integer> 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<Integer> 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<Integer> emptyList = Collections.emptyList(); Set<Integer> emptySet = Collections.emptySet(); Map<Integer, String> 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<Integer> set = Collections.singleton(Integer.valueOf(99)); List<Integer> list = Collections.singletonList(Integer.valueOf(99)); Map<Integer, String> 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<Integer> list = new LinkedList<>();
ListFiller.fill(list, new RandomGenerator.IntGenerator(), 10);
test(list);
}
private static <T extends Comparable<? super T>> void test(List<T> 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<Integer> list = new ArrayList<>();
private static Generator<Integer> gen = new RandomGenerator.IntGenerator();
public static List<Integer> 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<Integer> 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<Integer> 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<Integer> list = new ArrayList<>();
list = Collections.synchronizedList(list);
list.addAll(Arrays.asList(1, 2, 3, 4, 5));
System.out.println(list);
Map<Integer, String> 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<Integer> list = ListFiller.getList(new CommonGenerator.IntGenerator(), 10);
Iterator<Integer> 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<WeakReference<Student>> list = new LinkedList<>();
List<Student> students = new LinkedList<>();
for (int i = 0; i < SIZE; i++) {
Student s = new Student();
students.add(s);
list.add(new WeakReference<Student>(s));
}
System.out.println("init list=================");
System.out.println(students);
printWeakList(list);
Iterator<Student> 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 <T> void printWeakList(List<WeakReference<T>> list) {
StringBuffer sb = new StringBuffer();
sb.append("[");
for (WeakReference<T> 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<Student, Integer> whm = new WeakHashMap<>();
List<Student> 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
中的那些键值对。
文章评论