资讯专栏INFORMATION COLUMN

【java源码一带一路系列】之ArrayList

RebeccaZhong / 1810人阅读

摘要:一路至此,风景过半。与虽然名字各异,源码实现基本相同,除了增加了线程安全。同时注意溢出情况处理。同时增加了考虑并发问题。此外,源码中出现了大量泛型如。允许为非线程安全有序。

一路至此,风景过半。ArrayList与Vector虽然名字各异,源码实现基本相同,除了Vector增加了线程安全。所以作者建议我们在不需要线程安全的情况下尽量使用ArrayList。下面看看在ArrayList源码中遇到什么有趣的事情。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA
/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection"s
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652) ①
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

区别:DEFAULTCAPACITY_EMPTY_ELEMENTDATA用于无参初始化;EMPTY_ELEMENTDATA用于指定容量为0时的初始化。

trimToSize()
/**
 * Trims the capacity of this ArrayList instance to be the
 * list"s current size.  An application can use this operation to minimize
 * the storage of an ArrayList instance.
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

去除扩容后未存放元素的预留空间,以size为基准。

ensureCapacity() --> ensureExplicitCapacity() --> grow() --> hugeCapacity()
/**
 * Increases the capacity of this ArrayList instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It"s already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

预设容量(提前扩容),可提高初始化效率。扩容后比扩容前多了“oldCapacity >> 1”(即多了原来的50%)。同时注意溢出情况处理。(overflow-conscious code)。即“a-b<0”而不是"a

int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE + 1;    
System.out.println(a < b); // false    
System.out.println(a - b < 0); // true
toArray()
/**
 * Returns an array containing all of the elements in this list in proper
 * sequence (from first to last element); the runtime type of the returned
 * array is that of the specified array.  If the list fits in the
 * specified array, it is returned therein.  Otherwise, a new array is
 * allocated with the runtime type of the specified array and the size of
 * this list.
 *
 * 

If the list fits in the specified array with room to spare * (i.e., the array has more elements than the list), the element in * the array immediately following the end of the collection is set to * null. (This is useful in determining the length of the * list only if the caller knows that the list does not contain * any null elements.) * * @param a the array into which the elements of the list are to * be stored, if it is big enough; otherwise, a new array of the * same runtime type is allocated for this purpose. * @return an array containing the elements of the list * @throws ArrayStoreException if the runtime type of the specified array * is not a supertype of the runtime type of every element in * this list * @throws NullPointerException if the specified array is null */ @SuppressWarnings("unchecked") public 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); if (a.length > size) a[size] = null; return a; }

当传入数组长度大于ArrayList的size时,将a[size]置空作为调用者判断标志。根据这段代码写了个demo帮助理解:(扩展知识见②)

ArrayList al = new ArrayList();
al.add("s");

String[] s = {"c","h","e"};
String[] sal = (String[]) al.toArray(s);
System.out.println(sal[0] + "," + sal[1] + "," + sal[2]); // s,null,e
add()
/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
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++;
}

新增、删除都用到了System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);下面举例加深理解。

String[] arr ={"r", "e", "b", "e", "y", "."}; 
System.arraycopy(arr, 0, arr, 2, 2);
for(String i : arr) {
    System.out.println(i);
}

即将arr下标从0开始的2个元素拷贝到arr下标从2开始的位置。

retainAll()
/**
 * Retains only the elements in this list that are contained in the
 * specified collection.  In other words, removes from this list all
 * of its elements that are not contained in the specified collection.
 *
 * @param c collection containing elements to be retained in this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (optional)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (optional),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean retainAll(Collection c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

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;
}

a.retainAll(c)可以看成取a与c交集,a非c子集时,返回true。a中只留在c中存在的元素,其余删除。否则,返回false。

“elementData[w++] = elementData[r];”w永远小于等于r,因此可以将找到的相等元素大胆的放在elementData[w++]中(elementData[w++]是先放后加)。

iterator()
/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * 

The returned iterator is fail-fast. * * @return an iterator over the elements in this list in proper sequence */ public Iterator iterator() { return new Itr(); } /** * An optimized version of AbstractList.Itr */ private class Itr implements Iterator { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; // 是否有下一个元素 public boolean hasNext() { return cursor != size; } // 游标移动 @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; // !!! if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; //第一次cursor=1,lastRet=0 } // lastRet不等于-1时才能进行删除,即next()后才能使用remove() public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic !!! cursor = i; lastRet = i - 1; checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

Iterator()所指类似数据库的游标,不了解的同学可参看以下解释:

当使用语句Iterator it=List.Iterator()时,迭代器it指向的位置是Iterator1指向的位置,当执行语句it.next()之后,迭代器指向的位置后移到Iterator2指向的位置。[1]

由源码可见ArrayList的迭代器基于Itr子类实现。该类实现了Iterator接口,并重写了它的全部方法(4种)。同时增加了checkForComodification()考虑并发问题。

listIterator()
/**
 * Returns a list iterator over the elements in this list (in proper
 * sequence), starting at the specified position in the list.
 * The specified index indicates the first element that would be
 * returned by an initial call to {@link ListIterator#next next}.
 * An initial call to {@link ListIterator#previous previous} would
 * return the element with the specified index minus one.
 *
 * 

The returned list iterator is fail-fast. * * @throws IndexOutOfBoundsException {@inheritDoc} */ public ListIterator listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } /** * Returns a list iterator over the elements in this list (in proper * sequence). * *

The returned list iterator is fail-fast. * * @see #listIterator(int) */ public ListIterator listIterator() { return new ListItr(0); } /** * An optimized version of AbstractList.ListItr */ private class ListItr extends Itr implements ListIterator { ListItr(int index) { super(); cursor = index; } // 向前 public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } // 替换 public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }

listIterator有2中构造方法,即它多了指定游标的功能。它实现了ListIterator extends Iterator接口,比Iterator多了一些方法。Iterator只能从前往后删除,而listIterator可实现从后往前删除/替换。同时也提供了获取前后下标的方法。

说点什么

private class SubList extends AbstractList implements RandomAccess {...} 源码太长就不贴出来了。它是ArrayList的子类,表示ArrayList的子集,需要注意的是,对它的数据进行更改会影响原数据。

此外,源码中出现了大量泛型(如T、E...)。希望顺便巩固泛型知识。

ArrayList允许为null;非线程安全;有序。

更多有意思的内容,欢迎访问笔者小站: rebey.cn

知识点

1.[ArrayList c.toArray might (incorrectly) not return Object[] (see 6260652);](http://www.cnblogs.com/cmdra/...

2.[为什么 Java ArrayList.toArray(T[]) 方法的参数类型是 T 而不是 E ?](http://www.cnblogs.com/xiaomi...;2016.04.07;

[1]JAVA中ListIterator和Iterator详解与辨析;2014.11.27;

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70131.html

相关文章

  • java源码一带一路系列LinkedHashMap.afterNodeAccess()

    摘要:如今行至于此,当观赏一方。由于所返回的无执行意义。源码阅读总体门槛相对而言比,毕竟大多数底层都由实现了。比心可通过这篇文章理解创建一个实例过程图工作原理往期线路回顾源码一带一路系列之源码一带一路系列之源码一带一路系列之 本文以jdk1.8中LinkedHashMap.afterNodeAccess()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程...

    levy9527 评论0 收藏0
  • java源码一带一路系列HashSet、LinkedHashSet、TreeSet

    摘要:同样在源码的与分别见看到老朋友和。这样做可以降低性能消耗的同时,还可以减少序列化字节流的大小,从而减少网络开销框架中。使用了反射来寻找是否声明了这两个方法。十进制和,通过返回值能反应当前状态。 Map篇暂告段落,却并非离我们而去。这不在本篇中你就能经常见到她。HashSet、LinkedHashSet、TreeSet各自基于对应Map实现,各自源码内容较少,因此归纳为一篇。 HashS...

    UCloud 评论0 收藏0
  • java源码一带一路系列HashMap.compute()

    摘要:本篇涉及少许以下简称新特性,请驴友们系好安全带,准备开车。观光线路图是在中新增的一个方法,相对而言较为陌生。其作用是把的计算结果关联到上即返回值作为新。实际上,乃缩写,即二元函数之意类似。 本文以jdk1.8中HashMap.compute()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程)。本篇涉及少许Java8(以下简称J8)新特性,请驴友们...

    wapeyang 评论0 收藏0
  • java源码一带一路系列HashMap.putAll()

    摘要:观光线路图将涉及到的源码全局变量哈希表初始化长度默认值是负载因子默认表示的填满程度。根据是否为零将原链表拆分成个链表,一部分仍保留在原链表中不需要移动,一部分移动到原索引的新链表中。 前言 本文以jdk1.8中HashMap.putAll()方法为切入点,分析其中难理解、有价值的源码片段(类似ctrl+鼠标左键查看的源码过程)。✈观光线路图:putAll() --> putMapEnt...

    chanjarster 评论0 收藏0
  • java源码一带一路系列HashMap.putVal()

    摘要:表示该类本身不可比表示与对应的之间不可比。当数目满足时,链表将转为红黑树结构,否则继续扩容。至此,插入告一段落。当超出时,哈希表将会即内部数据结构重建至大约两倍。要注意的是使用许多有这相同的键值肯定会降低哈希表性能。 回顾上期✈观光线路图:putAll() --> putMapEntries() --> tableSizeFor() --> resize() --> hash() --...

    cloud 评论0 收藏0

发表评论

0条评论

RebeccaZhong

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<