ArrayList中提供了三个构造方法:
1、无参构造
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }此处注意其注释,说默认容量大小是10的空数组,其实这里只是给了一个空数组。在第一次添加元素的时候才将容量扩大为10的,如下:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }注意calculateCapacity方法:
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); // DEFAULT_CAPACITY==10 } return minCapacity; }2、自定义长度的构造方法:
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); } }以上两个构造函数可以看出,如果在创建结合实例时就知道容量大小,就直接给出需要的大小,性能更高。
3、参数为Collection的构造函数:
public ArrayList(Collection<? extends E> 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; } }这个构造函数稍微复杂一点,逻辑大致是先将集合转化为数组,然后通过反射的机制进行数组复制 。
以下我们通过我们惯用的“增删改查”的逻辑来看ArrayList的常用方法。
1、boolean add(E e)
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }我们上面提到了,这个方法是像集合中添加元素的方法,返回值是boolean类型。
注意:这个方法添加的元素都是集合的最后一个。
以下来分析底层实现:
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }重点关注ensureExplicitCapacity方法中的grow方法:
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } 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); }这个方法主要就是集合的扩容的底层方法。
注意,重点关注:
// 将集合扩充到原来的1.5倍。如果原来的容量是奇数n,则现扩充为n+(n-1)/2的长度。(这个也是与Vector的区别之一)。 int newCapacity = oldCapacity + (oldCapacity >> 1);如果扩充1.5倍后不够用,则扩充为传入的长度;
如果传入的长度大于2^31-1-8,则调用hugeCapacity方法:
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }2、void add(int index, E element)
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++; }这个方法基本与上个方法类似(底层调用的是同一个方法),不同的是,它是将元素添加到对应的位置上,同时向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。
3、boolean addAll(Collection<? extends E> c)
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; }这个方法也不用多说,基本上看命名和参数就知道有什么用途,底层也类似。
4、boolean addAll(int index, Collection<? extends E> c)
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; }我们将几个删除方法放在一起看看:
1、E remove(int index)
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; }2、boolean remove
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 }以上两个方法我们可以看出,集合的删除,基本上就是数组的(复制)操作,核心方法是System.arraycopy。我们看看该方法:
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);该方法是一个native方法,也即该方法与平台有关,非java语言实现。此处不做过多涉及。
3、boolean removeAll(Collection<?> c)
public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } 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; }4、void clear()
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }一目了然,清空数组。
1、E set(int index, E element)
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }注意:这个方法是将原有位置的元素进行替换,长度不变。
void sort(Comparator<? super E> c)
public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }集合排序。
通过以上的一些分析,我们基本上可以得出一个结论,也就是ArrayList的底层是数组,对ArrayList的操作,基本都是对数组的操作,归咎到数组的复制,数组元素的移动等。我们对于这种底层的认识很重要。
关于ArrayList和Vector区别如下:
ArrayList在内存不够时默认是扩展50% + 1个,Vector是默认扩展1倍。Vector提供indexOf(obj, start)接口,ArrayList没有。Vector属于线程安全级别的,但是大多数情况下不使用Vector,因为线程安全需要更大的系统开销。1、在《高效能程序员的修炼》一书中看到这样一句话,任何文档都比不上看源码,所有的本源都可以在源码中找到;
2、人类的智慧真的强大,而且在不断进步。就比如几个修改:
1)初始化
2)容量扩展计算改为了位移运算
3、读源码一定要深入进去,触类旁通,多多思考,多多对比。
转载于:https://www.cnblogs.com/yanfei1819/p/9951695.html
相关资源:ArrayList源码分析