Java集合框架之视图与包装器

通过使用视图可以获得其他的实现了集合接口和映射表接口的对象。

轻量级集包装器

Arrays类的静态方法asList将返回一个包装了Java数组的List包装器。返回的对象不是ArrayList,而是一个视图对象,其来自于Arrays的内部类,源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
{
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;

ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}

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

@Override
public Object[] toArray() {
return a.clone();
}

@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
int size = size();
if (a.length < size)
return Arrays.copyOf(this.a, size,
(Class<? extends T[]>) a.getClass());
System.arraycopy(this.a, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

@Override
public E get(int index) {
return a[index];
}

@Override
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}

@Override
public int indexOf(Object o) {
E[] a = this.a;
if (o == null) {
for (int i = 0; i < a.length; i++)
if (a[i] == null)
return i;
} else {
for (int i = 0; i < a.length; i++)
if (o.equals(a[i]))
return i;
}
return -1;
}

@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}

@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(a, Spliterator.ORDERED);
}

@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
for (E e : a) {
action.accept(e);
}
}

@Override
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
E[] a = this.a;
for (int i = 0; i < a.length; i++) {
a[i] = operator.apply(a[i]);
}
}

@Override
public void sort(Comparator<? super E> c) {
Arrays.sort(a, c);
}
}

可以看到这个内部类并没有实现add和remove等方法,所以调用改变数组大小的所有方法都会抛出一个Unsupported OperationException异常(因为其继承自AbstractList,而该父类中add和remove等默认实现是抛出异常)。

Collections.nCopies(n, anObject)方法将返回一个实现了List接口的不可修改的对象,看起来像一个包含n个元素,每个元素都是一个anObject的对象,其源码如下:

1
2
3
4
5
public static <T> List<T> nCopies(int n, T o) {
if (n < 0)
throw new IllegalArgumentException("List length = " + n);
return new CopiesList<>(n, o);
}

而CopiesList的源码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
private static class CopiesList<E>
extends AbstractList<E>
implements RandomAccess, Serializable
{
private static final long serialVersionUID = 2739099268398711800L;

final int n;
final E element;

CopiesList(int n, E e) {
assert n >= 0;
this.n = n;
element = e;
}

public int size() {
return n;
}

public boolean contains(Object obj) {
return n != 0 && eq(obj, element);
}

public int indexOf(Object o) {
return contains(o) ? 0 : -1;
}

public int lastIndexOf(Object o) {
return contains(o) ? n - 1 : -1;
}

public E get(int index) {
if (index < 0 || index >= n)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+n);
return element;
}

public Object[] toArray() {
final Object[] a = new Object[n];
if (element != null)
Arrays.fill(a, 0, n, element);
return a;
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
final int n = this.n;
if (a.length < n) {
a = (T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), n);
if (element != null)
Arrays.fill(a, 0, n, element);
} else {
Arrays.fill(a, 0, n, element);
if (a.length > n)
a[n] = null;
}
return a;
}

public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > n)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
return new CopiesList<>(toIndex - fromIndex, element);
}

// Override default methods in Collection
@Override
public Stream<E> stream() {
return IntStream.range(0, n).mapToObj(i -> element);
}

@Override
public Stream<E> parallelStream() {
return IntStream.range(0, n).parallel().mapToObj(i -> element);
}

@Override
public Spliterator<E> spliterator() {
return stream().spliterator();
}
}

实际上字符串对象只存储一次,所以付出的存储代价很小。

子范围

 很多集合都支持子范围视图的建立。

如使用subList方法来获得一个列表的子范围视图:List group2 = staff.subList(10, 20);

可以将任何操作应用于子范围,并且能够自动地反映整个列表的情况,例如删除整个子范围:group2.clear();

其中ArrayList.SubList的源码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;

SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}

public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}

public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}

public int size() {
checkForComodification();
return this.size;
}

public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}

public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}

protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}

public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;

checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}

public Iterator<E> iterator() {
return listIterator();
}

public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;

return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;

public boolean hasNext() {
return cursor != SubList.this.size;
}

@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}

public boolean hasPrevious() {
return cursor != 0;
}

@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}

@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}

public int nextIndex() {
return cursor;
}

public int previousIndex() {
return cursor - 1;
}

public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();

try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

public void add(E e) {
checkForComodification();

try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}

那么list.subList(from, to).clear();是怎么实现的呢,可以看到SubList没有实现clear方法,其父类AbstractList中对应的缺省实现为:

1
2
3
public void clear() {
removeRange(0, size());
}

而removeRange在SubList中是有实现的,parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex);,其中parent为父列表,parentOffset为子列表在父列表中的偏移,所以这个操作最终还是交给父列表实现的。
对于有序集和映射表,可以使用排列顺序而不是元素位置建立子范围。

不可修改的视图

Collections还有几个方法,用于产生集合的不可修改视图。这些视图对现有集合增加了一个运行时的检查。如果发现试图对集合进行修改,就抛出异常,同时这个集合将保持未修改的状态。
可以使用下面6种方法获得不可修改视图:

  • Collections.unmodifiableCollection
  • Collections.unmodifiableList
  • Collections.unmodifiableSet
  • Collections.unmodifiableSortedSet
  • Collections.unmodifiableMap
  • Collections.unmodifiableSortedMap

这个视图的访问器方法将从源集合中获取值,但是所有的更改器方法都已经被重新定义为抛出UnsupportedOperationException异常,而不是将调用传递给底层集合。
不可修改视图并不是集合本身不可修改。仍然可以通过集合的原始引用对集合进行修改。并且仍然可以让集合的元素调用更改器方法。
由于视图只是包装了接口而不是实际的集合对象,所以只能访问接口中定义的方法。

同步视图

类库的设计者使用视图机制来确保常规集合的线程安全,而不是实现线程安全的集合类。例如,Collections类的静态方法synchronizedMap方法可以将任何一个映射表转换成具有同步访问方法的Map:
Map<String, Employee> map = Collections.synchronizedMap(new HashMap<String, Employee>());

其中遍历视图时应该由用户手动将操作置于同步块中,如文档所说:

1
2
3
4
5
6
7
8
9
10
11
12
It is imperative that the user manually synchronize on the returned map when iterating over any of its collection views:
Map m = Collections.synchronizedMap(new HashMap());
...
Set s = m.keySet(); // Needn't be in synchronized block
...
synchronized (m) { // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

Failure to follow this advice may result in non-deterministic behavior.

检查视图

Java SE 5.0增加了一组“检查”视图,用来对泛型类型发生问题时提供调试支持。

1
2
3
ArrayList<String> strings = new ArrayList<>();
ArrayList rawList = strings;
rawList.add(new Date()));

这个错误的add命令在运行时检测不到。相反,只有在稍后的另一部分代码中调用get方法,并将结果转化为String时,这个类才会抛出异常。

检查视图可以探测到这类问题。下面定义了一个安全列表:
List<String> safeStrings = Collections.checkedList(strings, String.class);

视图中的add方法将检测插入的对象是否属于给定的类(如上述语句中的String.class),如果不属于给定的类,就立即抛出一个ClassCastExceotion

即使使用raw list,其也能在执行add方法时探查到类型转化错误。

1
2
List list = Collections.checkedList(strings, String.class);
list.add(new Date()); //This will be detected once add method is invoked.

因为在方法中增加了对类型的检查,这样确保在add时就快速失败。

1
2
3
public void add(int index, E element) {
list.add(index, typeCheck(element));
}

被检查视图受限于虚拟机可以运行的运行时检查。例如,对于ArrayList<Pair<String>>,由于虚拟机有一个单独的“原始”Pair类,所以,无法阻止插入Pair<Date>(类型擦除)。