Collections.shuffle()中关于wildcard capture的源码分析

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@SuppressWarnings({"rawtypes", "unchecked"})
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray();

// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));

// Dump array back into list
// instead of using a raw type here, it's possible to capture
// the wildcard but it will require a call to a supplementary
// private method
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}

这是一个打乱指定List的洗牌算法,当List长度小于SHUFFLE_THRESHOLD(定义为5)或者是RandomAccess的实例时,直接以List的数据结构进行打乱,否则转为数组再打乱,最后转储回List。推测是List长度比较大时,直接swap效率降低,所以要转成数组处理。方法暂时没什么问题,主要是源码中部分注释不是很理解,整理如下。

注释详解

instead of using a raw type here, it’s possible to capture the wildcard but it will require a call to a supplementary private method.

什么是capture the wildcard?

一开始猜测是在洗牌算法中的特有名词,后来在Java官方文档中找到了答案1

在某些情况下,编译器可以推断wildcard的类型。举例来说,一个list可能被定义为List<?>,但是,当评估这个表达式时,编译器会从代码中推断出一个特定的类型。这种现象被称为wildcard capture。

简而言之,wildcard capture 指的是编译器从代码里推断泛型的现象

wildcard capture会在什么情况下发生错误?

继续看文档。

大多数情况下,你不需要担心wildcard capture出错。除非你看到报错中包含关键词:”capture of”。

比如这段代码将在编译时报错:

1
2
3
4
5
6
7
8
import java.util.List;

public class WildcardError {

void foo(List<?> i) {
i.set(0, i.get(0));
}
}

在这个例子中,编译器将输入参数i处理为Object类型。当foo()调用List.set(int, E)时,编译器不能确定将要插入list中的Object类型,产生一个错误。当这种类型的错误发生时,通常它的意思是编译器认为你正将错误的类型分配给一个变量。在Java语言中加入泛型的原因在此-编译时强制类型安全

这里可以看到报错信息,编译器无法识别 i.get(0) 是何种类型,所以报错。

为什么capture the wildcard就需要调用额外的私有方法?

为了解决出现上述的wildcard capture错误,可以写一个私有辅助方法(Helper Method),比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class WildcardFixed {

void foo(List<?> i) {
fooHelper(i);
}


// Helper method created so that the wildcard can be captured
// through type inference.
private <T> void fooHelper(List<T> l) {
l.set(0, l.get(0));
}

}

Thanks to the helper method, the compiler uses inference to determine that T is CAP#1, the capture variable, in the invocation. The example now compiles successfully.

多亏了辅助方法,编译器在调用中通过推断确定CAP#1(捕获变量)的类型是T。示例现在可以成功编译了。

源码中的应用

现在,回到Collections.shuffle(),StackOverflow的Sweeper大佬给出了解释2

在shuffle()方法这个例子中,你可以将“转储数组”的操作提取到泛型辅助方法中:

1
2
3
4
5
6
7
8
9
10
private static <T> void dumpArray(Object[] arr, List<T> list) {
ListIterator<T> it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set((T)arr[i]);
}
}

//...
dumpArray(arr, list);

这就是注释中capture wildcard需要调用额外私有方法(即上述辅助方法)的原因。

参考


[1] Java官方文档


[2] StackOverflow

0%