最近在整理数据结构和算法，发现java的源码很优秀。就学习一下， 这里做个记录。
我使用的是jdk8
熟悉java的都知道ArrayList.
动态数组容器类。
具体的使用方法这里就不介绍了。
先概况看类，再细化具体method
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 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 = {};
/**
* 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
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
....
我们注意一下继承的类以及实现的接口
其中implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到上面有一个
transient Object[] elementData;
private int size;
这里定义一个数组用于保存数据， size记录数组中元素数量
我们看一下构造方法
// 给定容量大小
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);
}
}
// 没有指定容量，默认一个空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 直接放入一个容器对象，处理逻辑，将容器中数据copy到 成员变量 elementData 数组中
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
add
// 在尾部追加数据的
public boolean add(E e) {
modCount++; // 你不修改次数
add(e, elementData, size); // 加入数据
return true;
}
// s是索引位置
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length) // 如果添加数据溢出了，就动态扩容
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
// 这里扩容，并将原数组数据copy到新扩容的数组中
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
下面介绍一下，具体的扩容算法
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
正常情况下就是扩容 1.5倍， 另外也做一些边缘条件的判断。
我们再看一下删除
remove
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
// 删除指定位置数据，指定索引后面的数据进行搬移
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
迭代
先看源码吧
实现的迭代的接口
public ListIterator<E> listIterator(int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public Iterator<E> iterator() {
return new Itr();
}
其中 Iterator的接口方法
我们看下ArrayList的具体实现代码：
/**
* 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;
// prevent creating a synthetic constructor
Itr() {}
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
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int size = ArrayList.this.size;
int i = cursor;
if (i < size) {
final Object[] es = elementData;
if (i >= es.length)
throw new ConcurrentModificationException();
for (; i < size && modCount == expectedModCount; i++)
action.accept(elementAt(es, i));
// update once at end to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
上面通过
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
这三个值，暂时保存状态，进行迭代实现的。 modCount用于在迭代中操作数据出现异常，用于记录等作用。
对于 ArrayList,它的特点是内部采用动态数组实现,这决定了以下几点。
1)可以随机访问,按照索引位置进行访问效率很高,用算法描述中的术语,效率是O(1),简单说
就是可以一步到位。
2)除非数组已排序,否则按照内容查找元素效率比较低,具体是O(N),N为数组内容长度,也就
是说,性能与数组长度成正比。
3)添加元素的效率还可以,重新分配和复制数组的开销被平摊了,具体来说,添加N个元素的效率为O(N)。
4)插入和删除元素的效率比较低,因为需要移动元素,具体为O(N)
这里只是简单的介绍一些，只要把握底层是数组这条主线，其他的就简单了。
网友评论