JDK1.7
| 类 |
数据结构 |
默认容量 |
扩容 |
| ArrayList |
数组 |
10 |
1.5倍或增加数据后的长度 (取最大值) |
| Vector |
数组 |
10 |
指定扩容增量或2倍(取最大值) |
| LinkedList |
双向链表 |
无默认容量 |
不需要扩容 |
JDK1.8
| 类 |
数据结构 |
默认容量 |
扩容 |
| ArrayList |
数组 |
10 |
第一次最小为10、以后为1.5倍或增加数据后的长度(取最大值) |
| Vector |
数组 |
10 |
指定扩容增量或2倍(取最大值) |
| LinkedList |
双向链表 |
无默认容量 |
不需要扩容 |
ArrayList (jdk1.7、jdk1.8)
数据结构
jdk1.7
//数据存储结构
private transient Object[] elementData;
jdk1.8
//数据存储结构
transient Object[] elementData;
默认容量
jdk1.7
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
jdk1.8
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// size默认为0
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
扩容
jdk1.7
public boolean add(E e) {
// 扩容方法
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// 大于当前数组长度才进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容正常最大值（-8因为java有保留）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// minCapacity-->add、addAll 方法计算需要最小容量
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新数组大小为原有数组1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 默认扩容大小、数组需要容量最小值 判断取最大值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// System.arraycopy native方法
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 获取数组长度最最最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
jdk1.8
// 默认扩容大小
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
// 扩容方法
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//扩容内部方法
private void ensureCapacityInternal(int minCapacity) {
// 对象为空{},本方法为第一次调用。比较默认容量和参数指定容量,取最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 最小长度为默认的10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 扩容判断方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 大于数组长度才进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容正常最大值（-8因为java有保留）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//minCapacity-->add、addAll 方法计算需要最小容量
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新数组大小为原有数组1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 默认扩容大小、数组需要容量最小值 判断取最大值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// System.arraycopy native方法
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 获取数组长度最最最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Vector (jdk1.7、jdk1.8)
数据结构
jdk1.7
//数据结构
protected Object[] elementData;
// 容量增量
protected int capacityIncrement;
jdk1.8
// 数据结构
protected Object[] elementData
//容量增量
protected int capacityIncrement;
默认容量
jdk1.7
// 默认10
public Vector() {
this(10);
}
// 容量增量为0
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
jdk1.8
// 同jdk1.7
扩容
jdk1.7
// 同步add方法
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
// 扩容判断方法
private void ensureCapacityHelper(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 扩容增量大于0,按照指定的扩容增量增加,反之在原有长度上增加1倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
// 以下同ArrayList
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
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;
}
jdk1.8
// 同jdk1.7
LinkedList (jdk1.7、jdk1.8)
数据结构
jdk1.7
transient int size = 0;
transient Node<E> first;// 第一个元素
transient Node<E> last;// 最后一个元素
private static class Node<E> {
E item;//本身元素
Node<E> next;// 下一个元素对象引用
Node<E> prev;//上一个元素对象引用
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
jdk1.8
//同jdk1.7
默认容量
无默认容量(链表结构)
扩容
无需扩容,只要内存够大, 就可以无限制，前提是不考虑效率问题
