我在写程序的时候经常会用到数组或者是集合，与数组相比，我更喜欢用List<T>集合，因为他不用规定数组的上限，可以无限量的添加，那么List<T> 集合里面是什么原理呢。
在写代码的时候我经常会用的ArrarList<T>,那么我们从ArrayList<T>开始看起吧
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
...
}
public interface List<E> extends Collection<E> {
...
}
public interface Collection<E> extends Iterable<E> {
...
}
public interface Iterable<T> {
...
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
...
}
public abstract class AbstractCollection<E> implements Collection<E> {
...
}
我们从上面可以看到，ArrayList实现自List,List实现自Collection,Collection实现自Iterable,Iterable是一个接口，上面这些类处ArrayList外都是接口。
然后ArrayList还继承自抽象类AbstractList，AbstractList实现自Collection
我从网上找到一张图，我们可以看一下
三种list集合对比.png
从图中我们可以看到集合除了ArrayList外还有LinkList Track vector,集合，那么他们有什么区别呢，可以简单概括一下
1.arrayList是一个数组，查询效率快，但是插入删除效率低，这是由于数组的特性决定的
2.linkedlist双向链表，查询效率低，但是插入删除效率高，这是由于链表的特性决定的
3.vector同arrayList相似，只不过vector是线程安全的
4.stack继承vector，有着先进后出的特性
什么是线程安全可以看我写的另一篇文章
关于线程安全的一些理解与同步锁synchronized的使用
ArrayList的构造方法
所有的类都是从初始化开始的，我们先来看先ArrayList的构造好处
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
transient Object[] elementData; // non-private to simplify nested class access
/**
* 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<? 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有三个初始化方法，初始化的时候都是对elementData 这个Object数组进行初始化
- ArrayList()方法，是开辟了一个空的object数组，然后赋值给 elementData
- ArrayList(int initialCapacity)方法，是开辟了initialCapacity 个object数组空间，然后赋值给 elementData
- ArrayList(Collection<? extends E> c)方法，是将传入的继承自Collection的集合对象，直接转化成Object数组然后赋值给elementData
ArrayList的Add方法
接下来我们看看add的方法
/**
* 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) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
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;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(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;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果集合是空的
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY值是10
}
//如果minCapacity的值
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)//当添加的集合的长度+1大于elementData的最大长度
grow(minCapacity);//对数组进行扩容
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//新的大小 1.5倍
if (newCapacity - minCapacity < 0) //如果minCapacity>newCapacity 则使用minCapacity
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
newCapacity = hugeCapacity(minCapacity);//判断临界值 Integer.MAX_VALUE
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
从上面的代码我们可以看到在add的方法中
1.先判断插入的新值后是否会超出elementData数组的大小
2.如果超出了则对数组进行扩容，每次会扩容1.5倍，如果1.5倍还不能满足，则将数组扩容到，原有size+插入数据的size。
3.将传入的对象赋值到elementData 集合中去
我再写代码的时候喜欢用集合的原因是因为数组还得扩容，觉得使用起来非常麻烦，在集合里面就不用考虑这个问题，所以我觉得集合操作上还是很方便的
ArrayList的get set方法
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
get与set方法很简单，就是单纯的根据index来查找elementData中的位置
ArrayList的Remove方法
/**
* 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) {
if (index >= size) //判断是否越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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;
}
//与remove(int index) 类似，只不过不返回对象
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
}
我们可以看到remove有两个方法，一个是根据index,一个是根据Object移除
- 根据index移除的会先根据index获取对象，然后对数组进行赋值操作，并将数组最后无用的对象置空处理，然后返回移除的对象
- 根据Object移除的则是先遍历elementData数组然后获取到index，再根据index最数组进行赋值操作，最后返回boolean类型值
从上面两种remove方法中我们可以想象的到remove(Object) 比remove(int)在效率上要慢的很多
remove多个元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);//判断是否为null
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
//w表示批量删除后数组还剩多少元素
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)//遍历集合
//根据complement值来判断保留的元素
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 出现异常会导致r != size，则将出现异常的数据全部添加到保留的数组里，不进行删除
if (r != size) {
//将异常的数据插入要保留的数组里
System.arraycopy(elementData, r,
elementData, w,
size - r);
//修改w的数量，将剩余异常的数据长度加到要保留的长度上
w += size - r;
}
//判断要保留的长度和集合长度是否一致，
if (w != size) {
// clear to let GC do its work
// 将删除空出来的下标全部置为null
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);//判断是否为null
return batchRemove(c, true);
}
removeAll与retainAll的区别就是调用batchRemove方法的complement参数出入的不同，然后根据complement值来判断应该留下的数组，然后对数组进行赋值与置空的操作
contains clear isEmpty操作
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 void clear() {
//修改modCount
modCount++;
// 将所有下标数据都置为null，保留数组大小
for (int i = 0; i < size; i++)
elementData[i] = null;
//修改size大小
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
我觉得这几个方法没什么可说的了，都是一面了然
迭代器 Iterator
public Iterator<E> iterator() {
return new 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) elemenctData[lastRet = i];
}
//删除掉上一次next的元素
public void remove() {
//判断是否执行过next
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
//要删除的下标
cursor = lastRet;
//防止重复删除，将下标置为-1
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//判断是否修改过集合的结构，如果修改过直接抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
以上就是对ArrayList的源码解析
总的来说ArrayList实际上是对elemenctData数组进行的操作
- ArrayList是线性表中的顺序存储结构的顺序表，因为内部维护的是一个数组，数组是一个拥有连续存储地址的存储块。
- ArrayList因为内部维护的是一个数组，查询和修改的效率很高，但是插入添加和删除的效率比较低，特别是数据量大的情况下必较明显。
- 在使用普通的for循环遍历ArrayList的时候删除其中的元素容易出现数据删除错乱问题，改用Iterator迭代器能够很好的解决这个问题。
- ArrayList在添加元素的时候是允许加入null元素的，为了避免后续使用数据时出现NullPointerException的异常，请先对要添加的元素做非空判断。
- ArrayList从上面的源码分析可以看出，它可以添加重复的元素对象，所以在添加对象的时候做好相等对象的判断。
- 从上面源码可以看出，ArrayList的size和真实申请的堆内存对象容量不同，所以在使用的时候控制好ArrayList的容量使用也是很好的性能优化手段。
- ArrayList的是线程不安全的，在多线程环境下需要注意对象数据同步问题。
网友评论