版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/81383693
ArrayList
ArrayList是基于数组
实现的,是一个动态数组
,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。
- ArrayList
不是线程安全
的,只能用在单线程环境
下 - 多线程环境下可以考虑用
Collections.synchronizedList(List l)函数
返回一个线程安全的ArrayList类 - 也可以使用concurrent并发包下的
CopyOnWriteArrayList类
- ArrayList
实现了Serializable接口
,因此它支持序列化,能够通过序列化传输 - 实现了
RandomAccess接口
,支持快速随机访问,实际上就是通过下标序号进行快速访问 - 实现了
Cloneable接口
,能被克隆
根据JDK版本的不同 ,构造方法也不同
/**
* JDK 1.8
*/
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 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 = {};
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 上面这个对象数组就是其存储元素的数据结构,前面有一个java关键字transient
* 这个关键字是去序列化的意思,即,在这个类序列化后保存到磁盘或者输出到输出流的时候
* 这个对象数组是不被保存或者输出的。(这个不是下面的翻译,对transient解释)
*
* 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
/**
* ArrayList带容量大小的构造函数。
* 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);
}
}
/**
* 无参构造方法构造的ArrayList的默认返回空数组
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 带有Collection参数的构造方法
* 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;
}
}
/**
* JDK 1.7/1.6
*/
/**
* 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) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 无参构造直接返回了this(10);默认10 这也是与1.8不同的地方
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 在这1.8也多了一个判断
* @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();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
为什么用到 transient?
这就跟这个ArrayList的特性有关,我们知道ArrayList的容量,也就是这个数组的容量,一般都是预留一些容量,等到容量不够时再拓展,那么就会出现容量还有冗余的情况,如果这时候进行序列化,整个数组都会被序列化,连后面没有意义空元素的也被序列化。这些是不应该被存储的。所以java的设计者,就为这个类提供了一个writeObject方法,在实现了Serializable接口的类,如果这个类提供了writeObject方法,那么在进行序列化的时候就会通过writeObject方法进行序列化,所以ArrayList的writeObject方法就会显式的为每个实际的数组元素进行序列化,只序列化有用的元素。
为什么源码中大量地调用了Arrays.copyof()和System.arraycopy()方法?
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
最后都调用了System.arraycopy()方法。
/**
* 该方法被标记了native,调用了系统的C/C++代码,在JDK中是看不到的,
* 但在openJDK中可以看到其源码。该函数实际上最终调用了C语言的memmove()函数,
* 因此它可以保证同一个数组内元素的正确复制 和移动,比一般的复制方法的实现效率要高很多,
* 很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法,以取得更高的效率。
* 这也说明了ArrayList 与数组
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
JDK1.6 开始扩容办法也不一样
/**
* JDK1.6
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* JDK1.8
*/
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- 1.7JDK开始使用的是位运算
- 在算出newCapacity时,其没有和ArrayList所定义的MAX_ARRAY_SIZE作比较,为什么没有进行比较呢,原因是jdk1.6没有定义这个MAX_ARRAY_SIZE最大容量,也就是说,其没有最大容量限制的,但是jdk1.7以上做了一个改进,进行了容量限制。
Java 集合中常见 checkForComodification()方法的作用? modCount和expectedModCount作用?
ArrayList 快速访问
ArrayList基于数组实现,可以通过下标索引直接查找到指定位置的元素,因此查找效率高,但每次插入或删除元素,就要大量地移动元素,插入删除元素的效率低。
/**
* 先检查索引 然后校验操作正确
*/
public E get(int var1) {
this.rangeCheck(var1);
return this.elementData(var1);
}