Java集合源代码剖析（一）【集合框架概述、ArrayList、LinkedList、Vector】

2022-12-19 15:48:07

Java集合框架概述

Java集合工具包位于Java.util包下。包括了非常多经常使用的数据结构，如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致能够分为例如以下五个部分：List列表、Set集合、Map映射、迭代器（Iterator、Enumeration）、工具类（Arrays、Collections）。

Java集合类的总体框架例如以下：

Java集合源代码剖析（一）【集合框架概述、ArrayList、LinkedList、Vector】

从上图中能够看出，集合类主要分为两大类：Collection和Map。

Collection是List、Set等集合高度抽象出来的接口，它包括了这些集合的基本操作。它主要又分为两大部分：List和Set。

List接口通常表示一个列表（数组、队列、链表、栈等），当中的元素能够反复。经常使用实现类为ArrayList和LinkedList，另外还有不经常使用的Vector。另外，LinkedList还是实现了Queue接口。因此也能够作为队列使用。

Set接口通常表示一个集合。当中的元素不同意反复（通过hashcode和equals函数保证），经常使用实现类有HashSet和TreeSet，HashSet是通过Map中的HashMap实现的。而TreeSet是通过Map中的TreeMap实现的。

另外。TreeSet还实现了SortedSet接口，因此是有序的集合（集合中的元素要实现Comparable接口。并覆写Compartor函数才行）。

我们看到，抽象类AbstractCollection、AbstractList和AbstractSet分别实现了Collection、List和Set接口，这就是在Java集合框架中用的非常多的适配器设计模式。用这些抽象类去实现接口，在抽象类中实现接口中的若干或所有方法，这样以下的一些类仅仅需直接继承该抽象类。并实现自己须要的方法就可以。而不用实现接口中的所有抽象方法。

Map是一个映射接口。当中的每一个元素都是一个key-value键值对，相同抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数，TreeMap、HashMap、WeakHashMap等实现类都通过继承AbstractMap来实现，另外，不经常使用的HashTable直接实现了Map接口，它和Vector都是JDK1.0就引入的集合类。

Iterator是遍历集合的迭代器（不能遍历Map，仅仅用来遍历Collection）。Collection的实现类都实现了iterator()函数，它返回一个Iterator对象。用来遍历集合，ListIterator则专门用来遍历List。而Enumeration则是JDK1.0时引入的，作用与Iterator相同，但它的功能比Iterator要少，它仅仅能再Hashtable、Vector和Stack中使用。

Arrays和Collections是用来操作数组、集合的两个工具类。比如在ArrayList和Vector中大量调用了Arrays.Copyof()方法，而Collections中有非常多静态方法能够返回各集合类的synchronized版本号，即线程安全的版本号，当然了，假设要用线程安全的结合类，首选Concurrent并发包下的相应的集合类。

ArrayList源代码剖析


ArrayList简单介绍

ArrayList是基于数组实现的。是一个动态数组。其容量能自己主动增长，相似于C语言中的动态申请内存，动态增长内存。

ArrayList不是线程安全的，仅仅能用在单线程环境下，多线程环境下能够考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也能够使用concurrent并发包下的CopyOnWriteArrayList类。

ArrayList实现了Serializable接口，因此它支持序列化。能够通过序列化传输，实现了RandomAccess接口。支持高速随机訪问。实际上就是通过下标序号进行高速訪问，实现了Cloneable接口，能被克隆。

ArrayList源代码剖析

ArrayList的源代码例如以下（加入了比較具体的凝视）：

[java] view plaincopyJava集合源代码剖析（一）【集合框架概述、ArrayList、LinkedList、Vector】Java集合源代码剖析（一）【集合框架概述、ArrayList、LinkedList、Vector】
  1. package java.util;
  2. public class ArrayList<E> extends AbstractList<E>
  3. implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  4. {
  5. // 序列版本号号
  6. private static final long serialVersionUID = 8683452581122892189L;
  7. // ArrayList基于该数组实现，用该数组保存数据
  8. private transient Object[] elementData;
  9. // ArrayList中实际数据的数量
  10. private int size;
  11. // ArrayList带容量大小的构造函数。
  12. public ArrayList(int initialCapacity) {
  13. super();
  14. if (initialCapacity < 0)
  15. throw new IllegalArgumentException("Illegal Capacity: "+
  16. initialCapacity);
  17. // 新建一个数组
  18. this.elementData = new Object[initialCapacity];
  19. }
  20. // ArrayList无參构造函数。默认容量是10。
  21. public ArrayList() {
  22. this(10);
  23. }
  24. // 创建一个包括collection的ArrayList
  25. public ArrayList(Collection<? extends E> c) {
  26. elementData = c.toArray();
  27. size = elementData.length;
  28. if (elementData.getClass() != Object[].class)
  29. elementData = Arrays.copyOf(elementData, size, Object[].class);
  30. }
  31. // 将当前容量值设为实际元素个数
  32. public void trimToSize() {
  33. modCount++;
  34. int oldCapacity = elementData.length;
  35. if (size < oldCapacity) {
  36. elementData = Arrays.copyOf(elementData, size);
  37. }
  38. }
  39. // 确定ArrarList的容量。
  40. // 若ArrayList的容量不足以容纳当前的所有元素，设置 新的容量=“(原始容量x3)/2 + 1”
  41. public void ensureCapacity(int minCapacity) {
  42. // 将“改动统计数”+1。该变量主要是用来实现fail-fast机制的
  43. modCount++;
  44. int oldCapacity = elementData.length;
  45. // 若当前容量不足以容纳当前的元素个数。设置 新的容量=“(原始容量x3)/2 + 1”
  46. if (minCapacity > oldCapacity) {
  47. Object oldData[] = elementData;
  48. int newCapacity = (oldCapacity * 3)/2 + 1;
  49. //假设还不够，则直接将minCapacity设置为当前容量
  50. if (newCapacity < minCapacity)
  51. newCapacity = minCapacity;
  52. elementData = Arrays.copyOf(elementData, newCapacity);
  53. }
  54. }
  55. // 加入元素e
  56. public boolean add(E e) {
  57. // 确定ArrayList的容量大小
  58. ensureCapacity(size + 1);  // Increments modCount!!
  59. // 加入e到ArrayList中
  60. elementData[size++] = e;
  61. return true;
  62. }
  63. // 返回ArrayList的实际大小
  64. public int size() {
  65. return size;
  66. }
  67. // ArrayList是否包括Object(o)
  68. public boolean contains(Object o) {
  69. return indexOf(o) >= 0;
  70. }
  71. //返回ArrayList是否为空
  72. public boolean isEmpty() {
  73. return size == 0;
  74. }
  75. // 正向查找。返回元素的索引值
  76. public int indexOf(Object o) {
  77. if (o == null) {
  78. for (int i = 0; i < size; i++)
  79. if (elementData[i]==null)
  80. return i;
  81. } else {
  82. for (int i = 0; i < size; i++)
  83. if (o.equals(elementData[i]))
  84. return i;
  85. }
  86. return -1;
  87. }
  88. // 反向查找。返回元素的索引值
  89. public int lastIndexOf(Object o) {
  90. if (o == null) {
  91. for (int i = size-1; i >= 0; i--)
  92. if (elementData[i]==null)
  93. return i;
  94. } else {
  95. for (int i = size-1; i >= 0; i--)
  96. if (o.equals(elementData[i]))
  97. return i;
  98. }
  99. return -1;
  100. }
  101. // 反向查找(从数组末尾向開始查找)。返回元素(o)的索引值
  102. public int lastIndexOf(Object o) {
  103. if (o == null) {
  104. for (int i = size-1; i >= 0; i--)
  105. if (elementData[i]==null)
  106. return i;
  107. } else {
  108. for (int i = size-1; i >= 0; i--)
  109. if (o.equals(elementData[i]))
  110. return i;
  111. }
  112. return -1;
  113. }
  114. // 返回ArrayList的Object数组
  115. public Object[] toArray() {
  116. return Arrays.copyOf(elementData, size);
  117. }
  118. // 返回ArrayList元素组成的数组
  119. public <T> T[] toArray(T[] a) {
  120. // 若数组a的大小 < ArrayList的元素个数；
  121. // 则新建一个T[]数组。数组大小是“ArrayList的元素个数”，并将“ArrayList”所有复制到新数组中
  122. if (a.length < size)
  123. return (T[]) Arrays.copyOf(elementData, size, a.getClass());
  124. // 若数组a的大小 >= ArrayList的元素个数；
  125. // 则将ArrayList的所有元素都复制到数组a中。
  126. System.arraycopy(elementData, 0, a, 0, size);
  127. if (a.length > size)
  128. a[size] = null;
  129. return a;
  130. }
  131. // 获取index位置的元素值
  132. public E get(int index) {
  133. RangeCheck(index);
  134. return (E) elementData[index];
  135. }
  136. // 设置index位置的值为element
  137. public E set(int index, E element) {
  138. RangeCheck(index);
  139. E oldValue = (E) elementData[index];
  140. elementData[index] = element;
  141. return oldValue;
  142. }
  143. // 将e加入到ArrayList中
  144. public boolean add(E e) {
  145. ensureCapacity(size + 1);  // Increments modCount!!
  146. elementData[size++] = e;
  147. return true;
  148. }
  149. // 将e加入到ArrayList的指定位置
  150. public void add(int index, E element) {
  151. if (index > size || index < 0)
  152. throw new IndexOutOfBoundsException(
  153. "Index: "+index+", Size: "+size);
  154. ensureCapacity(size+1);  // Increments modCount!!
  155. System.arraycopy(elementData, index, elementData, index + 1,
  156. size - index);
  157. elementData[index] = element;
  158. size++;
  159. }
  160. // 删除ArrayList指定位置的元素
  161. public E remove(int index) {
  162. RangeCheck(index);
  163. modCount++;
  164. E oldValue = (E) elementData[index];
  165. int numMoved = size - index - 1;
  166. if (numMoved > 0)
  167. System.arraycopy(elementData, index+1, elementData, index,
  168. numMoved);
  169. elementData[--size] = null; // Let gc do its work
  170. return oldValue;
  171. }
  172. // 删除ArrayList的指定元素
  173. public boolean remove(Object o) {
  174. if (o == null) {
  175. for (int index = 0; index < size; index++)
  176. if (elementData[index] == null) {
  177. fastRemove(index);
  178. return true;
  179. }
  180. } else {
  181. for (int index = 0; index < size; index++)
  182. if (o.equals(elementData[index])) {
  183. fastRemove(index);
  184. return true;
  185. }
  186. }
  187. return false;
  188. }
  189. // 高速删除第index个元素
  190. private void fastRemove(int index) {
  191. modCount++;
  192. int numMoved = size - index - 1;
  193. // 从"index+1"開始。用后面的元素替换前面的元素。
  194. if (numMoved > 0)
  195. System.arraycopy(elementData, index+1, elementData, index,
  196. numMoved);
  197. // 将最后一个元素设为null
  198. elementData[--size] = null; // Let gc do its work
  199. }
  200. // 删除元素
  201. public boolean remove(Object o) {
  202. if (o == null) {
  203. for (int index = 0; index < size; index++)
  204. if (elementData[index] == null) {
  205. fastRemove(index);
  206. return true;
  207. }
  208. } else {
  209. // 便利ArrayList，找到“元素o”。则删除，并返回true。
  210. for (int index = 0; index < size; index++)
  211. if (o.equals(elementData[index])) {
  212. fastRemove(index);
  213. return true;
  214. }
  215. }
  216. return false;
  217. }
  218. // 清空ArrayList，将所有的元素设为null
  219. public void clear() {
  220. modCount++;
  221. for (int i = 0; i < size; i++)
  222. elementData[i] = null;
  223. size = 0;
  224. }
  225. // 将集合c追加到ArrayList中
  226. public boolean addAll(Collection<?

    extends E> c) {

  227. Object[] a = c.toArray();
  228. int numNew = a.length;
  229. ensureCapacity(size + numNew);  // Increments modCount
  230. System.arraycopy(a, 0, elementData, size, numNew);
  231. size += numNew;
  232. return numNew != 0;
  233. }
  234. // 从index位置開始，将集合c加入到ArrayList
  235. public boolean addAll(int index, Collection<?

    extends E> c) {

  236. if (index > size || index < 0)
  237. throw new IndexOutOfBoundsException(
  238. "Index: " + index + ", Size: " + size);
  239. Object[] a = c.toArray();
  240. int numNew = a.length;
  241. ensureCapacity(size + numNew);  // Increments modCount
  242. int numMoved = size - index;
  243. if (numMoved > 0)
  244. System.arraycopy(elementData, index, elementData, index + numNew,
  245. numMoved);
  246. System.arraycopy(a, 0, elementData, index, numNew);
  247. size += numNew;
  248. return numNew != 0;
  249. }
  250. // 删除fromIndex到toIndex之间的所有元素。
  251. protected void removeRange(int fromIndex, int toIndex) {
  252. modCount++;
  253. int numMoved = size - toIndex;
  254. System.arraycopy(elementData, toIndex, elementData, fromIndex,
  255. numMoved);
  256. // Let gc do its work
  257. int newSize = size - (toIndex-fromIndex);
  258. while (size != newSize)
  259. elementData[--size] = null;
  260. }
  261. private void RangeCheck(int index) {
  262. if (index >= size)
  263. throw new IndexOutOfBoundsException(
  264. "Index: "+index+", Size: "+size);
  265. }
  266. // 克隆函数
  267. public Object clone() {
  268. try {
  269. ArrayList<E> v = (ArrayList<E>) super.clone();
  270. // 将当前ArrayList的所有元素复制到v中
  271. v.elementData = Arrays.copyOf(elementData, size);
  272. v.modCount = 0;
  273. return v;
  274. } catch (CloneNotSupportedException e) {
  275. // this shouldn't happen, since we are Cloneable
  276. throw new InternalError();
  277. }
  278. }
  279. // java.io.Serializable的写入函数
  280. // 将ArrayList的“容量，所有的元素值”都写入到输出流中
  281. private void writeObject(java.io.ObjectOutputStream s)
  282. throws java.io.IOException{
  283. // Write out element count, and any hidden stuff
  284. int expectedModCount = modCount;
  285. s.defaultWriteObject();
  286. // 写入“数组的容量”
  287. s.writeInt(elementData.length);
  288. // 写入“数组的每一个元素”
  289. for (int i=0; i<size; i++)
  290. s.writeObject(elementData[i]);
  291. if (modCount != expectedModCount) {
  292. throw new ConcurrentModificationException();
  293. }
  294. }
  295. // java.io.Serializable的读取函数：依据写入方式读出
  296. // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
  297. private void readObject(java.io.ObjectInputStream s)
  298. throws java.io.IOException, ClassNotFoundException {
  299. // Read in size, and any hidden stuff
  300. s.defaultReadObject();
  301. // 从输入流中读取ArrayList的“容量”
  302. int arrayLength = s.readInt();
  303. Object[] a = elementData = new Object[arrayLength];
  304. // 从输入流中将“所有的元素值”读出
  305. for (int i=0; i<size; i++)
  306. a[i] = s.readObject();
  307. }
  308. }

, copy, 0,

  • Math.min(original.length, newLength));
  • return copy;
  • }

    • ]);

  • return newText;
  • }
    • 上一篇：Java容器解析系列(4) ArrayList Vector Stack 详解


    下一篇：基于Python+Pyqt5应用程序开发