前言

(PS:上周由于准备自考,更新延误了一些,见谅!)
AbstractCollection类是Collection接口的一个实现类,它只是为了给我们提供了一些最基础的接口的实现,在实际的应用中,我们并不会去使用这个类来封装一些信息,接下来我们首先去看一下这个类的继承关系图。

结构图

Java基础系列(四十):集合之AbstractCollection - 图1
由此可以看出AbStractCollection只是实现了Collection接口,并没有实现或者继承其他的类或者接口。接下来,我们来看一下这个类的源码,看看会有什么收获。

源码

  1. package java.util;
  2. //TAG 1
  3. public abstract class AbstractCollection<E> implements Collection<E> {
  4. protected AbstractCollection() {
  5. }
  6. public abstract Iterator<E> iterator();
  7. public abstract int size();
  8. //TAG 2
  9. public boolean isEmpty() {
  10. return size() == 0;
  11. }
  12. //TAG 3
  13. public boolean contains(Object o) {
  14. Iterator<E> it = iterator();
  15. if (o==null) {
  16. while (it.hasNext())
  17. if (it.next()==null)
  18. return true;
  19. } else {
  20. while (it.hasNext())
  21. if (o.equals(it.next()))
  22. return true;
  23. }
  24. return false;
  25. }
  26. //TAG 3
  27. public Object[] toArray() {
  28. Object[] r = new Object[size()];
  29. Iterator<E> it = iterator();
  30. for (int i = 0; i < r.length; i++) {
  31. if (! it.hasNext())
  32. return Arrays.copyOf(r, i);
  33. r[i] = it.next();
  34. }
  35. return it.hasNext() ? finishToArray(r, it) : r;
  36. }
  37. //TAG 3
  38. @SuppressWarnings("unchecked")
  39. public <T> T[] toArray(T[] a) {
  40. int size = size();
  41. T[] r = a.length >= size ? a :
  42. (T[])java.lang.reflect.Array
  43. .newInstance(a.getClass().getComponentType(), size);
  44. Iterator<E> it = iterator();
  45. for (int i = 0; i < r.length; i++) {
  46. if (! it.hasNext()) {
  47. if (a == r) {
  48. r[i] = null;
  49. } else if (a.length < i) {
  50. return Arrays.copyOf(r, i);
  51. } else {
  52. System.arraycopy(r, 0, a, 0, i);
  53. if (a.length > i) {
  54. a[i] = null;
  55. }
  56. }
  57. return a;
  58. }
  59. r[i] = (T)it.next();
  60. }
  61. return it.hasNext() ? finishToArray(r, it) : r;
  62. }
  63. //TAG 4
  64. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  65. //TAG 5
  66. @SuppressWarnings("unchecked")
  67. private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
  68. int i = r.length;
  69. while (it.hasNext()) {
  70. int cap = r.length;
  71. if (i == cap) {
  72. int newCap = cap + (cap >> 1) + 1;
  73. if (newCap - MAX_ARRAY_SIZE > 0)
  74. newCap = hugeCapacity(cap + 1);
  75. r = Arrays.copyOf(r, newCap);
  76. }
  77. r[i++] = (T)it.next();
  78. }
  79. return (i == r.length) ? r : Arrays.copyOf(r, i);
  80. }
  81. //TAG 6
  82. private static int hugeCapacity(int minCapacity) {
  83. if (minCapacity < 0) // overflow
  84. throw new OutOfMemoryError
  85. ("Required array size too large");
  86. return (minCapacity > MAX_ARRAY_SIZE) ?
  87. Integer.MAX_VALUE :
  88. MAX_ARRAY_SIZE;
  89. }
  90. //TAG 7
  91. public boolean add(E e) {
  92. throw new UnsupportedOperationException();
  93. }
  94. //TAG 3
  95. public boolean remove(Object o) {
  96. Iterator<E> it = iterator();
  97. if (o==null) {
  98. while (it.hasNext()) {
  99. if (it.next()==null) {
  100. it.remove();
  101. return true;
  102. }
  103. }
  104. } else {
  105. while (it.hasNext()) {
  106. if (o.equals(it.next())) {
  107. it.remove();
  108. return true;
  109. }
  110. }
  111. }
  112. return false;
  113. }
  114. //TAG 3
  115. public boolean containsAll(Collection<?> c) {
  116. for (Object e : c)
  117. if (!contains(e))
  118. return false;
  119. return true;
  120. }
  121. //TAG 3
  122. public boolean addAll(Collection<? extends E> c) {
  123. boolean modified = false;
  124. for (E e : c)
  125. if (add(e))
  126. modified = true;
  127. return modified;
  128. }
  129. //TAG 3
  130. public boolean removeAll(Collection<?> c) {
  131. Objects.requireNonNull(c);
  132. boolean modified = false;
  133. Iterator<?> it = iterator();
  134. while (it.hasNext()) {
  135. if (c.contains(it.next())) {
  136. it.remove();
  137. modified = true;
  138. }
  139. }
  140. return modified;
  141. }
  142. //TAG 3
  143. public boolean retainAll(Collection<?> c) {
  144. Objects.requireNonNull(c);
  145. boolean modified = false;
  146. Iterator<E> it = iterator();
  147. while (it.hasNext()) {
  148. if (!c.contains(it.next())) {
  149. it.remove();
  150. modified = true;
  151. }
  152. }
  153. return modified;
  154. }
  155. //TAG 3
  156. public void clear() {
  157. Iterator<E> it = iterator();
  158. while (it.hasNext()) {
  159. it.next();
  160. it.remove();
  161. }
  162. }
  163. //TAG 3
  164. public String toString() {
  165. Iterator<E> it = iterator();
  166. if (! it.hasNext())
  167. return "[]";
  168. StringBuilder sb = new StringBuilder();
  169. sb.append('[');
  170. for (;;) {
  171. E e = it.next();
  172. sb.append(e == this ? "(this Collection)" : e);
  173. if (! it.hasNext())
  174. return sb.append(']').toString();
  175. sb.append(',').append(' ');
  176. }
  177. }
  178. }

TAG 1
从关键字abstract可以看出这个类是一个抽象类,这个类只是实现了一部分的接口,还遗留了一部分接口需要我们在子类中去实现。

TAG 2

isEmpty()方法通过size()接口是否等于0来判断,而size()接口的实现交给了更为具体的集合类去实现。

TAG 3
contains()remove()containsAll()addAll()removeAll()retainAll()clear()toString()这些方法我们通过阅读源码可以知道,都是通过迭代器来实现的,其中有一些方法使用了增强for循环,但其实编译器会将增强for循环编译为使用迭代器的遍历操作。

TAG 4 :
数组作为一个对象,需要一定的内存存储对象头信息,对象头信息最大占用内存不可超过8 byte。

TAG 5 :
finishToArray(T[] r, Iterator<?> it)方法用于数组扩容,当数组索引指向最后一个元素+1时,对数组进行扩容:即创建一个大小为(cap + cap/2 +1)的数组,然后将原数组的内容复制到新数组中。扩容前需要先判断是否数组长度是否溢出。这里的迭代器是从上层的方法(toArray(T[] t))传过来的,并且这个迭代器已执行了一部分,而不是从头开始迭代的

TAG 6
hugeCapacity(int minCapacity)方法用来判断该容器是否已经超过了该集合类默认的最大值即(Integer.MAX_VALUE -8),一般我们用到这个方法的时候比较少,后面我们会在ArrayList类的学习中,看到ArrayList动态扩容用到了这个方法。

TAG 7
这里的add(E)方法默认抛出了一个异常,为什么这样去定义呢?而不是直接定义为抽象方法?
如果我们想修改一个不可变的集合时,抛出 UnsupportedOperationException 是正常的行为,比如当你用 Collections.unmodifiableXXX() 方法对某个集合进行处理后,再调用这个集合的修改方法(add,remove,set…),都会报这个错。因此 AbstractCollection.add(E) 抛出这个错误是准从标准。
而之所以没有定义为抽象方法,是因为可能有很多地方用不到这个方法,用不到还必须实现,这岂不是让人很困惑么。(PS:参考自拭心

toArray详解

在这个类中,我们需要详细了解的方法是toArray,正如其名,它可以把一个集合转换为数组,可以看到toArray方法分为了两种参数的方法:

  1. /**
  2. * 分配了一个等大空间的数组,然后依次对数组元素进行赋值
  3. */
  4. public Object[] toArray() {
  5. //新建等大的数组
  6. Object[] r = new Object[size()];
  7. Iterator<E> it = iterator();
  8. for (int i = 0; i < r.length; i++) {
  9. //判断是否遍历结束,以防多线程操作的时候集合变得更小
  10. if (! it.hasNext())
  11. return Arrays.copyOf(r, i);
  12. r[i] = it.next();
  13. }
  14. //判断是否遍历未结束,以防多线程操作的时候集合变得更大,进行扩容
  15. return it.hasNext() ? finishToArray(r, it) : r;
  16. }
  17. /**
  18. * 泛型方法的`toArray(T[] a)`方法在处理里,会先判断参数数组的大小,
  19. * 如果空间足够就使用参数作为元素存储,如果不够则新分配一个。
  20. * 在循环中的判断也是一样,如果参数a能够存储则返回a,如果不能再新分配。
  21. */
  22. @SuppressWarnings("unchecked")
  23. public <T> T[] toArray(T[] a) {
  24. int size = size();
  25. //当数组a的长度大于等于a,直接将a赋予给r,否则使用反射API获取一个长度为size的数组
  26. T[] r = a.length >= size ? a :
  27. (T[])java.lang.reflect.Array
  28. .newInstance(a.getClass().getComponentType(), size);
  29. Iterator<E> it = iterator();
  30. for (int i = 0; i < r.length; i++) {
  31. //判断是否遍历结束
  32. if (! it.hasNext()) {
  33. //如果 a == r,将r的每项值赋空,并将a返回
  34. if (a == r) {
  35. r[i] = null;
  36. } else if (a.length < i) {
  37. //如果a的长度小于r,直接调用Arrays.copyOf进行复制获取一个新的数组
  38. return Arrays.copyOf(r, i);
  39. } else {
  40. System.arraycopy(r, 0, a, 0, i);
  41. if (a.length > i) {
  42. a[i] = null;
  43. }
  44. }
  45. return a;
  46. }
  47. //如果遍历结束,将迭代器获取的值赋给r
  48. r[i] = (T)it.next();
  49. }
  50. //判断是否遍历未结束,以防多线程操作的时候集合变得更大,进行扩容
  51. return it.hasNext() ? finishToArray(r, it) : r;
  52. }
  53. /**
  54. * 设定该容器的最大值
  55. */
  56. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  57. /**
  58. * 用于动态扩容
  59. */
  60. @SuppressWarnings("unchecked")
  61. private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
  62. int i = r.length;
  63. while (it.hasNext()) {
  64. int cap = r.length;
  65. if (i == cap) {
  66. int newCap = cap + (cap >> 1) + 1;
  67. if (newCap - MAX_ARRAY_SIZE > 0)
  68. newCap = hugeCapacity(cap + 1);
  69. r = Arrays.copyOf(r, newCap);
  70. }
  71. r[i++] = (T)it.next();
  72. }
  73. return (i == r.length) ? r : Arrays.copyOf(r, i);
  74. }
  75. private static int hugeCapacity(int minCapacity) {
  76. if (minCapacity < 0) // overflow
  77. throw new OutOfMemoryError
  78. ("Required array size too large");
  79. return (minCapacity > MAX_ARRAY_SIZE) ?
  80. Integer.MAX_VALUE :
  81. MAX_ARRAY_SIZE;
  82. }

为了帮助了解,我把Arrays.copyOf(r.i)的源码也贴出来:

//参数original代表你传入的需要复制的泛型数组,newLength复制得到数组的大小
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

我们可以观察到其中调用了System.arraycopy方法,为了保持刨根问底的态度,我们又去翻看了这个方法的源码:

 //src数组里从索引为srcPos的元素开始, 复制到数组dest里的索引为destPos的位置, 复制的元素个数为length个. 
 public static native void arraycopy(Object src, int srcPos, Object dest, int destPos,int length);

可以看到这个方式是由关键字native修饰的方法,那么native修饰的方法有什么含义呢?
native关键字说明其修饰的方法是一个原生态方法,方法对应的实现不是在当前文件,而是在用其他语言(如C和C++)实现的文件中。Java语言本身不能对操作系统底层进行访问和操作,但是可以通过JNI接口调用其他语言来实现对底层的访问。

JNI是Java本机接口(Java Native Interface),是一个本机编程接口,它是Java软件开发工具箱(java Software Development Kit,SDK)的一部分。JNI允许Java代码使用以其他语言编写的代码和代码库。Invocation API(JNI的一部分)可以用来将Java虚拟机(JVM)嵌入到本机应用程序中,从而允许程序员从本机代码内部调用Java代码。

然后我们来分析toArray()中需要注意的点,通过原源码中的英文注解,toArray得到的数组跟原collection没有任何关系,我们可以对数组的每个引用值做修改,而不会影响到原collection.这个看起来好像是多余说明的,但是考虑到ArrayList其实就是基于数组实现的,那这个限制保证了即使是将ArrayList转化为数组,那也应该是分配一个新数组,而不是返回原来的数组。

如果我们在单线程操作的情况下,collection集合大小不变,正常应该是执行到 return it.hasNext() ? finishToArray(r, it) : r;这条语句结束,但考虑到在复制的过程中,collection的集合可能会有变化,可能是变大也可能是变小,所以方法增加了对这种情况的处理,这就是为什么每次循环都要判断是collection是否遍历完,以及最后再判断collection是否变得更长,如果是的话,还需要重新再为array分配空间。

通常情况下,我们不会执行到hugeCapacity,但作为一个框架来说,这体现了设计时的严谨。

下节预告

下节课,我们会刨根问底的去了解List的使用。


公众号

扫码或微信搜索 Vi的技术博客,关注公众号,不定期送书活动各种福利~

Java基础系列(四十):集合之AbstractCollection - 图2