解析ArrayList类
ArrayList类的继承关系
在这上面可以看到ArrayList和AbstractList都是实现了List接口， 但是ArrayList又是继承了AbstractList， 所以我在看这一段代码的时候就很疑惑， 作者这样做的目的是什么？
http://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete
可以看看这个答案， 目的就是当初作者说明这就是一个写法错误。
如何进行初始化的？
/**
* 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 = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 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<? 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;
}
}
在上面的这一段中可以看到有三个构造方法， 我们来一个个的说一下各自的作用
1.无参构造方法：这个构造方法就是初始化一个集合对象， 默认的是一个容量为10的一个值， 但是要在第一次添加的时候才会填充进去。
2.第二个构造方法是传一个大小的值， 直接对Object数组对象进行初始化。
3.第三个构造方法是传一个Collection的集合， 这个时候泛型的好处就来了，在那个构造方法中不允许传和当前集合元素没有关系的类型。Collection<? extends E> c
如何添加、删除、遍历、替换。。
添加和插入
/**
* 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;
}
/**
* 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++;
}
在上面这一段代码中可以看到添加有2个方法， 默认的是不带索引的添加， 而下面一个复写的方法是带索引的方法
-
boolean add(E e)
这一个就是直接在数组的尾部添加一个元素， 但是在添加之前我们可以看方法上面有一个**ensureCapacityInternal(size + 1)**的这样一个方法， 这个方法是检验是否这个数组的大小能不能继续添加元素，如果不能， 那么就进行扩容操作， 扩容操作就是将当前数组的容量扩容一半。然后在尾部进行添加
/**
* 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);
}
最主要的就是设置大小这里， 这里涉及到了位运算， 在这里我们可以看到，进行了右移操作
-
void add(int index, E element)
这个方法就是将指定的对象插入到数组指定的位置当中去， 这个做法是非常消耗性能的， 如果说需要大量的这种指定插入的话， 建议的方法是用LinkedList, 链表(LinkedList)
删除元素
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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 remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
可以看到， 删除也是两个方法， 不过和添加不同， 默认的不是从尾部或者头部开始删除。而是说默认的是指定集合的下标开始删除。
-
E remove(int index)
从指定的下标开始删除， 和插入的道理是相通的 -
boolean remove(Object o)
这个方法的实现可以看一下， 这里面实现了一个如果传过来的是null,这个删除动作也会将数据为null的给删除掉。默认是用equals来进行比较。
-
void fastRemove(int index)
- 可以看到，这个方法才是真正进行删除的方法， 是一个私有的方法， 实现的方式也很特别， 是通过拷贝方式来实现的， 我们可以来看一下这个方法。
这里删除用了将后面一部分的元素替换了前面的一部分元素， 然后将结尾的删除掉
/*
* @param src 这个源数组
* @param srcPos 源数组启始的下标位置
* @param dest 目的地的数组
* @param destPos 目的地开始的下标位置
* @param length 需要拷贝多少个元素
* @exception IndexOutOfBoundsException if copying would cause
* access of data outside array bounds.
* @exception ArrayStoreException if an element in the <code>src</code>
* array could not be stored into the <code>dest</code> array
* because of a type mismatch.
* @exception NullPointerException if either <code>src</code> or
* <code>dest</code> is <code>null</code>.
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
替换操作
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
-
void replaceAll(UnaryOperator operator)
这里面的参数是1.8里面新加入的一个功能， lambda表达式， 又是一个函数式编程， 这里就不再说明函数式编程是啥， 这个参数的作用就是UnaryOperator传入两个相同类型的参数最终返回一个同类型的对象
遍历操作
在Collection类里面就已经继承了Iterable的这一个接口了， 这个接口里面有一个Iterator抽象方法
public interface Iterable<T> {
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
可以看见， 其他两个方法都是在1.8之后进行加入的默认方法， 可以默认不进行继承， 这个操作也是为了方便lambda表达式的使用而构建的， 具体去参考lambda函数式编程这一本书。
那么这个迭代器是干吗的呢？就是进行迭代的。。。
里面的类有兴趣自己去看看， 这里就不在进行深入去讲了，
回到ArrayList。
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
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];
}
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<? super E> 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();
}
}
- 私有的内部类有什么好处呢？
第一个就是可以访问外部的私有属性和其他属性， 因为自己也是外面的一部分。
第二就是外面可以进行实例化内部的类， 而在其他包里面是访问不到这个类的存在的。
详细的点击链接
-
boolean hasNext()
这个方法实现就是当前的位置是不是到头了？如果是，就返回false， 否则返回true
-
void remove()
删除当前下标前一个元素， 而不是当前下标的元素。首先会判断当前的元素有没有迭代， 如果有迭代至少一次才能删除， 不然就是状态异常
IllegalStateException， 接下来才会判断是否有无其他线程在操作。在java语言中， 如果内部类和主类有相同的方法名怎么办， 这时候就需要指定一个方法名this派上用场了，调用ArrayList.this.remove() 删除方法。最后要进行变量置等。 -
E next()
看着个方法就知道是干嘛的， 这个方法就是返回当前下标的元素， 看看里面具体做了什么操作。
1.checkForComodification(); 这个方法是干啥的呢？也就是说，在我用这个对象的时候， 对对象有添加或者删除这种更改数据行为的操作都是非法的！我们可以看看源码，modCount 这个字段就是做了操作就会进行递增， 如果当前expectedModCount 和 modCount不相等的话， 那么就会抛ConcurrentModificationException(其他线程修改异常)， 那么我们要删除怎么办， 在迭代器提供了删除操作。往下看，就是常规的操作了 -
void forEachRemaining(Consumer<? super E> consumer)
不得不说啊， 在1.8之后， 大量的采用了lambda的机制！可以看见，这个方法里面的参数是Consumer<? super E> consumer这里进行了类型限制， 并且这个类是一个消费者模型， 也就是说！这个对象就是拿来消费的！这个方法的作用就是从当前下标来进行遍历操作， 消费后面的元素。
增强版的遍历操作
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
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();
}
}
}
可以看继承结构就可以看得出来， 这个是在Itr内部类的基础之上而做出的增强版操作
1.允许初始化的时候任意指定下标位置
2.允许向前遍历
3.允许添加操作
4.允许更改操作
SubList子类
这个类的作用是用来截取当前集合中的一部分数据，但是你在这部分数据中进行操作，特别是那种影响结构的操作， 会直接影响到主集合， 所以操作的时候要小心，但是在网上有一个集合split的操作却是经典
/** Split a list into two sublists. The original list will be modified to
* have size i and will contain exactly the same elements at indices 0
* through i-1 as it had originally; the returned list will have size
* len-i (where len is the size of the original list before the call)
* and will have the same elements at indices 0 through len-(i+1) as
* the original list had at indices i through len-1.
*/
<T> List<T> split(List<T> list, int i);