1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 import java.util.function.Consumer; 6 import java.util.function.Predicate; 7 import java.u... ...
1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 import java.util.function.Consumer; 6 import java.util.function.Predicate; 7 import java.util.function.UnaryOperator; 8 9 10 /** 11 * 概述: 12 * List介面可調整大小的數組實現。實現所有可選的List操作,並允許所有元素,包括null,元素可重覆。 13 * 除了列表介面外,該類提供了一種方法來操作該數組的大小來存儲該列表中的數組的大小。 14 * 時間複雜度: 15 * 方法size、isEmpty、get、set、iterator和listIterator的調用是常數時間的。 16 * 添加刪除的時間複雜度為O(N)。其他所有操作也都是線性時間複雜度。 17 * 容量: 18 * 每個ArrayList都有容量,容量大小至少為List元素的長度,預設初始化為10。 19 * 容量可以自動增長。 20 * 如果提前知道數組元素較多,可以在添加元素前通過調用ensureCapacity()方法提前增加容量以減小後期容量自動增長的開銷。 21 * 也可以通過帶初始容量的構造器初始化這個容量。 22 * 線程不安全: 23 * ArrayList不是線程安全的。 24 * 如果需要應用到多線程中,需要在外部做同步 25 * modCount: 26 * 定義在AbstractList中:protected transient int modCount = 0; 27 * 已從結構上修改此列表的次數。從結構上修改是指更改列表的大小,或者打亂列表,從而使正在進行的迭代產生錯誤的結果。 28 * 此欄位由iterator和listiterator方法返回的迭代器和列表迭代器實現使用。 29 * 如果意外更改了此欄位中的值,則迭代器(或列表迭代器)將拋出concurrentmodificationexception來響應next、remove、previous、set或add操作。 30 * 在迭代期間面臨併發修改時,它提供了快速失敗 行為,而不是非確定性行為。 31 * 子類是否使用此欄位是可選的。 32 * 如果子類希望提供快速失敗迭代器(和列表迭代器),則它只需在其 add(int,e)和remove(int)方法(以及它所重寫的、導致列表結構上修改的任何其他方法)中增加此欄位。 33 * 對add(int, e)或remove(int)的單個調用向此欄位添加的數量不得超過 1,否則迭代器(和列表迭代器)將拋出虛假的 concurrentmodificationexceptions。 34 * 如果某個實現不希望提供快速失敗迭代器,則可以忽略此欄位。 35 * transient: 36 * 預設情況下,對象的所有成員變數都將被持久化.在某些情況下,如果你想避免持久化對象的一些成員變數,你可以使用transient關鍵字來標記他們,transient也是java中的保留字(JDK 1.8) 37 */ 38 39 public class ArrayList<E> extends AbstractList<E> 40 implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 41 private static final long serialVersionUID = 8683452581122892189L; 42 43 /** 44 * 預設容量 45 */ 46 private static final int DEFAULT_CAPACITY = 10; 47 48 /** 49 * 空的對象數組 50 */ 51 private static final Object[] EMPTY_ELEMENTDATA = {}; 52 53 /** 54 * 預設的空數組 55 * 無參構造函數創建的數組 56 */ 57 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 58 59 /** 60 * 存放數據的數組的緩存變數,不可序列化 61 */ 62 transient Object[] elementData; 63 64 /** 65 * 元素數量 66 * 67 * @serial 68 */ 69 private int size; 70 71 /** 72 * 帶有容量initialCapacity的構造方法 73 * 74 * @param 初始容量列表的初始容量 75 * @throws IllegalArgumentException 如果指定容量為負 76 */ 77 public ArrayList(int initialCapacity) { 78 // 如果初始化時ArrayList大小大於0 79 if (initialCapacity > 0) { 80 // new一個該大小的object數組賦給elementData 81 this.elementData = new Object[initialCapacity]; 82 } else if (initialCapacity == 0) {// 如果大小為0 83 // 將空數組賦給elementData 84 this.elementData = EMPTY_ELEMENTDATA; 85 } else {// 小於0 86 // 則拋出IllegalArgumentException異常 87 throw new IllegalArgumentException("Illegal Capacity: " + 88 initialCapacity); 89 } 90 } 91 92 /** 93 * 不帶參數的構造方法 94 */ 95 public ArrayList() { 96 // 直接將空數組賦給elementData 97 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 98 } 99 100 /** 101 * 帶參數Collection的構造方法 102 * 103 * @param c 其元素將被放入此列表中的集合 104 * @throws NullPointerException 如果指定的集合是空的 105 */ 106 public ArrayList(Collection<? extends E> c) { 107 elementData = c.toArray(); 108 if ((size = elementData.length) != 0) { 109 // c.toarray可能(錯誤地)不返回對象[](見JAVA BUG編號6260652) 110 if (elementData.getClass() != Object[].class) 111 elementData = Arrays.copyOf(elementData, size, Object[].class); 112 } else { 113 // 使用空數組 114 this.elementData = EMPTY_ELEMENTDATA; 115 } 116 } 117 118 /** 119 * 因為容量常常會大於實際元素的數量。記憶體緊張時,可以調用該方法刪除預留的位置,調整容量為元素實際數量。 120 * 如果確定不會再有元素添加進來時也可以調用該方法來節約空間 121 */ 122 public void trimToSize() { 123 modCount++; 124 // 如果size小於length 125 if (size < elementData.length) { 126 // 重新將elementData設置大小為size 127 elementData = (size == 0) 128 ? EMPTY_ELEMENTDATA 129 : Arrays.copyOf(elementData, size); 130 } 131 } 132 133 /** 134 * 使用指定參數設置數組容量 135 * 136 * @param minCapacity 所需的最小容量 137 */ 138 public void ensureCapacity(int minCapacity) { 139 //如果數組為空,容量預取0,否則去預設值(10) 140 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 141 // any size if not default element table 142 ? 0 143 // larger than default for default empty table. It's already 144 // supposed to be at default size. 145 : DEFAULT_CAPACITY; 146 //若參數大於預設的容量,在使用該參數進一步設置數組容量 147 if (minCapacity > minExpand) { 148 ensureExplicitCapacity(minCapacity); 149 } 150 } 151 152 private static int calculateCapacity(Object[] elementData, int minCapacity) { 153 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 154 return Math.max(DEFAULT_CAPACITY, minCapacity); 155 } 156 return minCapacity; 157 } 158 159 /** 160 * 得到最小擴容量 161 * 162 * @param minCapacity 163 */ 164 private void ensureCapacityInternal(int minCapacity) { 165 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 166 } 167 168 /** 169 * 判斷是否需要擴容 170 * 171 * @param minCapacity 172 */ 173 private void ensureExplicitCapacity(int minCapacity) { 174 modCount++; 175 176 // 如果最小需要空間比elementData的記憶體空間要大,則需要擴容 177 if (minCapacity - elementData.length > 0) 178 grow(minCapacity); 179 } 180 181 /** 182 * 數組的最大容量,可能會導致記憶體溢出(VM記憶體限制) 183 */ 184 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 185 186 /** 187 * 擴容,以確保它可以至少持有由參數指定的元素的數目 188 * 189 * @param minCapacity 所需的最小容量 190 */ 191 private void grow(int minCapacity) { 192 // 獲取到ArrayList中elementData數組的記憶體空間長度 193 int oldCapacity = elementData.length; 194 // 擴容至原來的1.5倍 195 int newCapacity = oldCapacity + (oldCapacity >> 1); 196 // 再判斷一下新數組的容量夠不夠,夠了就直接使用這個長度創建新數組, 197 // 不夠就將數組長度設置為需要的長度 198 if (newCapacity - minCapacity < 0) 199 newCapacity = minCapacity; 200 //若預設值大於預設的最大值檢查是否溢出 201 if (newCapacity - MAX_ARRAY_SIZE > 0) 202 newCapacity = hugeCapacity(minCapacity); 203 // 調用Arrays.copyOf方法將elementData數組指向新的記憶體空間時newCapacity的連續空間 204 // 並將elementData的數據複製到新的記憶體空間 205 elementData = Arrays.copyOf(elementData, newCapacity); 206 } 207 208 /** 209 * 檢查是否溢出,若沒有溢出,返回最大整數值(java中的int為4位元組,所以最大為0x7fffffff)或預設最大值 210 * 211 * @param minCapacity 212 * @return 213 */ 214 private static int hugeCapacity(int minCapacity) { 215 if (minCapacity < 0) //溢出 216 throw new OutOfMemoryError(); 217 return (minCapacity > MAX_ARRAY_SIZE) ? 218 Integer.MAX_VALUE : 219 MAX_ARRAY_SIZE; 220 } 221 222 /** 223 * 返回ArrayList的大小 224 * 225 * @return ArrayList中的元素數量 226 */ 227 public int size() { 228 return size; 229 } 230 231 /** 232 * 返回是否為空 233 * 234 * @return true 如果ArrayList中無元素 235 */ 236 public boolean isEmpty() { 237 return size == 0; 238 } 239 240 /** 241 * 是否包含一個數 返回bool 242 * 243 * @param o 檢測o是否為ArrayList中元素 244 * @return true 如果ArrayList中包含o元素 245 */ 246 public boolean contains(Object o) { 247 return indexOf(o) >= 0; 248 } 249 250 251 /** 252 * 返回一個值在數組首次出現的位置,會根據是否為null使用不同方式判斷。不存在就返回-1。時間複雜度為O(N) 253 * 254 * @param o 255 * @return 256 */ 257 public int indexOf(Object o) { 258 if (o == null) { 259 for (int i = 0; i < size; i++) 260 if (elementData[i] == null) 261 return i; 262 } else { 263 for (int i = 0; i < size; i++) 264 if (o.equals(elementData[i])) 265 return i; 266 } 267 return -1; 268 } 269 270 /** 271 * 返回一個值在數組最後一次出現的位置,會根據是否為null使用不同方式判斷。不存在就返回-1。時間複雜度為O(N) 272 * 273 * @param o 274 * @return 275 */ 276 public int lastIndexOf(Object o) { 277 if (o == null) { 278 for (int i = size - 1; i >= 0; i--) 279 if (elementData[i] == null) 280 return i; 281 } else { 282 for (int i = size - 1; i >= 0; i--) 283 if (o.equals(elementData[i])) 284 return i; 285 } 286 return -1; 287 } 288 289 /** 290 * 返回副本,元素本身沒有被覆制,複製過程數組發生改變會拋出異常 291 * 292 * @return v ArrayList副本 293 */ 294 public Object clone() { 295 try { 296 // 調用父類(翻看源碼可見是Object類)的clone方法得到一個ArrayList副本 297 ArrayList<?> v = (ArrayList<?>) super.clone(); 298 // 調用Arrays類的copyOf,將ArrayList的elementData數組賦值給副本的elementData數組 299 v.elementData = Arrays.copyOf(elementData, size); 300 v.modCount = 0; 301 // 返回副本v 302 return v; 303 } catch (CloneNotSupportedException e) { 304 // this shouldn't happen, since we are Cloneable 305 throw new InternalError(e); 306 } 307 } 308 309 /** 310 * 轉換為Object數組,使用Arrays.copyOf()方法 311 * 312 * @return 一個數組包含所有列表中的元素, 且順序正確 313 */ 314 public Object[] toArray() { 315 return Arrays.copyOf(elementData, size); 316 } 317 318 /** 319 * 將ArrayList裡面的元素賦值到一個數組中去 320 * 如果a的長度小於ArrayList的長度,直接調用Arrays類的copyOf,返回一個比a數組長度要大的新數組,裡面元素就是ArrayList裡面的元素; 321 * 如果a的長度比ArrayList的長度大,那麼就調用System.arraycopy,將ArrayList的elementData數組賦值到a數組,然後把a數組的size位置賦值為空。 322 * 323 * @param a 如果它的長度大的話,列表元素將存儲在這個數組中; 否則,將為此分配一個相同運行時類型的新數組。 324 * @return 一個包含ArrayList元素的數組 325 * @throws ArrayStoreException 將與數組類型不相容的值賦值給數組元素時拋出的異常 326 * @throws NullPointerException 數組為空 327 */ 328 @SuppressWarnings("unchecked") 329 public <T> T[] toArray(T[] a) { 330 if (a.length < size) 331 // 創建一個新的a的運行時類型數組,內容不變 332 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 333 System.arraycopy(elementData, 0, a, 0, size); 334 if (a.length > size) 335 a[size] = null; 336 return a; 337 } 338 339 340 /** 341 * 返回指定位置的值,因為是數組,所以速度特別快 342 * 343 * @param index 344 * @return 345 */ 346 @SuppressWarnings("unchecked") 347 E elementData(int index) { 348 return (E) elementData[index]; 349 } 350 351 /** 352 * 返回指定位置的值,但是會先檢查這個位置數否超出數組長度 353 * 354 * @param index 要返回的元素的索引 355 * @return ArrayList中指定位置的元素 356 * @throws IndexOutOfBoundsException {@inheritDoc} 357 */ 358 public E get(int index) { 359 // 檢查是否越界 360 rangeCheck(index); 361 // 返回ArrayList的elementData數組index位置的元素 362 return elementData(index); 363 } 364 365 /** 366 * 設置指定位置為一個新值,並返回之前的值,會檢查這個位置是否超出數組長度 367 * 368 * @param index 要替換的元素的索引 369 * @param element 要存儲在指定位置的元素 370 * @return 之前在指定位置的元素 371 * @throws IndexOutOfBoundsException {@inheritDoc} 372 */ 373 public E set(int index, E element) { 374 // 檢查是否越界 375 rangeCheck(index); 376 // 調用elementData(index)獲取到當前位置的值 377 E oldValue = elementData(index); 378 // 將element賦值到ArrayList的elementData數組的第index位置 379 elementData[index] = element; 380 return oldValue; 381 } 382 383 /** 384 * 添加一個值,首先會確保容量 385 * 386 * @param e 要添加到此列表中的元素 387 * @return <tt>true</tt> (as specified by {@link Collection#add}) 388 */ 389 public boolean add(E e) { 390 // 擴容 391 ensureCapacityInternal(size + 1); // Increments modCount!! 392 // 將e賦值給elementData的size+1的位置 393 elementData[size++] = e; 394 return true; 395 } 396 397 /** 398 * 在ArrayList的index位置,添加元素element,會檢查添加的位置和容量 399 * 400 * @param index 指定元素將被插入的索引 401 * @param element 要插入的元素 402 * @throws IndexOutOfBoundsException {@inheritDoc} 403 */ 404 public void add(int index, E element) { 405 // 判斷index是否越界 406 rangeCheckForAdd(index); 407 // 擴容 408 ensureCapacityInternal(size + 1); // Increments modCount!! 409 //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 410 //src:源數組; srcPos:源數組要複製的起始位置; dest:目的數組; destPos:目的數組放置的起始位置; length:複製的長度 411 // 將elementData從index位置開始,複製到elementData的index+1開始的連續空間 412 System.arraycopy(elementData, index, elementData, index + 1, 413 size - index); 414 // 在elementData的index位置賦值element 415 elementData[index] = element; 416 // ArrayList的大小加一 417 size++; 418 } 419 420 /** 421 * 在ArrayList的移除index位置的元素,會檢查添加的位置,返回之前的值 422 * 423 * @param index 要刪除的元素的索引 424 * @return 從ArrayList中刪除的元素 425 * @throws IndexOutOfBoundsException {@inheritDoc} 426 */ 427 public E remove(int index) { 428 // 判斷是否越界 429 rangeCheck(index); 430 431 modCount++; 432 // 讀取舊值 433 E oldValue = elementData(index); 434 // 獲取index位置開始到最後一個位置的個數 435 int numMoved = size - index - 1; 436 if (numMoved > 0) 437 // 將elementData數組index+1位置開始拷貝到elementData從index開始的空間 438 System.arraycopy(elementData, index + 1, elementData, index, 439 numMoved); 440 // 使size-1 ,設置elementData的size位置為空,讓GC來清理記憶體空間 441 elementData[--size] = null; //便於垃圾回收器回收 442 443 return oldValue; 444 } 445 446 /** 447 * 在ArrayList的移除對象為O的元素,跟indexOf方法思想基本一致 448 * 449 * @param o 要從該列表中刪除的元素(如果存在) 450 * @return true 如果這個列表包含指定的元素 451 */ 452 public boolean remove(Object o) { 453 if (o == null) { 454 for (int index = 0; index < size; index++) 455 if (elementData[index] == null) { 456 fastRemove(index); 457 return true; 458 } 459 } else { 460 for (int index = 0; index < size; index++) 461 if (o.equals(elementData[index])) { 462 fastRemove(index); 463 return true; 464 } 465 } 466 return false; 467 } 468 469 470 /** 471 * 快速刪除指定位置的值,之所以叫快速,應該是不需要檢查和返回值,因為只內部使用 472 * 473 * @param index 474 */ 475 private void fastRemove(int index) { 476 modCount++; 477 int numMoved = size - index - 1; 478 if (numMoved > 0) 479 System.arraycopy(elementData, index + 1, elementData, index, 480 numMoved); 481 // 使size-1 ,設置elementData的size位置為空,讓GC來清理記憶體空間 482 elementData[--size] = null; //