一、Collection接口
从《Java集合:整体结构》一文中我们知道所有的List和Set都继承自Collection接口,该接口类提供了集合最基本的方法,虽然List接口和Set等都有一些自己独有的方法,但是基本的操作类似。我们先看下Collection接口提供的方法:
总体上可以将Collection的方法分为以下几大类:
1、增加(add/addAll)
2、删除(remove/removeAll/clear/retainAll)
3、查询(contain/containAll/iterator/size/isEmpty)
4、转数组(toArray/toArray(T[]))
直接实现该接口的类只有AbstractCollection类,该类也只是一个抽象类,提供了对集合类操作的一些基本实现。List和Set的具体实现类基本上都直接或间接的继承了该类。为了方便以后更清晰的理解这些类的实现,我们先看下AbstractCollection的实现。
二、AbstractCollection源码解析
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 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 | package java.util; public abstract class AbstractCollection<E> implements Collection<E> { protected AbstractCollection() { } public abstract Iterator<E> iterator(); public abstract int size(); //判断集合中是否有数据 public boolean isEmpty() { return size() == 0 ; } /** * 判断是否包含指定的元素 * (1)如果参数为null,查找值为null的元素,如果存在,返回true,否则返回false。 * (2)如果参数不为null,则根据equals方法查找与参数相等的元素,如果存在,则返回true,否则返回false。 * 注意:这里必须对null单独处理,否则null.equals会报空指针异常 */ public boolean contains(Object o) { Iterator<E> it = iterator(); if (o== null ) { while (it.hasNext()) if (it.next()== null ) return true ; } else { while (it.hasNext()) if (o.equals(it.next())) return true ; } return false ; } /** * 功能:将集合元素转换为数组 * 实现: * (1)创建一个数组,大小为集合中元素的数量 * (2)通过迭代器遍历集合,将当前集合中的元素复制到数组中(复制引用) * (3)如果集合中元素比预期的少,则调用Arrays.copyOf()方法将数组的元素复制到新数组中,并返回新数组,Arrays.copyOf的源码在后续文章中会分析. * (4)如果集合中元素比预期的多,则调用finishToArray方法生成新数组,并返回新数组,否则返回(1)中创建的数组 */ public Object[] toArray() { Object[] r = new Object[size()]; Iterator<E> it = iterator(); for ( int i = 0 ; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; } /** * 功能:通过泛型约束返回指定类型的数组 * 实现: * (1)如果传入数组的长度的长度大于等于集合的长度,则将当前集合的元素复制到传入的数组中 * (2)如果传入数组的长度小于集合的大小,则将创建一个新的数组来进行集合元素的存储 */ public <T> T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator<E> it = iterator(); for ( int i = 0 ; i < r.length; i++) { //集合元素大小小于数组的长度 if (! it.hasNext()) { // fewer elements than expected if (a == r) { //如果数组是参数中的数组,则将剩余部分的值都设置为null r[i] = null ; // null-terminate } else if (a.length < i) { //如果传入的数组长度小于集合长度,则通过Arrays.copyOf将之前数组中的元素复制到新数组中 return Arrays.copyOf(r, i); } else { //如果传入数组的长度比集合大,则将多的元素设置为空 System.arraycopy(r, 0 , a, 0 , i); if (a.length > i) { a[i] = null ; } } return a; } r[i] = (T)it.next(); } // more elements than expected //集合元素大小大于数组的长度 return it.hasNext() ? finishToArray(r, it) : r; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ; /** * 功能:数组扩容 * (1)当数组索引指向最后一个元素+1时,对数组进行扩容:即创建一个更长的数组,然后将原数组的内容复制到新数组中 * (2)扩容大小:cap + cap/2 +1 * (3)扩容前需要先判断是否数组长度是否溢出 * 注意:这里的迭代器是从上层的方法(toArray)传过来的,并且这个迭代器已执行了一部分,而不是从头开始迭代的 */ private static <T> T[] finishToArray(T[] r, Iterator<?> it) { int i = r.length; while (it.hasNext()) { int cap = r.length; if (i == cap) { int newCap = cap + (cap >> 1 ) + 1 ; // overflow-conscious code if (newCap - MAX_ARRAY_SIZE > 0 ) newCap = hugeCapacity(cap + 1 ); r = Arrays.copyOf(r, newCap); } r[i++] = (T)it.next(); } // trim if overallocated return (i == r.length) ? r : Arrays.copyOf(r, i); } /** * 判断数组容量是否溢出,最大为整型数据的最大值 */ private static int hugeCapacity( int minCapacity) { if (minCapacity < 0 ) // overflow throw new OutOfMemoryError ( "Required array size too large" ); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * 未实现 */ public boolean add(E e) { throw new UnsupportedOperationException(); } /** * 功能:移除指定元素 * (1)如果参数为null,则找到第一个值为null的元素,并将其删除,返回true,如果不存在null的元素,返回false。 * (2)如果参数不为null,则根据equals方法找到第一个与参数相等的元素,并将其删除,返回true,如果找不到,返回false。 */ public boolean remove(Object o) { Iterator<E> it = iterator(); if (o== null ) { while (it.hasNext()) { if (it.next()== null ) { it.remove(); return true ; } } } else { while (it.hasNext()) { if (o.equals(it.next())) { it.remove(); return true ; } } } return false ; } /** * 遍历参数集合,依次判断参数集合中的元素是否在当前集合中, * 只要有一个不存在,则返回false * 如果参数集合中所有的元素都在当前集合中,则返回true */ public boolean containsAll(Collection<?> c) { for (Object e : c) if (!contains(e)) return false ; return true ; } /** * 遍历参数集合,依次将参数集合中的元素添加当前集合中 */ public boolean addAll(Collection<? extends E> c) { boolean modified = false ; for (E e : c) if (add(e)) modified = true ; return modified; } /** * 功能:移除参数集合的元素 * (1)获取当前集合的迭代器进行遍历 * (2)如果当前集合中的元素包含在参数集合中,则删除当前集合中的元素 * 注:只要参数集合中有任何一个元素在当前元素中,则返回true,表示当前集合有发送变化,否则返回false。 */ public boolean removeAll(Collection<?> c) { boolean modified = false ; Iterator<?> it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true ; } } return modified; } /*** * 功能:求参数集合与当前集合的交集 * (1)获取当前集合的迭代器进行遍历 * (2)如果当前集合中的元素不在参数集合中,则将其移除。 * 注意:如果当前集合是参数集合中的子集,则返回false,表示当前集合未发送变化,否则返回true。 */ public boolean retainAll(Collection<?> c) { boolean modified = false ; Iterator<E> it = iterator(); while (it.hasNext()) { if (!c.contains(it.next())) { it.remove(); modified = true ; } } return modified; } //删除所有元素 public void clear() { Iterator<E> it = iterator(); while (it.hasNext()) { it.next(); it.remove(); } } public String toString() { Iterator<E> it = iterator(); if (! it.hasNext()) return "[]" ; StringBuilder sb = new StringBuilder(); sb.append( '[' ); for (;;) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append( ']' ).toString(); sb.append( ',' ).append( ' ' ); } } } |
整体上来说,AbstractCollection的源码还是比较容易理解,尤其是集合增、删、查等操作都非常简单。比较复杂的是关于集合转数组的操作,有几个点不是特别好理解,这里解释一下:
(1)MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,为什么最大长度要减8,根据官方的解释:
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
这段话的意思就是有的虚拟机实现,数组对象的头部会占用这8个字节。
(2)转换为数组的操作时,为什么长度会比size()长或者短?这个的原因还是考虑到并发情况下,当然,在并发环境上面的机制不一定可行,如在ArrayList中就重写了该方法,遇到size()与hasNext不一致的情况会直接报错。不过有些场景下可以通过这种方式保持弱一致性,具体后续遇到这种情况的时候再具体说明。
(3)这里面执行数组拷贝时,用到两个方法,一个是Arrays.copyOf,另一个是System.arraycopy(r, 0, a, 0, i)方法,这两个方法的区别也会在后续文章中讨论,这里暂不细说。
三、总结
本文主要分析了AbstractCollection类的源码,很多实现类会重写AbstractCollection中已实现的方法。但是弄明白AbstractCollection源码之后,再看其子类的实现,会更容易理解其源码实现背后的设计原因,其实,很多源码本身不难理解,难理解的地方在于其背后的设计思想和原因,这也是我们去看源码和真正要学习的东西。