ArrayList，
分享于 点击 28864 次 点评：12
ArrayList，
ArrayList
大小可变的数组，实现了List接口，允许null值。
set,get,iterator,listIterator,isEmpty,size的时间复杂度是常数时间
add方法是摊还常量时间。这意味着增加n个元素需要花费O（n）
其他方法的时间复杂度是线性时间
底层存储
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
* 默认的容量为10.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 共用的空数组。
* 1.用户声明了一个初始容量为0的数组 new ArrayList<>(0);
* 2.用户使用一个大小为0 的Colection来初始化实例 new ArrayList<>(一个size为0的collection)
* 3.用户使用trimSize的时候，数组中没有存储元素（size==0）
* 使用static和final修饰是为了让所有的类共用，减少一些内存吧。
*/
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.
* 默认容量下的空数组
* 这个空数组用在用户使用new ArrayList<>()构造器构造的实例中。
* 在使用这个构造器的时候，没有添加第一条数据时，使用它。
*/
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.
* 存储ArrayList元素的数组
* capacity是数组的大小，即当前数组能够存储多少元素。
* size是数组已经存储的元素。
* 大多数的集合类都有这两个特性。size指示当前大小，作为一个私有属性。capacity通常是通过底层结构的大小来获得。
*/
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;ArrayList底层使用数组来存储元素
3.动态增长
对于一个集合需要关注的主要信息在于：底层存储元素的方式，插入操作的实现及耗时，删除操作的实现，动态增长的时机和方式
对于ArrayList来说，底层使用数组来存储元素。
ArrayList的初始化
/**
* Constructs an empty list with the specified initial capacity.
* 构造一个拥有初始容量的数组。
* 如果参数大于0.则直接开一块内存空间，大小为4字节*capacity。否则使用EMPTY_ELEMENTDATA。
* @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.
* 构造一个初始容量为10的数组。不过这里并没有显示出来。暂时使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA;初始容量为10在哪里用到的呢。
* 想象插入第一个元素的时候，elementData的大小为0.需要为他分配空间，这个时候为他分配大小为10的空间
*/
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.
*这个里面有一个当elementData的类不是Object[]时，重新复制一次。这是因为c.toArray()会有不同的类型。（？？？）
* @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;
}
}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;
}/**
* 保证容量。注意几个需要动态增长的时机。1.第一次添加元素，minCapacity=1。2.数组已经填满minCapacity=size+1
* calculateCapacity(elementData, minCapacity)计算数组需要的容量
*
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 如果数组是使用无参构造器构造的，则返回10
* 否则返回minCapacity
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* minCapacity为10.或者为size+1
* modCount++:向数组增加一个元素，数组必定发生结构化的变化。结构化的变化值得是数组中存储的元素的多少有变化。仅是值得变化并不是结构化变化。
*
* 如果需要的长度大于当前数组的长度，即需要扩容的时候，使用grow（minCapacity）来扩容。如果需要的长度小于当前数组的长度，即（数组还有空间存新的元素）,不需要扩容.
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 增加数组的容量来保证它至少可以存储minCapacity个元素。
* newCapacity=oldCapacity*1.5
* @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);
}我们再来回到Add方法，保证数组的容量之后，就是设置新元素。
add(int index,E e).方法和上述一样。只是有一个移动元素的时间开销
/**
* 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++;
}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) {
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;
}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) {
rangeCheck(index);
return elementData(index);
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}总结：
Add摊还时间。Remove(index)常数时间，remove(Object)线性时间，set(index)常数时间,get(index)常数时间
ArrayList初始容量为10，每次增长1.5倍
测试
public class ArrayListTest {
public static void main(String[] args) {
//0
//add("0") ___ 1,10
//add("1") ___ 2,10....
//add("10") ___11,15... 下一次增长至15+7=22
ArrayList<String> list = new ArrayList<>();
for(int i=0; i<22; i++){
list.add("i"+i);
}
//初始容量为13,第一次增长至13+6=19,第二次增长至19+9=28
ArrayList<String> list1 = new ArrayList<>(13);
for(int i=0; i<26; i++){
list1.add(i+"");
}
}
}相关文章
- 暂无相关文章
用户点评