ArrayList源码解析（中）

2019-11-10 19:32:29

字体：大中小

来源：转载

供稿：网友

判断元素位置

这些函数都相对简单。因为存储的元素可能为null，所以判断的时候多了一次。

public int size() { return size;}public boolean isEmpty() { return size == 0;}public boolean contains(Object o) { return indexOf(o) >= 0;}public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1;}public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1;}

数组转化

toArray()重载了两个方法，其中一个返回Object[]，另外一个返回指定类型的数组。对于有参的方法的调用建议：传入一个空的对象，如 new Integer[]{} 作为参数。关于ClassCastException异常：经常会需要将ArrayList里的内容转化为特定类型的数组，但是如果使用无参的toArray()进行强制转换，就会出现ClassCastException异常。此时需要使用第二个有参的方法。例如类似于： (Integer[]) ArrayList某个实例.toArray(new Integer[]{})。在我们使用 T[] toArray(T[] a) 的时候还需要再一次进行显式的转化，这点有点不懂。因为这个函数内部已经转化了，但是我们还需要 (Integer[]) ArrayList某个实例.toArray(new Integer[]{}) 这么写，而不是 ArrayList某个实例.toArray(new Integer[]{}) 这么写？依旧是有参的那个函数，如果传入的参数的长度大于size，得到的结果会变得没有使用意义，正如下面代码注释里演示的一样。public Object clone() { try { @SupPRessWarnings("unchecked") ArrayList<E> v = (ArrayList<E>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } }public Object[] toArray() { return Arrays.copyOf(elementData, size);}@SuppressWarnings("unchecked")public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); // 如果a的长度大于size，a[size] = null，这个逻辑不知为何这么设计，不理解 // 比如elementData{1,2}, a{3,4,5}, 得到的结果会是{1,2,null,4,5} if (a.length > size) a[size] = null; return a;}

增删改查

// Positional access Operations@SuppressWarnings("unchecked")E elementData(int index) { return (E) elementData[index];}public E get(int index) { rangeCheck(index); return elementData(index);}public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;}add操作时怎么扩充容量？调用ensureCapacityInternal(size + 1) 方法，如果 size+1 < elementData.length，则表示容量充足，不需要扩充；如果反之，那么容量扩充到原来的elementData.length 的1.5倍。在进行add操作的时候，都会尝试对elementData扩充容量(ensureCapacityInternal()方法)，这里有个提升效率的技巧，详见ArrayList源码解析（上）的 “关于扩展容量的相关操作” 段落。/*** 每次进行增加操作的时候，都会尝试扩充elementData的容量*/public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true;}public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++;}public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0;}public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0;}public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue;}public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false;}private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work}public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0;}protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize;}private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size;}public boolean removeAll(Collection<?> c) { return batchRemove(c, false);}public boolean retainAll(Collection<?> c) { return batchRemove(c, true);}

关于batchRemove()方法 1. 批量删除的方法，具体是对集合c和elementData的交集处理，这里详细说明一下。

假如集合c和elementData的交集是U，那么，如果complement是true，elementData最终会只存储U；如果complement是false，elementData最终删除U。

2. 在对elementData的元素进行筛选的时候，这里使用了r、w两个游标，从而避免从新开辟一个新的数组进行存储。这种方法也是比较常见的一种算法题。

private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { // 在原有数组上进行筛选的方法，而不是另外开辟一个新的数组 for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified;}

上一篇：eclipse安装Activiti Designer插件

下一篇：[TsinsenA1490] osu!（乔明达）