备战-Java 容器

备战-Java 容器

 

　　　　玉阶生白露，夜久侵罗袜。

 

简介：备战-Java 容器

一、概述

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着key-value 键值对（两个对象）的映射表。

Collection

1. Set

• TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

• HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

• LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

2. List

• ArrayList：基于动态数组实现，支持随机访问。

• Vector：和 ArrayList 类似，但它是线程安全的。

• LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

3. Queue

• LinkedList：可以用它来实现双向队列。

• PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

Map

• TreeMap：基于红黑树实现。

• HashMap：基于哈希表实现。

• HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。

• LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。(LRU算法是Least Recently Used的缩写，即最近最少使用)

二、容器中的设计模式

迭代器模式

 Collection 继承了 Iterable 接口，其中的 iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

1 List<String> list = new ArrayList<>();2 list.add("a");3 list.add("b");4 for (String item : list) {5  System.out.println(item);6 }

View Code

适配器模式

java.util.Arrays.asList() 可以把数组类型转换为 List 类型。

1 @SafeVarargs2 public static <T> List<T> asList(T... a)

值得注意的是 asList() 的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组。

1 Integer[] arr = {1, 2, 3};2 List list = Arrays.asList(arr);

也可以使用以下方式调用 asList()：

List list = Arrays.asList(1, 2, 3);

三、源码分析

如果没有特别说明，以下源码分析基于 JDK 1.8。

在 IDEA 中 双击 shift 键调出 Search EveryWhere，查找源码文件，找到之后就可以阅读源码。

ArrayList

1. 概览

因为 ArrayList 是基于数组实现的，所以支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问，其默认数组大小为10

 1 /* 2  * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved. 3  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 4  * 5  * 6  * 7  * 8  * 9  * 10  * 11  * 12  * 13  * 14  * 15  * 16  * 17  * 18  * 19  * 20  * 21  * 22  * 23  * 24 */ 25  26 package java.util; 27  28 import java.util.function.Consumer; 29 import java.util.function.Predicate; 30 import java.util.function.UnaryOperator; 31 import sun.misc.SharedSecrets; 32  33 /** 34  * Resizable-array implementation of the <tt>List</tt> interface. Implements 35  * all optional list operations, and permits all elements, including 36  * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface, 37  * this class provides methods to manipulate the size of the array that is 38  * used internally to store the list. (This class is roughly equivalent to 39  * <tt>Vector</tt>, except that it is unsynchronized.) 40  * 41  * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, 42  * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant 43  * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>, 44  * that is, adding n elements requires O(n) time. All of the other operations 45  * run in linear time (roughly speaking). The constant factor is low compared 46  * to that for the <tt>LinkedList</tt> implementation. 47  * 48  * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is 49  * the size of the array used to store the elements in the list. It is always 50  * at least as large as the list size. As elements are added to an ArrayList, 51  * its capacity grows automatically. The details of the growth policy are not 52  * specified beyond the fact that adding an element has constant amortized 53  * time cost. 54  * 55  * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance 56  * before adding a large number of elements using the <tt>ensureCapacity</tt> 57  * operation. This may reduce the amount of incremental reallocation. 58  * 59  * <p><strong>Note that this implementation is not synchronized.</strong> 60  * If multiple threads access an <tt>ArrayList</tt> instance concurrently, 61  * and at least one of the threads modifies the list structurally, it 62  * <i>must</i> be synchronized externally. (A structural modification is 63  * any operation that adds or deletes one or more elements, or explicitly 64  * resizes the backing array; merely setting the value of an element is not 65  * a structural modification.) This is typically accomplished by 66  * synchronizing on some object that naturally encapsulates the list. 67  * 68  * If no such object exists, the list should be "wrapped" using the 69  * {@link Collections#synchronizedList Collections.synchronizedList} 70  * method. This is best done at creation time, to prevent accidental 71  * unsynchronized access to the list:<pre> 72  * List list = Collections.synchronizedList(new ArrayList(...));</pre> 73  * 74  * <p><a name="fail-fast"> 75  * The iterators returned by this class's {@link #iterator() iterator} and 76  * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a> 77  * if the list is structurally modified at any time after the iterator is 78  * created, in any way except through the iterator's own 79  * {@link ListIterator#remove() remove} or 80  * {@link ListIterator#add(Object) add} methods, the iterator will throw a 81  * {@link ConcurrentModificationException}. Thus, in the face of 82  * concurrent modification, the iterator fails quickly and cleanly, rather 83  * than risking arbitrary, non-deterministic behavior at an undetermined 84  * time in the future. 85  * 86  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 87  * as it is, generally speaking, impossible to make any hard guarantees in the 88  * presence of unsynchronized concurrent modification. Fail-fast iterators 89  * throw {@code ConcurrentModificationException} on a best-effort basis. 90  * Therefore, it would be wrong to write a program that depended on this 91  * exception for its correctness: <i>the fail-fast behavior of iterators 92  * should be used only to detect bugs.</i> 93  * 94  * <p>This class is a member of the 95  * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 96  * Java Collections Framework</a>. 97  * 98  * @author Josh Bloch 99  * @author Neal Gafter 100  * @see  Collection 101  * @see  List 102  * @see  LinkedList 103  * @see  Vector 104  * @since 1.2 105 */ 106  107 public class ArrayList<E> extends AbstractList<E> 108   implements List<E>, RandomAccess, Cloneable, java.io.Serializable 109 { 110  private static final long serialVersionUID = 8683452581122892189L; 111  112  /** 113   * Default initial capacity. 114  */ 115  private static final int DEFAULT_CAPACITY = 10; 116  117  /** 118   * Shared empty array instance used for empty instances. 119  */ 120  private static final Object[] EMPTY_ELEMENTDATA = {}; 121  122  /** 123   * Shared empty array instance used for default sized empty instances. We 124   * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when 125   * first element is added. 126  */ 127  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 128  129  /** 130   * The array buffer into which the elements of the ArrayList are stored. 131   * The capacity of the ArrayList is the length of this array buffer. Any 132   * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 133   * will be expanded to DEFAULT_CAPACITY when the first element is added. 134  */ 135  transient Object[] elementData; // non-private to simplify nested class access 136  137  /** 138   * The size of the ArrayList (the number of elements it contains). 139   * 140   * @serial 141  */ 142  private int size; 143  144  /** 145   * Constructs an empty list with the specified initial capacity. 146   * 147   * @param initialCapacity the initial capacity of the list 148   * @throws IllegalArgumentException if the specified initial capacity 149   *   is negative 150  */ 151  public ArrayList(int initialCapacity) { 152   if (initialCapacity > 0) { 153    this.elementData = new Object[initialCapacity]; 154   } else if (initialCapacity == 0) { 155    this.elementData = EMPTY_ELEMENTDATA; 156   } else { 157    throw new IllegalArgumentException("Illegal Capacity: "+ 158             initialCapacity); 159   } 160  } 161  162  /** 163   * Constructs an empty list with an initial capacity of ten. 164  */ 165  public ArrayList() { 166   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 167  } 168  169  /** 170   * Constructs a list containing the elements of the specified 171   * collection, in the order they are returned by the collection's 172   * iterator. 173   * 174   * @param c the collection whose elements are to be placed into this list 175   * @throws NullPointerException if the specified collection is null 176  */ 177  public ArrayList(Collection<? extends E> c) { 178   elementData = c.toArray(); 179   if ((size = elementData.length) != 0) { 180    // c.toArray might (incorrectly) not return Object[] (see 6260652) 181    if (elementData.getClass() != Object[].class) 182     elementData = Arrays.copyOf(elementData, size, Object[].class); 183   } else { 184    // replace with empty array. 185    this.elementData = EMPTY_ELEMENTDATA; 186   } 187  } 188  189  /** 190   * Trims the capacity of this <tt>ArrayList</tt> instance to be the 191   * list's current size. An application can use this operation to minimize 192   * the storage of an <tt>ArrayList</tt> instance. 193  */ 194  public void trimToSize() { 195   modCount++; 196   if (size < elementData.length) { 197    elementData = (size == 0) 198    ? EMPTY_ELEMENTDATA 199     : Arrays.copyOf(elementData, size); 200   } 201  } 202  203  /** 204   * Increases the capacity of this <tt>ArrayList</tt> instance, if 205   * necessary, to ensure that it can hold at least the number of elements 206   * specified by the minimum capacity argument. 207   * 208   * @param minCapacity the desired minimum capacity 209  */ 210  public void ensureCapacity(int minCapacity) { 211   int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 212    // any size if not default element table 213    ? 0 214    // larger than default for default empty table. It's already 215    // supposed to be at default size. 216    : DEFAULT_CAPACITY; 217  218   if (minCapacity > minExpand) { 219    ensureExplicitCapacity(minCapacity); 220   } 221  } 222  223  private static int calculateCapacity(Object[] elementData, int minCapacity) { 224   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 225    return Math.max(DEFAULT_CAPACITY, minCapacity); 226   } 227   return minCapacity; 228  } 229  230  private void ensureCapacityInternal(int minCapacity) { 231   ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 232  } 233  234  private void ensureExplicitCapacity(int minCapacity) { 235   modCount++; 236  237   // overflow-conscious code 238   if (minCapacity - elementData.length > 0) 239    grow(minCapacity); 240  } 241  242  /** 243   * The maximum size of array to allocate. 244   * Some VMs reserve some header words in an array. 245   * Attempts to allocate larger arrays may result in 246   * OutOfMemoryError: Requested array size exceeds VM limit 247  */ 248  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 249  250  /** 251   * Increases the capacity to ensure that it can hold at least the 252   * number of elements specified by the minimum capacity argument. 253   * 254   * @param minCapacity the desired minimum capacity 255  */ 256  private void grow(int minCapacity) { 257   // overflow-conscious code 258   int oldCapacity = elementData.length; 259   int newCapacity = oldCapacity + (oldCapacity >> 1); 260   if (newCapacity - minCapacity < 0) 261    newCapacity = minCapacity; 262   if (newCapacity - MAX_ARRAY_SIZE > 0) 263    newCapacity = hugeCapacity(minCapacity); 264   // minCapacity is usually close to size, so this is a win: 265   elementData = Arrays.copyOf(elementData, newCapacity); 266  } 267  268  private static int hugeCapacity(int minCapacity) { 269   if (minCapacity < 0) // overflow 270    throw new OutOfMemoryError(); 271   return (minCapacity > MAX_ARRAY_SIZE) ? 272    Integer.MAX_VALUE : 273    MAX_ARRAY_SIZE; 274  } 275  276  /** 277   * Returns the number of elements in this list. 278   * 279   * @return the number of elements in this list 280  */ 281  public int size() { 282   return size; 283  } 284  285  /** 286   * Returns <tt>true</tt> if this list contains no elements. 287   * 288   * @return <tt>true</tt> if this list contains no elements 289  */ 290  public boolean isEmpty() { 291   return size == 0; 292  } 293  294  /** 295   * Returns <tt>true</tt> if this list contains the specified element. 296   * More formally, returns <tt>true</tt> if and only if this list contains 297   * at least one element <tt>e</tt> such that 298   * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>. 299   * 300   * @param o element whose presence in this list is to be tested 301   * @return <tt>true</tt> if this list contains the specified element 302  */ 303  public boolean contains(Object o) { 304   return indexOf(o) >= 0; 305  } 306  307  /** 308   * Returns the index of the first occurrence of the specified element 309   * in this list, or -1 if this list does not contain the element. 310   * More formally, returns the lowest index <tt>i</tt> such that 311   * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>, 312   * or -1 if there is no such index. 313  */ 314  public int indexOf(Object o) { 315   if (o == null) { 316    for (int i = 0; i < size; i++) 317     if (elementData[i]==null) 318      return i; 319   } else { 320    for (int i = 0; i < size; i++) 321     if (o.equals(elementData[i])) 322      return i; 323   } 324   return -1; 325  } 326  327  /** 328   * Returns the index of the last occurrence of the specified element 329   * in this list, or -1 if this list does not contain the element. 330   * More formally, returns the highest index <tt>i</tt> such that 331   * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>, 332   * or -1 if there is no such index. 333  */ 334  public int lastIndexOf(Object o) { 335   if (o == null) { 336    for (int i = size-1; i >= 0; i--) 337     if (elementData[i]==null) 338      return i; 339   } else { 340    for (int i = size-1; i >= 0; i--) 341     if (o.equals(elementData[i])) 342      return i; 343   } 344   return -1; 345  } 346  347  /** 348   * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The 349   * elements themselves are not copied.) 350   * 351   * @return a clone of this <tt>ArrayList</tt> instance 352  */ 353  public Object clone() { 354   try { 355    ArrayList<?> v = (ArrayList<?>) super.clone(); 356    v.elementData = Arrays.copyOf(elementData, size); 357    v.modCount = 0; 358    return v; 359   } catch (CloneNotSupportedException e) { 360    // this shouldn't happen, since we are Cloneable 361    throw new InternalError(e); 362   } 363  } 364  365  /** 366   * Returns an array containing all of the elements in this list 367   * in proper sequence (from first to last element). 368   * 369   * <p>The returned array will be "safe" in that no references to it are 370   * maintained by this list. (In other words, this method must allocate 371   * a new array). The caller is thus free to modify the returned array. 372   * 373   * <p>This method acts as bridge between array-based and collection-based 374   * APIs. 375   * 376   * @return an array containing all of the elements in this list in 377   *   proper sequence 378  */ 379  public Object[] toArray() { 380   return Arrays.copyOf(elementData, size); 381  } 382  383  /** 384   * Returns an array containing all of the elements in this list in proper 385   * sequence (from first to last element); the runtime type of the returned 386   * array is that of the specified array. If the list fits in the 387   * specified array, it is returned therein. Otherwise, a new array is 388   * allocated with the runtime type of the specified array and the size of 389   * this list. 390   * 391   * <p>If the list fits in the specified array with room to spare 392   * (i.e., the array has more elements than the list), the element in 393   * the array immediately following the end of the collection is set to 394   * <tt>null</tt>. (This is useful in determining the length of the 395   * list <i>only</i> if the caller knows that the list does not contain 396   * any null elements.) 397   * 398   * @param a the array into which the elements of the list are to 399   *   be stored, if it is big enough; otherwise, a new array of the 400   *   same runtime type is allocated for this purpose. 401   * @return an array containing the elements of the list 402   * @throws ArrayStoreException if the runtime type of the specified array 403   *   is not a supertype of the runtime type of every element in 404   *   this list 405   * @throws NullPointerException if the specified array is null 406  */ 407  @SuppressWarnings("unchecked") 408  public <T> T[] toArray(T[] a) { 409   if (a.length < size) 410    // Make a new array of a's runtime type, but my contents: 411    return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 412   System.arraycopy(elementData, 0, a, 0, size); 413   if (a.length > size) 414    a[size] = null; 415   return a; 416  } 417  418  // Positional Access Operations 419  420  @SuppressWarnings("unchecked") 421  E elementData(int index) { 422   return (E) elementData[index]; 423  } 424  425  /** 426   * Returns the element at the specified position in this list. 427   * 428   * @param index index of the element to return 429   * @return the element at the specified position in this list 430   * @throws IndexOutOfBoundsException {@inheritDoc} 431  */ 432  public E get(int index) { 433   rangeCheck(index); 434  435   return elementData(index); 436  } 437  438  /** 439   * Replaces the element at the specified position in this list with 440   * the specified element. 441   * 442   * @param index index of the element to replace 443   * @param element element to be stored at the specified position 444   * @return the element previously at the specified position 445   * @throws IndexOutOfBoundsException {@inheritDoc} 446  */ 447  public E set(int index, E element) { 448   rangeCheck(index); 449  450   E oldValue = elementData(index); 451   elementData[index] = element; 452   return oldValue; 453  } 454  455  /** 456   * Appends the specified element to the end of this list. 457   * 458   * @param e element to be appended to this list 459   * @return <tt>true</tt> (as specified by {@link Collection#add}) 460  */ 461  public boolean add(E e) { 462   ensureCapacityInternal(size + 1); // Increments modCount!! 463   elementData[size++] = e; 464   return true; 465  } 466  467  /** 468   * Inserts the specified element at the specified position in this 469   * list. Shifts the element currently at that position (if any) and 470   * any subsequent elements to the right (adds one to their indices). 471   * 472   * @param index index at which the specified element is to be inserted 473   * @param element element to be inserted 474   * @throws IndexOutOfBoundsException {@inheritDoc} 475  */ 476  public void add(int index, E element) { 477   rangeCheckForAdd(index); 478  479   ensureCapacityInternal(size + 1); // Increments modCount!! 480   System.arraycopy(elementData, index, elementData, index + 1, 481       size - index); 482   elementData[index] = element; 483   size++; 484  } 485  486  /** 487   * Removes the element at the specified position in this list. 488   * Shifts any subsequent elements to the left (subtracts one from their 489   * indices). 490   * 491   * @param index the index of the element to be removed 492   * @return the element that was removed from the list 493   * @throws IndexOutOfBoundsException {@inheritDoc} 494  */ 495  public E remove(int index) { 496   rangeCheck(index); 497  498   modCount++; 499   E oldValue = elementData(index); 500  501   int numMoved = size - index - 1; 502   if (numMoved > 0) 503    System.arraycopy(elementData, index+1, elementData, index, 504         numMoved); 505   elementData[--size] = null; // clear to let GC do its work 506  507   return oldValue; 508  } 509  510  /** 511   * Removes the first occurrence of the specified element from this list, 512   * if it is present. If the list does not contain the element, it is 513   * unchanged. More formally, removes the element with the lowest index 514   * <tt>i</tt> such that 515   * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt> 516   * (if such an element exists). Returns <tt>true</tt> if this list 517   * contained the specified element (or equivalently, if this list 518   * changed as a result of the call). 519   * 520   * @param o element to be removed from this list, if present 521   * @return <tt>true</tt> if this list contained the specified element 522  */ 523  public boolean remove(Object o) { 524   if (o == null) { 525    for (int index = 0; index < size; index++) 526     if (elementData[index] == null) { 527      fastRemove(index); 528      return true; 529     } 530   } else { 531    for (int index = 0; index < size; index++) 532     if (o.equals(elementData[index])) { 533      fastRemove(index); 534      return true; 535     } 536   } 537   return false; 538  } 539  540  /* 541   * Private remove method that skips bounds checking and does not 542   * return the value removed. 543  */ 544  private void fastRemove(int index) { 545   modCount++; 546   int numMoved = size - index - 1; 547   if (numMoved > 0) 548    System.arraycopy(elementData, index+1, elementData, index, 549         numMoved); 550   elementData[--size] = null; // clear to let GC do its work 551  } 552  553  /** 554   * Removes all of the elements from this list. The list will 555   * be empty after this call returns. 556  */ 557  public void clear() { 558   modCount++; 559  560   // clear to let GC do its work 561   for (int i = 0; i < size; i++) 562    elementData[i] = null; 563  564   size = 0; 565  } 566  567  /** 568   * Appends all of the elements in the specified collection to the end of 569   * this list, in the order that they are returned by the 570   * specified collection's Iterator. The behavior of this operation is 571   * undefined if the specified collection is modified while the operation 572   * is in progress. (This implies that the behavior of this call is 573   * undefined if the specified collection is this list, and this 574   * list is nonempty.) 575   * 576   * @param c collection containing elements to be added to this list 577   * @return <tt>true</tt> if this list changed as a result of the call 578   * @throws NullPointerException if the specified collection is null 579  */ 580  public boolean addAll(Collection<? extends E> c) { 581   Object[] a = c.toArray(); 582   int numNew = a.length; 583   ensureCapacityInternal(size + numNew); // Increments modCount 584   System.arraycopy(a, 0, elementData, size, numNew); 585   size += numNew; 586   return numNew != 0; 587  } 588  589  /** 590   * Inserts all of the elements in the specified collection into this 591   * list, starting at the specified position. Shifts the element 592   * currently at that position (if any) and any subsequent elements to 593   * the right (increases their indices). The new elements will appear 594   * in the list in the order that they are returned by the 595   * specified collection's iterator. 596   * 597   * @param index index at which to insert the first element from the 598   *    specified collection 599   * @param c collection containing elements to be added to this list 600   * @return <tt>true</tt> if this list changed as a result of the call 601   * @throws IndexOutOfBoundsException {@inheritDoc} 602   * @throws NullPointerException if the specified collection is null 603  */ 604  public boolean addAll(int index, Collection<? extends E> c) { 605   rangeCheckForAdd(index); 606  607   Object[] a = c.toArray(); 608   int numNew = a.length; 609   ensureCapacityInternal(size + numNew); // Increments modCount 610  611   int numMoved = size - index; 612   if (numMoved > 0) 613    System.arraycopy(elementData, index, elementData, index + numNew, 614         numMoved); 615  616   System.arraycopy(a, 0, elementData, index, numNew); 617   size += numNew; 618   return numNew != 0; 619  } 620  621  /** 622   * Removes from this list all of the elements whose index is between 623   * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 624   * Shifts any succeeding elements to the left (reduces their index). 625   * This call shortens the list by {@code (toIndex - fromIndex)} elements. 626   * (If {@code toIndex==fromIndex}, this operation has no effect.) 627   * 628   * @throws IndexOutOfBoundsException if {@code fromIndex} or 629   *   {@code toIndex} is out of range 630   *   ({@code fromIndex < 0 || 631   *   fromIndex >= size() || 632   *   toIndex > size() || 633   *   toIndex < fromIndex}) 634  */ 635  protected void removeRange(int fromIndex, int toIndex) { 636   modCount++; 637   int numMoved = size - toIndex; 638   System.arraycopy(elementData, toIndex, elementData, fromIndex, 639        numMoved); 640  641   // clear to let GC do its work 642   int newSize = size - (toIndex-fromIndex); 643   for (int i = newSize; i < size; i++) { 644    elementData[i] = null; 645   } 646   size = newSize; 647  } 648  649  /** 650   * Checks if the given index is in range. If not, throws an appropriate 651   * runtime exception. This method does *not* check if the index is 652   * negative: It is always used immediately prior to an array access, 653   * which throws an ArrayIndexOutOfBoundsException if index is negative. 654  */ 655  private void rangeCheck(int index) { 656   if (index >= size) 657    throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 658  } 659  660  /** 661   * A version of rangeCheck used by add and addAll. 662  */ 663  private void rangeCheckForAdd(int index) { 664   if (index > size || index < 0) 665    throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 666  } 667  668  /** 669   * Constructs an IndexOutOfBoundsException detail message. 670   * Of the many possible refactorings of the error handling code, 671   * this "outlining" performs best with both server and client VMs. 672  */ 673  private String outOfBoundsMsg(int index) { 674   return "Index: "+index+", Size: "+size; 675  } 676  677  /** 678   * Removes from this list all of its elements that are contained in the 679   * specified collection. 680   * 681   * @param c collection containing elements to be removed from this list 682   * @return {@code true} if this list changed as a result of the call 683   * @throws ClassCastException if the class of an element of this list 684   *   is incompatible with the specified collection 685   * (<a href="Collection.html#optional-restrictions">optional</a>) 686   * @throws NullPointerException if this list contains a null element and the 687   *   specified collection does not permit null elements 688   * (<a href="Collection.html#optional-restrictions">optional</a>), 689   *   or if the specified collection is null 690   * @see Collection#contains(Object) 691  */ 692  public boolean removeAll(Collection<?> c) { 693   Objects.requireNonNull(c); 694   return batchRemove(c, false); 695  } 696  697  /** 698   * Retains only the elements in this list that are contained in the 699   * specified collection. In other words, removes from this list all 700   * of its elements that are not contained in the specified collection. 701   * 702   * @param c collection containing elements to be retained in this list 703   * @return {@code true} if this list changed as a result of the call 704   * @throws ClassCastException if the class of an element of this list 705   *   is incompatible with the specified collection 706   * (<a href="Collection.html#optional-restrictions">optional</a>) 707   * @throws NullPointerException if this list contains a null element and the 708   *   specified collection does not permit null elements 709   * (<a href="Collection.html#optional-restrictions">optional</a>), 710   *   or if the specified collection is null 711   * @see Collection#contains(Object) 712  */ 713  public boolean retainAll(Collection<?> c) { 714   Objects.requireNonNull(c); 715   return batchRemove(c, true); 716  } 717  718  private boolean batchRemove(Collection<?> c, boolean complement) { 719   final Object[] elementData = this.elementData; 720   int r = 0, w = 0; 721   boolean modified = false; 722   try { 723    for (; r < size; r++) 724     if (c.contains(elementData[r]) == complement) 725      elementData[w++] = elementData[r]; 726   } finally { 727    // Preserve behavioral compatibility with AbstractCollection, 728    // even if c.contains() throws. 729    if (r != size) { 730     System.arraycopy(elementData, r, 731          elementData, w, 732         size - r); 733     w += size - r; 734    } 735    if (w != size) { 736     // clear to let GC do its work 737     for (int i = w; i < size; i++) 738      elementData[i] = null; 739     modCount += size - w; 740     size = w; 741     modified = true; 742    } 743   } 744   return modified; 745  } 746  747  /** 748   * Save the state of the <tt>ArrayList</tt> instance to a stream (that 749   * is, serialize it). 750   * 751   * @serialData The length of the array backing the <tt>ArrayList</tt> 752   *    instance is emitted (int), followed by all of its elements 753   *    (each an <tt>Object</tt>) in the proper order. 754  */ 755  private void writeObject(java.io.ObjectOutputStream s) 756   throws java.io.IOException{ 757   // Write out element count, and any hidden stuff 758   int expectedModCount = modCount; 759   s.defaultWriteObject(); 760  761   // Write out size as capacity for behavioural compatibility with clone() 762   s.writeInt(size); 763  764   // Write out all elements in the proper order. 765   for (int i=0; i<size; i++) { 766    s.writeObject(elementData[i]); 767   } 768  769   if (modCount != expectedModCount) { 770    throw new ConcurrentModificationException(); 771   } 772  } 773  774  /** 775   * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, 776   * deserialize it). 777  */ 778  private void readObject(java.io.ObjectInputStream s) 779   throws java.io.IOException, ClassNotFoundException { 780   elementData = EMPTY_ELEMENTDATA; 781  782   // Read in size, and any hidden stuff 783   s.defaultReadObject(); 784  785   // Read in capacity 786   s.readInt(); // ignored 787  788   if (size > 0) { 789    // be like clone(), allocate array based upon size not capacity 790    int capacity = calculateCapacity(elementData, size); 791    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); 792    ensureCapacityInternal(size); 793  794    Object[] a = elementData; 795    // Read in all elements in the proper order. 796    for (int i=0; i<size; i++) { 797     a[i] = s.readObject(); 798    } 799   } 800  } 801  802  /** 803   * Returns a list iterator over the elements in this list (in proper 804   * sequence), starting at the specified position in the list. 805   * The specified index indicates the first element that would be 806   * returned by an initial call to {@link ListIterator#next next}. 807   * An initial call to {@link ListIterator#previous previous} would 808   * return the element with the specified index minus one. 809   * 810   * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 811   * 812   * @throws IndexOutOfBoundsException {@inheritDoc} 813  */ 814  public ListIterator<E> listIterator(int index) { 815   if (index < 0 || index > size) 816    throw new IndexOutOfBoundsException("Index: "+index); 817   return new ListItr(index); 818  } 819  820  /** 821   * Returns a list iterator over the elements in this list (in proper 822   * sequence). 823   * 824   * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 825   * 826   * @see #listIterator(int) 827  */ 828  public ListIterator<E> listIterator() { 829   return new ListItr(0); 830  } 831  832  /** 833   * Returns an iterator over the elements in this list in proper sequence. 834   * 835   * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 836   * 837   * @return an iterator over the elements in this list in proper sequence 838  */ 839  public Iterator<E> iterator() { 840   return new Itr(); 841  } 842  843  /** 844   * An optimized version of AbstractList.Itr 845  */ 846  private class Itr implements Iterator<E> { 847   int cursor;  // index of next element to return 848   int lastRet = -1; // index of last element returned; -1 if no such 849   int expectedModCount = modCount; 850  851   Itr() {} 852  853   public boolean hasNext() { 854    return cursor != size; 855   } 856  857   @SuppressWarnings("unchecked") 858   public E next() { 859    checkForComodification(); 860    int i = cursor; 861    if (i >= size) 862     throw new NoSuchElementException(); 863    Object[] elementData = ArrayList.this.elementData; 864    if (i >= elementData.length) 865     throw new ConcurrentModificationException(); 866    cursor = i + 1; 867    return (E) elementData[lastRet = i]; 868   } 869  870   public void remove() { 871    if (lastRet < 0) 872     throw new IllegalStateException(); 873    checkForComodification(); 874  875    try { 876     ArrayList.this.remove(lastRet); 877     cursor = lastRet; 878     lastRet = -1; 879     expectedModCount = modCount; 880    } catch (IndexOutOfBoundsException ex) { 881     throw new ConcurrentModificationException(); 882    } 883   } 884  885   @Override 886   @SuppressWarnings("unchecked") 887   public void forEachRemaining(Consumer<? super E> consumer) { 888    Objects.requireNonNull(consumer); 889    final int size = ArrayList.this.size; 890    int i = cursor; 891    if (i >= size) { 892     return; 893    } 894    final Object[] elementData = ArrayList.this.elementData; 895    if (i >= elementData.length) { 896     throw new ConcurrentModificationException(); 897    } 898    while (i != size && modCount == expectedModCount) { 899     consumer.accept((E) elementData[i++]); 900    } 901    // update once at end of iteration to reduce heap write traffic 902    cursor = i; 903    lastRet = i - 1; 904    checkForComodification(); 905   } 906  907   final void checkForComodification() { 908    if (modCount != expectedModCount) 909     throw new ConcurrentModificationException(); 910   } 911  } 912  913  /** 914   * An optimized version of AbstractList.ListItr 915  */ 916  private class ListItr extends Itr implements ListIterator<E> { 917   ListItr(int index) { 918    super(); 919    cursor = index; 920   } 921  922   public boolean hasPrevious() { 923    return cursor != 0; 924   } 925  926   public int nextIndex() { 927    return cursor; 928   } 929  930   public int previousIndex() { 931    return cursor - 1; 932   } 933  934   @SuppressWarnings("unchecked") 935   public E previous() { 936    checkForComodification(); 937    int i = cursor - 1; 938    if (i < 0) 939     throw new NoSuchElementException(); 940    Object[] elementData = ArrayList.this.elementData; 941    if (i >= elementData.length) 942     throw new ConcurrentModificationException(); 943    cursor = i; 944    return (E) elementData[lastRet = i]; 945   } 946  947   public void set(E e) { 948    if (lastRet < 0) 949     throw new IllegalStateException(); 950    checkForComodification(); 951  952    try { 953     ArrayList.this.set(lastRet, e); 954    } catch (IndexOutOfBoundsException ex) { 955     throw new ConcurrentModificationException(); 956    } 957   } 958  959   public void add(E e) { 960    checkForComodification(); 961  962    try { 963     int i = cursor; 964     ArrayList.this.add(i, e); 965     cursor = i + 1; 966     lastRet = -1; 967     expectedModCount = modCount; 968    } catch (IndexOutOfBoundsException ex) { 969     throw new ConcurrentModificationException(); 970    } 971   } 972  } 973  974  /** 975   * Returns a view of the portion of this list between the specified 976   * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If 977   * {@code fromIndex} and {@code toIndex} are equal, the returned list is 978   * empty.) The returned list is backed by this list, so non-structural 979   * changes in the returned list are reflected in this list, and vice-versa. 980   * The returned list supports all of the optional list operations. 981   * 982   * <p>This method eliminates the need for explicit range operations (of 983   * the sort that commonly exist for arrays). Any operation that expects 984   * a list can be used as a range operation by passing a subList view 985   * instead of a whole list. For example, the following idiom 986   * removes a range of elements from a list: 987   * <pre> 988   *  list.subList(from, to).clear(); 989   * </pre> 990   * Similar idioms may be constructed for {@link #indexOf(Object)} and 991   * {@link #lastIndexOf(Object)}, and all of the algorithms in the 992   * {@link Collections} class can be applied to a subList. 993   * 994   * <p>The semantics of the list returned by this method become undefined if 995   * the backing list (i.e., this list) is <i>structurally modified</i> in 996   * any way other than via the returned list. (Structural modifications are 997   * those that change the size of this list, or otherwise perturb it in such 998   * a fashion that iterations in progress may yield incorrect results.) 999   *1000   * @throws IndexOutOfBoundsException {@inheritDoc}1001   * @throws IllegalArgumentException {@inheritDoc}1002  */1003  public List<E> subList(int fromIndex, int toIndex) {1004   subListRangeCheck(fromIndex, toIndex, size);1005   return new SubList(this, 0, fromIndex, toIndex);1006  }1007 1008  static void subListRangeCheck(int fromIndex, int toIndex, int size) {1009   if (fromIndex < 0)1010    throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);1011   if (toIndex > size)1012    throw new IndexOutOfBoundsException("toIndex = " + toIndex);1013   if (fromIndex > toIndex)1014    throw new IllegalArgumentException("fromIndex(" + fromIndex +1015            ") > toIndex(" + toIndex + ")");1016  }1017 1018  private class SubList extends AbstractList<E> implements RandomAccess {1019   private final AbstractList<E> parent;1020   private final int parentOffset;1021   private final int offset;1022   int size;1023 1024   SubList(AbstractList<E> parent,1025     int offset, int fromIndex, int toIndex) {1026    this.parent = parent;1027    this.parentOffset = fromIndex;1028    this.offset = offset + fromIndex;1029    this.size = toIndex - fromIndex;1030    this.modCount = ArrayList.this.modCount;1031   }1032 1033   public E set(int index, E e) {1034    rangeCheck(index);1035    checkForComodification();1036    E oldValue = ArrayList.this.elementData(offset + index);1037    ArrayList.this.elementData[offset + index] = e;1038    return oldValue;1039   }1040 1041   public E get(int index) {1042    rangeCheck(index);1043    checkForComodification();1044    return ArrayList.this.elementData(offset + index);1045   }1046 1047   public int size() {1048    checkForComodification();1049    return this.size;1050   }1051 1052   public void add(int index, E e) {1053    rangeCheckForAdd(index);1054    checkForComodification();1055    parent.add(parentOffset + index, e);1056    this.modCount = parent.modCount;1057    this.size++;1058   }1059 1060   public E remove(int index) {1061    rangeCheck(index);1062    checkForComodification();1063    E result = parent.remove(parentOffset + index);1064    this.modCount = parent.modCount;1065    this.size--;1066    return result;1067   }1068 1069   protected void removeRange(int fromIndex, int toIndex) {1070    checkForComodification();1071    parent.removeRange(parentOffset + fromIndex,1072        parentOffset + toIndex);1073    this.modCount = parent.modCount;1074    this.size -= toIndex - fromIndex;1075   }1076 1077   public boolean addAll(Collection<? extends E> c) {1078    return addAll(this.size, c);1079   }1080 1081   public boolean addAll(int index, Collection<? extends E> c) {1082    rangeCheckForAdd(index);1083    int cSize = c.size();1084    if (cSize==0)1085     return false;1086 1087    checkForComodification();1088    parent.addAll(parentOffset + index, c);1089    this.modCount = parent.modCount;1090    this.size += cSize;1091    return true;1092   }1093 1094   public Iterator<E> iterator() {1095    return listIterator();1096   }1097 1098   public ListIterator<E> listIterator(final int index) {1099    checkForComodification();1100    rangeCheckForAdd(index);1101    final int offset = this.offset;1102 1103    return new ListIterator<E>() {1104     int cursor = index;1105     int lastRet = -1;1106     int expectedModCount = ArrayList.this.modCount;1107 1108     public boolean hasNext() {1109      return cursor != SubList.this.size;1110     }1111 1112     @SuppressWarnings("unchecked")1113     public E next() {1114      checkForComodification();1115      int i = cursor;1116      if (i >= SubList.this.size)1117       throw new NoSuchElementException();1118      Object[] elementData = ArrayList.this.elementData;1119      if (offset + i >= elementData.length)1120       throw new ConcurrentModificationException();1121      cursor = i + 1;1122      return (E) elementData[offset + (lastRet = i)];1123     }1124 1125     public boolean hasPrevious() {1126      return cursor != 0;1127     }1128 1129     @SuppressWarnings("unchecked")1130     public E previous() {1131      checkForComodification();1132      int i = cursor - 1;1133      if (i < 0)1134       throw new NoSuchElementException();1135      Object[] elementData = ArrayList.this.elementData;1136      if (offset + i >= elementData.length)1137       throw new ConcurrentModificationException();1138      cursor = i;1139      return (E) elementData[offset + (lastRet = i)];1140     }1141 1142     @SuppressWarnings("unchecked")1143     public void forEachRemaining(Consumer<? super E> consumer) {1144      Objects.requireNonNull(consumer);1145      final int size = SubList.this.size;1146      int i = cursor;1147      if (i >= size) {1148       return;1149      }1150      final Object[] elementData = ArrayList.this.elementData;1151      if (offset + i >= elementData.length) {1152       throw new ConcurrentModificationException();1153      }1154      while (i != size && modCount == expectedModCount) {1155       consumer.accept((E) elementData[offset + (i++)]);1156      }1157      // update once at end of iteration to reduce heap write traffic1158      lastRet = cursor = i;1159      checkForComodification();1160     }1161 1162     public int nextIndex() {1163      return cursor;1164     }1165 1166     public int previousIndex() {1167      return cursor - 1;1168     }1169 1170     public void remove() {1171      if (lastRet < 0)1172       throw new IllegalStateException();1173      checkForComodification();1174 1175      try {1176       SubList.this.remove(lastRet);1177       cursor = lastRet;1178       lastRet = -1;1179       expectedModCount = ArrayList.this.modCount;1180      } catch (IndexOutOfBoundsException ex) {1181       throw new ConcurrentModificationException();1182      }1183     }1184 1185     public void set(E e) {1186      if (lastRet < 0)1187       throw new IllegalStateException();1188      checkForComodification();1189 1190      try {1191       ArrayList.this.set(offset + lastRet, e);1192      } catch (IndexOutOfBoundsException ex) {1193       throw new ConcurrentModificationException();1194      }1195     }1196 1197     public void add(E e) {1198      checkForComodification();1199 1200      try {1201       int i = cursor;1202       SubList.this.add(i, e);1203       cursor = i + 1;1204       lastRet = -1;1205       expectedModCount = ArrayList.this.modCount;1206      } catch (IndexOutOfBoundsException ex) {1207       throw new ConcurrentModificationException();1208      }1209     }1210 1211     final void checkForComodification() {1212      if (expectedModCount != ArrayList.this.modCount)1213       throw new ConcurrentModificationException();1214     }1215    };1216   }1217 1218   public List<E> subList(int fromIndex, int toIndex) {1219    subListRangeCheck(fromIndex, toIndex, size);1220    return new SubList(this, offset, fromIndex, toIndex);1221   }1222 1223   private void rangeCheck(int index) {1224    if (index < 0 || index >= this.size)1225     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));1226   }1227 1228   private void rangeCheckForAdd(int index) {1229    if (index < 0 || index > this.size)1230     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));1231   }1232 1233   private String outOfBoundsMsg(int index) {1234    return "Index: "+index+", Size: "+this.size;1235   }1236 1237   private void checkForComodification() {1238    if (ArrayList.this.modCount != this.modCount)1239     throw new ConcurrentModificationException();1240   }1241 1242   public Spliterator<E> spliterator() {1243    checkForComodification();1244    return new ArrayListSpliterator<E>(ArrayList.this, offset,1245            offset + this.size, this.modCount);1246   }1247  }1248 1249  @Override1250  public void forEach(Consumer<? super E> action) {1251   Objects.requireNonNull(action);1252   final int expectedModCount = modCount;1253   @SuppressWarnings("unchecked")1254   final E[] elementData = (E[]) this.elementData;1255   final int size = this.size;1256   for (int i=0; modCount == expectedModCount && i < size; i++) {1257    action.accept(elementData[i]);1258   }1259   if (modCount != expectedModCount) {1260    throw new ConcurrentModificationException();1261   }1262  }1263 1264  /**1265   * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>1266   * and <em>fail-fast</em> {@link Spliterator} over the elements in this1267   * list.1268   *1269   * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},1270   * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.1271   * Overriding implementations should document the reporting of additional1272   * characteristic values.1273   *1274   * @return a {@code Spliterator} over the elements in this list1275   * @since 1.81276  */1277  @Override1278  public Spliterator<E> spliterator() {1279   return new ArrayListSpliterator<>(this, 0, -1, 0);1280  }1281 1282  /** Index-based split-by-two, lazily initialized Spliterator */1283  static final class ArrayListSpliterator<E> implements Spliterator<E> {1284 1285   /*1286    * If ArrayLists were immutable, or structurally immutable (no1287    * adds, removes, etc), we could implement their spliterators1288    * with Arrays.spliterator. Instead we detect as much1289    * interference during traversal as practical without1290    * sacrificing much performance. We rely primarily on1291    * modCounts. These are not guaranteed to detect concurrency1292    * violations, and are sometimes overly conservative about1293    * within-thread interference, but detect enough problems to1294    * be worthwhile in practice. To carry this out, we (1) lazily1295    * initialize fence and expectedModCount until the latest1296    * point that we need to commit to the state we are checking1297    * against; thus improving precision. (This doesn't apply to1298    * SubLists, that create spliterators with current non-lazy1299    * values). (2) We perform only a single1300    * ConcurrentModificationException check at the end of forEach1301    * (the most performance-sensitive method). When using forEach1302    * (as opposed to iterators), we can normally only detect1303    * interference after actions, not before. Further1304    * CME-triggering checks apply to all other possible1305    * violations of assumptions for example null or too-small1306    * elementData array given its size(), that could only have1307    * occurred due to interference. This allows the inner loop1308    * of forEach to run without any further checks, and1309    * simplifies lambda-resolution. While this does entail a1310    * number of checks, note that in the common case of1311    * list.stream().forEach(a), no checks or other computation1312    * occur anywhere other than inside forEach itself. The other1313    * less-often-used methods cannot take advantage of most of1314    * these streamlinings.1315   */1316 1317   private final ArrayList<E> list;1318   private int index; // current index, modified on advance/split1319   private int fence; // -1 until used; then one past last index1320   private int expectedModCount; // initialized when fence set1321 1322   /** Create new spliterator covering the given range */1323   ArrayListSpliterator(ArrayList<E> list, int origin, int fence,1324        int expectedModCount) {1325    this.list = list; // OK if null unless traversed1326    this.index = origin;1327    this.fence = fence;1328    this.expectedModCount = expectedModCount;1329   }1330 1331   private int getFence() { // initialize fence to size on first use1332    int hi; // (a specialized variant appears in method forEach)1333    ArrayList<E> lst;1334    if ((hi = fence) < 0) {1335     if ((lst = list) == null)1336      hi = fence = 0;1337     else {1338      expectedModCount = lst.modCount;1339      hi = fence = lst.size;1340     }1341    }1342    return hi;1343   }1344 1345   public ArrayListSpliterator<E> trySplit() {1346    int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;1347    return (lo >= mid) ? null : // divide range in half unless too small1348     new ArrayListSpliterator<E>(list, lo, index = mid,1349            expectedModCount);1350   }1351 1352   public boolean tryAdvance(Consumer<? super E> action) {1353    if (action == null)1354     throw new NullPointerException();1355    int hi = getFence(), i = index;1356    if (i < hi) {1357     index = i + 1;1358     @SuppressWarnings("unchecked") E e = (E)list.elementData[i];1359     action.accept(e);1360     if (list.modCount != expectedModCount)1361      throw new ConcurrentModificationException();1362     return true;1363    }1364    return false;1365   }1366 1367   public void forEachRemaining(Consumer<? super E> action) {1368    int i, hi, mc; // hoist accesses and checks from loop1369    ArrayList<E> lst; Object[] a;1370    if (action == null)1371     throw new NullPointerException();1372    if ((lst = list) != null && (a = lst.elementData) != null) {1373     if ((hi = fence) < 0) {1374      mc = lst.modCount;1375      hi = lst.size;1376     }1377     else1378      mc = expectedModCount;1379     if ((i = index) >= 0 && (index = hi) <= a.length) {1380      for (; i < hi; ++i) {1381       @SuppressWarnings("unchecked") E e = (E) a[i];1382       action.accept(e);1383      }1384      if (lst.modCount == mc)1385       return;1386     }1387    }1388    throw new ConcurrentModificationException();1389   }1390 1391   public long estimateSize() {1392    return (long) (getFence() - index);1393   }1394 1395   public int characteristics() {1396    return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;1397   }1398  }1399 1400  @Override1401  public boolean removeIf(Predicate<? super E> filter) {1402   Objects.requireNonNull(filter);1403   // figure out which elements are to be removed1404   // any exception thrown from the filter predicate at this stage1405   // will leave the collection unmodified1406   int removeCount = 0;1407   final BitSet removeSet = new BitSet(size);1408   final int expectedModCount = modCount;1409   final int size = this.size;1410   for (int i=0; modCount == expectedModCount && i < size; i++) {1411    @SuppressWarnings("unchecked")1412    final E element = (E) elementData[i];1413    if (filter.test(element)) {1414     removeSet.set(i);1415     removeCount++;1416    }1417   }1418   if (modCount != expectedModCount) {1419    throw new ConcurrentModificationException();1420   }1421 1422   // shift surviving elements left over the spaces left by removed elements1423   final boolean anyToRemove = removeCount > 0;1424   if (anyToRemove) {1425    final int newSize = size - removeCount;1426    for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {1427     i = removeSet.nextClearBit(i);1428     elementData[j] = elementData[i];1429    }1430    for (int k=newSize; k < size; k++) {1431     elementData[k] = null; // Let gc do its work1432    }1433    this.size = newSize;1434    if (modCount != expectedModCount) {1435     throw new ConcurrentModificationException();1436    }1437    modCount++;1438   }1439 1440   return anyToRemove;1441  }1442 1443  @Override1444  @SuppressWarnings("unchecked")1445  public void replaceAll(UnaryOperator<E> operator) {1446   Objects.requireNonNull(operator);1447   final int expectedModCount = modCount;1448   final int size = this.size;1449   for (int i=0; modCount == expectedModCount && i < size; i++) {1450    elementData[i] = operator.apply((E) elementData[i]);1451   }1452   if (modCount != expectedModCount) {1453    throw new ConcurrentModificationException();1454   }1455   modCount++;1456  }1457 1458  @Override1459  @SuppressWarnings("unchecked")1460  public void sort(Comparator<? super E> c) {1461   final int expectedModCount = modCount;1462   Arrays.sort((E[]) elementData, 0, size, c);1463   if (modCount != expectedModCount) {1464    throw new ConcurrentModificationException();1465   }1466   modCount++;1467  }1468 }

View Code

2. 扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右。（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍-0.5）

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

 1 public boolean add(E e) { 2  ensureCapacityInternal(size + 1); // Increments modCount!! 3  elementData[size++] = e; 4  return true; 5 } 6  7 private void ensureCapacityInternal(int minCapacity) { 8  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 9   minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);10  }11  ensureExplicitCapacity(minCapacity);12 }13 14 private void ensureExplicitCapacity(int minCapacity) {15  modCount++;16  // overflow-conscious code17  if (minCapacity - elementData.length > 0)18   grow(minCapacity);19 }20 21 private void grow(int minCapacity) {22  // overflow-conscious code23  int oldCapacity = elementData.length;24  int newCapacity = oldCapacity + (oldCapacity >> 1);25  if (newCapacity - minCapacity < 0)26   newCapacity = minCapacity;27  if (newCapacity - MAX_ARRAY_SIZE > 0)28   newCapacity = hugeCapacity(minCapacity);29  // minCapacity is usually close to size, so this is a win:30  elementData = Arrays.copyOf(elementData, newCapacity);31 }

View Code

3. 删除元素

需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的。

 1 public E remove(int index) { 2  rangeCheck(index); 3  modCount++; 4  E oldValue = elementData(index); 5  int numMoved = size - index......
原文转载：http://www.shaoqun.com/a/883582.html
跨境电商：https://www.ikjzd.com/
自贸区跨境通网站：https://www.ikjzd.com/w/1329
 
patpat：https://www.ikjzd.com/w/1079.html
 
贝贝母婴网：https://www.ikjzd.com/w/1321
 
备战-Java容器　　　　玉阶生白露，夜久侵罗袜。简介：备战-Java容器一、概述容器主要包括Collection和Map两种，Collection存储着对象的集合，而Map存储着key-value键值对（两个对象）的映射表。Collection1.SetTreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如HashSet，HashSet查找的时间复杂度为
tenso：https://www.ikjzd.com/w/1552
marks spencer：https://www.ikjzd.com/w/2385
深度游魔都不可错过的事：漫步小马路：http://www.30bags.com/a/430325.html
深度游魔都不可错过的事：循迹张爱玲等：http://www.30bags.com/a/430326.html
深度游上海 在魔都不可错过的10件事：http://www.30bags.com/a/430327.html
深赴港办文体旅游专场推介会 ：http://www.30bags.com/a/409423.html
被两个男人咬住吃奶野战 一边亲一边扎下面很爽：http://lady.shaoqun.com/m/a/248384.html
少妇口述：因寂寞难耐而玩起换妻游戏(2/2)：http://www.30bags.com/m/a/249650.html
沃尔玛成为卖家第二市场？！第三方卖家数突破十万：https://www.ikjzd.com/articles/146699
南阳旅游景点大全 南阳有什么旅游景点 ：http://www.30bags.com/a/507644.html
2021深圳哪里最好玩 深圳有什么好玩的旅游景点 ：http://www.30bags.com/a/507645.html
2021晋江旅游景点大全 晋江市旅游景点有哪些 ：http://www.30bags.com/a/507646.html