FreeOZ论坛

标题: Java集合框架小记 - 小key出品 [打印本页]

作者: key 时间: 30-6-2009 10:00
标题: Java集合框架小记 - 小key出品
Collection Framework是Java一直以来引以为傲的东西，在Java 1.3引入后，
大张旗鼓的宣传过好一阵。用过Collection Framework的人都知道，它有着比C++ STL优胜的地方。
但美中不足的是，这个Collection Framework一直用Object/Class Casting转来转去，
很烦。

Generic语法出来后，这点烦恼基本上可以消除了。虽然因为各种原因Generic的实现还不完美。
先解决问题再说吧。

而经过几年的变迁，collection framework本身也有着架构上的发展，让人看到一些良好的设计理念。

本文的目的就是探讨一下在新形势下Collection Framework同志的新思想，以及对未来的展望。Yeah~

作者: key 时间: 30-6-2009 10:03
标题: 两条线索：Array与Collection
很多人都认为Java Collection Framework有两条线索，那是Collection与Map。
而我的看法是Array和Collection。

大家不把Array看做是Collection Framework的一部分，主要是出于高贵的数据结构理想。
然而，你不能简单地抹掉Array在集合运算中的地址。作为Collection框架的一部分，少了
Array又怎能成事呢？

对了，本文不是一个教程，而是我个人观点的一些分享。欢迎批评。

作者: jfding 时间: 30-6-2009 10:26
看看java源码。colllections里很多类的实现，内部就是array。

作者: key 时间: 30-6-2009 11:13
标题: 线索下的线索：Arrays与Collections - 两个重要的Helper Classes
Arrays与Collections是两个Helper类，里面的方法“都是”静态的，而很多是配对的。我之前说
Java Collection Framework的两条线索是Array与Collection，和这两个Helper classes
多少有点关系。

互相转换
static <T> List<T> Arrays.asList(T... a) 把a数组的所有元素转成一个List，这个List
虽然没有言明，但大致上就是ArrayList之流（Serealizable + Random Accessable，还有谁呢？）
Object[] Collection.toArray()
<T> T[] Collection.toArray(T[] a)
注意，这里的Collection没有s，而方法也是non-static方法。也就是说，操作是Collection对象
的操作，而不需要通过Helper类来进行。
从1.5开始，因为引入了Generic，并同时引入了第二个toArray

Object[] Collection.toArray()是一个曾经让我们很痛苦的一个方法，看下面的测试代码：

1 public class ObjectArrayClassCastTest {
2 public static void main(String args []){
3 Object[] oa = new Object[3];
4 oa[0] = "Hello";
5 oa[1] = "world";
6 oa[2] = "!";
7
8 String[] sa = (String[])oa;
9 for(String s : sa) {
10 System.out.println(s);
11 }
12 }
13 }

复制代码

这套代码编译可以通过，但运行进会出现Runtime Exception

$ java ObjectArrayClassCastTest
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
at ObjectArrayClassCastTest.main(ObjectArrayClassCastTest.java:9)

复制代码

也就是说，如果Collection.toArray()返回了Object[]，我们还得手动转一次，那是多苦恼的一件事呀！
好吧，现在我们学了Generic，用Generic来试一次看看如何？

1 public class ObjectArrayClassCastTest {
2 public static void main(String args []){
3 Object[] oa = new Object[3];
4 oa[0] = "Hello";
5 oa[1] = "world";
6 oa[2] = "!";
7
8 //String[] sa = (String[])oa;
9 String[] sa = ObjectArrayClassCastTest.<String>cast(oa);
10 for(String s : sa) {
11 System.out.println(s);
12 }
13 }
14
15 public static <T> T[] cast(Object[] oa){
16 return (T[])oa;
17 }
18 }

复制代码

RuntimeException：

$ java ObjectArrayClassCastTest
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
at ObjectArrayClassCastTest.main(ObjectArrayClassCastTest.java:9)

复制代码

程序在第9行出错。。。为什么不是在16行出错呢？

我们来看看bytecode。首先是cast方法的bytecode

public static java.lang.Object[] cast(java.lang.Object[]);
Code:
0: aload_0
1: checkcast #10; //class "[Ljava/lang/Object;"
4: areturn

复制代码

很显然，在这里没有String或 T 什么事。这叫做什么？Generic Erasure。checkcast的时候，转换的
是目标是[Ljava/lang/Object;而不是 T 或 String（也不可能是String）

再看调用部分的bytecode

21: invokestatic #6; //Method cast:([Ljava/lang/Object;)[Ljava/lang/Object;
24: checkcast #7; //class "[Ljava/lang/String;"

复制代码

这个调用分两步进行，第一部是invokestatic，返回的结果是[Ljava/lang/Object;，即Object[]
第二步是checkcast，转换成String[]，所以RuntimeException就出现在这一步了。

无论如何，我们应该记得System.arraycopy(from, pos, to, pos, length)这个物体，应该说，这个怪物。
这个怪物总的来说是应运而生。因为XXX[]本身是一个Class，无论XXX与YYY有什么关系，XXX[]与YYY[]是没有关系的，
补充：其实还是有关系的，如果X和Y是继承或实现关系，可以默认转换，那么正向的默认转换是成功的，但反向的强制转换就不行了
你强行转换，最后只能一拍两散。我只是不明白为什么这种强行转换没有在compilation time发现并报错，
而对于Sibling Cast则兴致勃勃的报：

1 public class SiblingCastTest {
2 public static void main(String [] args){
3 Integer ia = 1;
4 Long la = (Long)ia; //sibling cast error
5 }
6 }

复制代码

于是，一个正确的转换版本大概如下：

1 public class ObjectArrayClassCastTest {
2 public static void main(String args []){
3 Object[] oa = new Object[3];
4 oa[0] = "Hello";
5 oa[1] = "world";
6 oa[2] = "!";
7
8 String[] sa = new String[oa.length];
9 System.arraycopy(oa, 0, sa, 0, oa.length);
10 for(String s : sa) {
11 System.out.println(s);
12 }
13 }
14 }

复制代码

显然，这个转换是老式的转换。我们需要新潮的，能一步到位的，让人看了身心俱畅的。。。
试看一下这个如何：

1 public class ObjectArrayClassCastTest {
2 public static void main(String args []){
3 Object[] oa = new Object[3];
4 oa[0] = "Hello";
5 oa[1] = "world";
6 oa[2] = "!";
7
8 String[] sa = new String[oa.length];
9 //System.arraycopy(oa, 0, sa, 0, oa.length);
10 sa = cast(oa, sa);
11 for(String s : sa) {
12 System.out.println(s);
13 }
14 }
15
16 public static <T> T[] cast(Object[] oa, T[] ta){
17 System.arraycopy(oa, 0, ta, 0, oa.length);
18 return ta;
19 }
20 }

复制代码

我们通过Generic把System.arraycopy()这个怪物藏起来了。由于返回值就是ta本身，不会引起
什么不和谐事件。

不过，老实说，如果看一下bytecode，你还真想骂人：
cast()方法的

public static java.lang.Object[] cast(java.lang.Object[], java.lang.Object[]);
Code:
0: aload_0
1: iconst_0
2: aload_1
3: iconst_0
4: aload_0
5: arraylength
6: invokestatic #11; //Method java/lang/System.arraycopy:(Ljava/lang/Object;ILjava/lang/Object;II)V
9: aload_1
10: areturn

复制代码

调用部分bytecode

28: invokestatic #7; //Method cast:([Ljava/lang/Object;[Ljava/lang/Object;)[Ljava/lang/Object;
31: checkcast #8; //class "[Ljava/lang/String;"

复制代码

看出和上面那个有什么区别？没有，还是Object[]和String[]转换，因为Generic Erasure，T[]被当成Object[]来看。
然而这个没有错……郁闷。我想我在某个地方忽略了什么吧。

OK，不去深究这东西的语法意义。就上面的程序本身来说，还是有问题的。因为我们不能永远确保两个数组等长。
在不等长的时候我们应该怎样做？

太长了，分另一个贴再说。

[ 本帖最后由 key 于 30-6-2009 10:53 编辑 ]

作者: key 时间: 30-6-2009 11:38
标题: 绝杀：reflect
上回说到，如果传入cast()的目标数组长度小于源数组，怎么办呢？

怎么办？怎么办？凉拌当然不行了。

由于Generic Erasure的存在，让我们没有可能采用类似 new T[X] 这样的简单快捷的实现，
可以做的只能是采用
obj.getClass().newInstance()
这样的方法了。然而，obj.getClass().newInstance()只能产生一个元素，怎样生成一串呢？

各位观众，现在，我们隆重介绍：java.lang.reflect.Array 同学，请大家鼓掌！

java.lang.reflect.Array.newInstance(Class<?> componentType, int length);

还有一个需要注意的是，如果我们对于cast(Object[] oa, T[] ta)中的ta采用
Class c = ta[0].getClass();
来获得类，那是很不专业的，因为ta[0]通常是null值，我们不能用它来处理一个non-static method？
于是我们用Class c = ta.getClass().getComponentType();

下面是参考代码，我留了一个有bug的版本做参考。cast2()是可用的

1 public class ObjectArrayClassCastTest {
2 public static void main(String args []){
3 Object[] oa = new Object[3];
4 oa[0] = "Hello";
5 oa[1] = "world";
6 oa[2] = "!";
7
8 String[] sa = new String[oa.length];
9 String[] sa1 = new String[0];
10 //System.arraycopy(oa, 0, sa, 0, oa.length);
11 sa = cast2(oa, sa);
12 sa1 = cast2(oa, sa1);
13 for(String s : sa) {
14 System.out.println(s);
15 }
16 for(String s : sa1) {
17 System.out.println(s);
18 }
19 }
20
21 //with bug
22 public static <T> T[] cast(Object[] oa, T[] ta){
23 if(ta.length >= oa.length)
24 System.arraycopy(oa, 0, ta, 0, oa.length);
25 else
26 ta = cast(oa, ta[0]);
27 return ta;
28 }
29
30 public static <T> T[] cast(Object[] oa, T obj){
31 Class c = obj.getClass();
32 Object o = java.lang.reflect.Array.newInstance(c, oa.length);
33 T[] to = (T[])o;
34 System.arraycopy(oa, 0, to, 0, oa.length);
35 return to;
36 }
37
38 public static <T> T[] cast2(Object[] oa, T[] ta){
39 if(ta.length < oa.length)
40 ta = (T[])java.lang.reflect.Array.newInstance(
41 ta.getClass().getComponentType(), oa.length);
42 System.arraycopy(oa, 0, ta, 0, oa.length);
43 return ta;
44 }
45 }

复制代码

对于Collection.toArray(T[])的实现，请参考java SDK的源代码。
事实上在java SDK src中采用的是Arrays.copyOf()方法来简化实现，而copyOf()的实质就是我上面说
的这一堆东西。所以说，原版本大致上就是和我这个差不多了。
关于这个话题说得有点远，不好意思。

[ 本帖最后由 key 于 30-6-2009 10:42 编辑 ]

作者: klux 时间: 30-6-2009 12:15
期待下文
另外能顺便分析一下执行效率就更好了

作者: key 时间: 30-6-2009 12:18
标题: 继续Helper Classes：排序与搜索
在Arrays和Collections中，排序和搜索都是两者共有的，而概念一致，格式雷同。
只是由于数组primitive array的互不兼容性，所以在Arrays中有多个版本。

为了简化起见，这里只列出范型部分
Natural Ordering
void Arrays.sort(Object[] a);
void Arrays.sort(Object[] a, form, to);

<T extends Comparable<? super T>> void
Collections.sort(List<T>)

采用第三方Comparator
<T> void Arrays.sort(T[] ta, Comparator<? super T>c);
<T> void Arrays.sort(T[] ta, from, to, Comparator<? super T>c);

<T> void Collections.sort(List<T>, Comparator<? super T> c);

注意
这里Comparator<? super T>采用了super，而不是extends。记得我前面提到PECS吗？
因为Comparator.compare(T a1, T a2)是对List<T>中的无素进行消费，C->Super，
所以这里采用了Super。

注意二
看到Arrays和Collections在接受范型参数是有什么不同吗？
对于自然排序的版本，Arrays直接采用了Object[]来做输入。而Collections则很认真的
用<A extends Comparator<? super A>>来做范型参数。
后面那个因为有Comparator，对于T自然就没有什么限制了。

请看下面的代码：

1 import java.util.*;
2
3 public class SortTest {
4
5 //static class ST implements Comparable<ST>{
6 static class ST /* implements Comparable<ST> */ {
7 private int x;
8
9 public ST(int x) {
10 this.x = x;
11 }
12
13 public int compareTo(ST o) {
14 return x - o.x;
15 }
16 }
17
18 public static void main(String args[]){
19 List<ST> list = new ArrayList<ST>();
20
21 Collections.sort(list);
22 }
23 }

复制代码

这个代码编译是通不过的。
但改成下面的代码，编译则没有问题：

1 import java.util.*;
2
3 public class SortTest {
4
5 //static class ST implements Comparable<ST>{
6 static class ST /* implements Comparable<ST> */ {
7 private int x;
8
9 public ST(int x) {
10 this.x = x;
11 }
12
13 public int compareTo(ST o) {
14 return x - o.x;
15 }
16 }
17
18 public static void main(String args[]){
19 List<ST> list = new ArrayList<ST>();
20 list.add(new ST(1));
21 list.add(new ST(2));
22
23 //Collections.sort(list);
24 Arrays.sort(list.toArray(new ST[0]));
25 }
26 }

复制代码

运行就会出现ClassCastException:

$ java SortTest
Exception in thread "main" java.lang.ClassCastException: SortTest$ST cannot be cast to java.lang.Comparable
at java.util.Arrays.mergeSort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at SortTest.main(SortTest.java:24)

复制代码

作者: key 时间: 30-6-2009 12:43
标题: 继续Helper Classes：排序与搜索[下]
关于搜索，似乎没有什么特别要说的话题。Arrays和Collections都提供了binarySearch()，找到就返回一个正值，
找不到就返回一个负值。

但这里需要注意几个问题：
返回值
如果返回正值，那好办。
返回负值呢？这个值的绝对值为搜索key的插入位置。

真的是binary search吗？
对于Array，这个问题就不大了。但对于List，binary search就未必一定是
binary search，比如LinkedList，采用的就是iterative search了，这样则是O(n)的时间

如果之前没有排序，会怎样？
the result is undefined... API document对这个问题抱着很潇洒的态度。

重键问题
binary search的解决方案都一样：就是返回其中一个，具体哪个？没所谓

上错花轿又会怎样？
看看Collections的方法定义：
static <T> int
Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)

如果你试试下面的程序，就知道不存在上错花娇的情况了：

1 import java.util.*;
2
3 public class SortTest {
4
5 static class ST implements Comparable<ST>{
6 private int x;
7
8 public ST(int x) {
9 this.x = x;
10 }
11
12 public int compareTo(ST o) {
13 return x - o.x;
14 }
15 }
16
17 public static void main(String args[]){
18 List<ST> list = new ArrayList<ST>();
19 list.add(new ST(1));
20 list.add(new ST(2));
21
22 Collections.sort(list);
23 int x = Collections.binarySearch(list, new Date());
24 }
25 }

复制代码

然而，因为各种原因，我们可能会写出这样的代码：

1 import java.util.*;
2
3 public class SortTest {
4
5 static class ST implements Comparable<ST>{
6 private int x;
7
8 public ST(int x) {
9 this.x = x;
10 }
11
12 public int compareTo(ST o) {
13 return x - o.x;
14 }
15 }
16
17 public static void main(String args[]){
18 List list = new ArrayList();
19 list.add(new ST(1));
20 list.add(new ST(2));
21 list.add(new Date());
22
23 List<ST> list2 = list;
24
25 Collections.sort(list2);
26 int x = Collections.binarySearch(list2, new ST(1));
27 }
28 }

复制代码

这样就有可能导致问题被迟延到runtime才发现。如果真的是这样，ClassCastException是不二之选。

[ 本帖最后由 key 于 30-6-2009 12:08 编辑 ]

作者: key 时间: 30-6-2009 13:29
标题: 继续Helper Class：copy 与copyOf 与copyOfRange
使用Arrays或Collections都可以实现集合的复制。
Arrays有copyOf和copyOfRange
而
Collections则有copy

相比较之下，Collections的版本我们很容易实现。因为Collection接口有addAll()方法，
调用一下就成了。情况真的是这样吗，答案是否定的。

而关于Arrays.copyOf()，我前面有说过用java.lang.reflect.Array.newInstance()的使用，
而copyOf()则正是采用了newInstance()来生成一个新的数组。注意Arrays.copyOf()返回
数组，而Collections.copy()的返回值为void。

下面重点补充一下Collections.copy()。这物体比较counterintuitive。它的目标是制作一个
从次序上一致的List，虽然original可能是LinkedList，而target是ArrayList。
于是，它采用的是ListIterator来进行逐个复制。
由于ListIterator的使用，使得这个复制有一个前提：目标list的长度必须大于源list，
否则就人为的生成IndexOutofBoundException异常。

简单来说，Arrays.copyOf()总是生成新数组新元素，而Collections.copy()则是在参数指向
的referece指向的list之间copy。

作者: key 时间: 30-6-2009 13:42
标题: 继续Helper Classes：equals
数组是类，但数组是特殊的类。它没有自己的overridden equals()方法。
于是就需要通过Helper class进行实现了。

而implements Collection的类可以自定义equals()方法，所以在Collections
上并不提供equals()

我们可以顺例看一个List的equals方法。根据AbstractList中的实现两个List进行比较，
只需要他们的元素逐次相等，则认为是两个相等的list。也就是说，LinkedList与ArrayList
有机会相等。

1 import java.util.*;
2
3 public class ListEqualsTest{
4 public static void main(String [] args){
5 List<String> list1 = new LinkedList<String>();
6 List<String> list2 = new ArrayList<String>();
7
8 list1.add("hello");
9 list1.add("world");
10 list1.add("!");
11
12 list2.add("hello");
13 list2.add("world");
14 list2.add("!");
15
16 System.out.println(list1.equals(list2));
17 }
18 }

复制代码

比较相等的方法在Collections中没有，比较不等则有一个：
static boolean Collections.disjoint(Collection<?> c1, Collection<?> c2)

这个方法是用来判断两个集合c1和c2当中有没有元素是相等的。比较的方法就是
通过采用Collection.contains()接口方法。

作者: key 时间: 30-6-2009 13:47
标题: 继续Helper Classes：fill
填充。这是一个无比简单的方法，不明白为什么要写入Helper class中，而且两个都写了。

作者: key 时间: 30-6-2009 15:13
标题: 独自上东莞：Collections.checkedXXXXX()
Arrays相对于Collections来说简单很多，基本的方法已经说得差不多。现在开始讨论一下
Collections的个性了。

首先我们来看看checkedXXXX系列方法。

什么是CheckedXXXX呢？由于历史原因，以及编译定义的原因，Java采用了Generic Erasure
的方法来处理泛型；而对于历史代码又采用了兼容的方式，这就存在某些地方，我们
“不小心”向集合加入了一些不兼容的元素。而在程序运行的某个时候，这些元素终于
在沉黩中暴发，拿走我们所有的credit。。。。但我们想知道，这些元素到底是由哪个
pk加入去，于是我们翻呀找呀，几万几十万行代码一行行的找……找到花儿也谢了……

现在，神要打救你了。听着，用checked collections吧。通过Collections.checkedXXXX()
方法，把你的Collection, List, Set, Map转成checked类型。这个类型有一个typeChecked()
方法，用于守护每个add()方法，一旦发现有异类，马上报告。（当然，如果你有事没事
catch(Exception e)，那只是真的问上帝了）。

由于checked collections对每次add操作都做typecheck，花了extra时间，一般只在调试时
用一下，过了就转回正常的collection。

作者: key 时间: 30-6-2009 15:33
标题: 独自上东莞：reverse/reverseOrder
如果你需要把整个List反过来，可以直接用Collections.reverse()来操作，保证称心满意。

而reverseOrder()又是什么？如果你看过Collections.java的实现，你会大吃一惊。
不含参数的reverseOrder

3301 public static <T> Comparator<T> reverseOrder() {
3302 return (Comparator<T>) REVERSE_ORDER;
3303 }

复制代码

这是Collections.reverseOrder()的实现。

那REVERSE_ORDER又是何方神圣？

3305 private static final Comparator REVERSE_ORDER = new ReverseComparator();

复制代码

几位观众，请注意REVERSE_ORDER是un-parameterized的。

我们再来看ReverseComparator类的实现：

3310 private static class ReverseComparator<T>
3311 implements Comparator<Comparable<Object>>, Serializable {
3312
3313 // use serialVersionUID from JDK 1.2.2 for interoperability
3314 private static final long serialVersionUID = 7207038068494060240L;
3315
3316 public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3317 return c2.compareTo(c1);
3318 }
3319
3320 private Object readResolve() { return reverseOrder(); }
3321 }

复制代码

注意Line-3311，实现的是Comparator<Comparable<Object>>接口。
按我非常naive的小心灵，想的只是：
private static class ReverseComparator<T>
implements Comparator<T> ...
如果真是这样，那Line-3316-3318就compiler error了。
但这样一来，那个所谓的<T>就有如空中浮云，水中映月，虚无呀飘渺呀，
根本就没有任何关系。

一句话，这个实现是利用了Java Generic的语法漏洞，crack the system！

含参数的reverseOrder
反观带了参数的reverseOrder就老实多了，传入一个Comparactor<T>，然后把次序反过来即可。

其实，为什么不能把那个无参数的实现删掉呢？无论传个Comparator还是Comparable过来，
都能让语法变得严谨，不落人话柄。。。。何苦来着？

作者: key 时间: 30-6-2009 15:39
标题: 独自上东莞：洗牌
Collections中有很多洗牌操作。——不是只有一个吗？你可能会反问。

是的，持证上岗的洗牌方法只有一个，但搞小动作的太多。
这包括了：
.reverse(List<?> list)
.rotate(List<?> list, int distance)
.shuffle(List<?> list)
.shuffle(List<?> list, Random rand)
.swap(List<?> list, int x, int y)

这些大大小小的变换次序的操作，我都称之为洗牌，只是大洗与小洗的区别。

作者: key 时间: 30-6-2009 16:04
标题: 独自上东莞：线程安全
有一个Java的小秘密：如果Java Document推荐你用某个东西，而不推荐用另一个东西，
那被推荐的那个十有八九是非线程安全的，不被推荐的则是线程安全的。

试看看：
StringBuffer, StringBuilder
Vector, ArrayList
Hashtable, HashMap

没错了吧？关于List和Map，更有“离谱”的说法是：你不要再依赖于Vector或Hashtable来找
回那一点点的线程安全，如果你真的需要线程安全，请用Collections.synchronizedXXX() wraps
你的Collections....

看来JLS灭Hastable/Vector之心那是坚决呀！

本文还没有涉及到的方法有：
.unmodifiableXXX()
.singletonXXX()
.indexOf...()
等

作者: key 时间: 30-6-2009 16:06
标题: Iterator与ListIterator
区别是：前者只能向前，后者可以向后。。。。

欢迎光临 FreeOZ论坛 (https://www.freeoz.org/ibbs/)