转载请注明原文地址: http://zk-chs.iteye.com/blog/2250804
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
上面是是ArrayList类的定义,它继承了抽象类AbstractList,但是真正继承的方法只有equals和hashCode,
别的方法在ArrayList 中都有自己的重新实现;
List接口在AbstractList中已经实现,这里是为了表明一下,没有太大含义;
RandomAccess没有方法,表明ArrayList支持快速随机访问;
实 现了 Cloneable 接口,以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制,如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法,则会导致抛出 CloneNotSupportedException 异常;
类通过实现 java.io.Serializable 接口以启用其序列化功能,未实现此接口的类将无法使其任何状态序列化或反序列化
transient Object[] elementData; // 我们用于存储数据的数组
private static final int DEFAULT_CAPACITY = 10; // 默认大小为10
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private int size; // elementDate中对象数量,不是length
protected transient int modCount = 0; // 用于并发使用
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
EMPTY_ELEMENTDATA在使用带参数构造函数时使用;
DEFAULTCAPACITY_EMPTY_ELEMENTDATA在使用默认构造函数时使用;
DEFAULT_CAPACITY会在默认构造函数实例的第一次调用add方法时使用;
modCount:当迭代时,如果modCount发生了变化,那么抛出并发修改异常(ConcurrentModificationException);
关于ArrayList的域就介绍这么多,下面看看方法:
public boolean add(E e):
// 在当前列表末尾添加一个对象,而不是数组
public boolean add(E e) {
// 确认数组大小,并让modCount + 1
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// if判断用于第一次调用add,如果是使用无参构造函数,那么进入此方法,设置minCapacity为10
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // first add
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// modCount自增,并判断数组大小是否足够,不够的话将增大数组(下面介绍grow)
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判断数组大小是否足够
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity):这是private方法,不能使用
private void grow(int minCapacity) { // 传入需要的数组大小
// oldCapacity为当前数组大小
int oldCapacity = elementData.length;
// 设置新数组大小的值,为当前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 当addAll时可能新数组大小也不够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// newCapacity可能会溢出,这里做判断
if (newCapacity - MAX_ARRAY_SIZE > 0) // MAX_ARRAY_SIZE = 2147483639
newCapacity = hugeCapacity(minCapacity);
// 使用Arrays扩展数组至newCapacity
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 : //2147483647
MAX_ARRAY_SIZE; // 2147483639
}
public boolean addAll(Collection<? extends E> c):
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); // 传入集合的数组显示
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 同上
// 将a的numNew长度的元素添加到elementDate的末尾
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew; // 对象数量增长numNew
return numNew != 0; // 如果c刚刚创建没有调用add,那么numNew会为0
}
public void add(int index, E element) 和 public boolean addAll(int index, Collection<? extends E> c):
// 从指定索引位置插入元素
public void add(int index, E element) {
rangeCheckForAdd(index); // 判断插入位置是否越界
// 和add没什么不同
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这就是我们常说的后移一位,其实是从指定位置开始复制
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// 同上
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(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;
}
// 用于add和addAll 判断传入的索引值index是否越界
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
需要注意:不管addAll添加多少元素,modCount只会自增1!!!
public E get(int index):
public E get(int index) { // 获取指定位置元素
rangeCheck(index); // 注意 这里不是rangeCheckForAdd,下面介绍
return elementData(index);
}
public E set(int index, E element):
// 替换指定索引位置的元素,返回原位置元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public E remove(int index):已经申请的内存空间不会回收(删除指定索引位置元素)
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); // 相当于index+1后的元素前移一位
elementData[--size] = null; // clear to let GC do its work 通知jvm回收,防止内存泄漏
return oldValue; // 返回从list中移除的元素
}
// 这里仅与size比较,小于0数组本身会抛异常
private void rangeCheck(int index) {
if (index >= size) // 防止index在size与elementDate.length之间
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 返回索引位置元素
E elementData(int index) {
return (E) elementData[index];
}
public boolean remove(Object o):(删除指定元素)
// 通过遍历数组删除指定元素
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;
}
// 为什么叫fastRemove?因为不需要再做检查,后面与remove相同
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
}
public void trimToSize():
// 将当前列表大小修改为当前元素size大小,释放被占用的空间
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size); // 复制size个元素,即数组大小变成size
}
}
public int size() 和 public boolean isEmpty():
public int size() {
return size; // 直接返回size
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o):
// 是否包含指定元素,
public boolean contains(Object o) {
return indexOf(o) >= 0; // indexOf下面介绍
}
public int indexOf(Object o) 和 public int lastIndexOf(Object o):
/**
* 一个从前向后遍历,一个从后向前遍历
*/
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 int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public Object clone():
// 为浅拷贝,不会拷贝数组内元素,两个列表引用相同的元素
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) { // 实现了Cloneable就不会出现
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
public Object[] toArray():
// 返回一个复制的数组,大小为size,而不是elementData.length,含有elementData中所有元素
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a):
// 传入一个指定类型的数组
public <T> T[] toArray(T[] a) {
if (a.length < size) // 如果a长度小于size,那么直接复制elementData,大小为size
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 否则从a的0索引开始复制,而且a[size]会被设置为null !!!!!
// 如果你的数组很重要,那就小心点这个方法
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
public void clear():
// 清空当前列表,但是已经申请的空间大小(elementData.length)不会变
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
public void ensureCapacity(int minCapacity):
// 保证当前列表至少有minCapacity的大小
public void ensureCapacity(int minCapacity) {
// minExpand为0或为10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
protected void removeRange(int fromIndex, int toIndex):
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex; // 要移动的元素数量
// 将从toIndex开始,共numMoved个元素移动到fromIndex的位置
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
// 移除范围内元素后新的size大小
int newSize = size - (toIndex-fromIndex);
// 将复制的多余的数组空间设置为空,使gc可以回收,防止内存泄漏
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
public boolean removeAll(Collection<?> c) 和 public boolean retainAll(Collection<?> c):
// 删除所有与c中任一对象相同的对象,从下面到contains我们能知道是调用equals比较
public boolean removeAll(Collection<?> c) {
// 判断是否为空,为空抛出空指针
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// 保留所有与c中任一对象相同的对象
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
// 批量删除,不建议使用,contains每次都要遍历,效率低下
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// contains每次都要遍历
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// finally语句块,即使contains抛出异常也会执行
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
public List<E> subList(int fromIndex, int toIndex):
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size); // 常规的判断,见下
return new SubList(this, 0, fromIndex, toIndex); // 内部类SubList,后面介绍
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
下面看看内部类SubList
private class SubList extends AbstractList<E> implements RandomAccess
除了是private没什么特别的
// 接着是域和构造函数,传入的list作为parent引用的对象
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex; // 截取的新列表的元素数量
this.modCount = ArrayList.this.modCount;
}
可以看到sublist的所有状态都是与传入的parent相关的;
如果你看了sublist的源码的话,你会发现它操作的就是parent的elementData数组;
只是每个方法添加了个offset而已,方法内容都是一样的,这里就不再重复了;
ArrayList的迭代器有2种;分别是Itr和ListItr;
private class Itr implements Iterator<E>
private class ListItr extends Itr implements ListIterator<E>
List比Itr多了操作对象的方法(例如add,set,previous等等);
下面是调用迭代器的方法:
// ListIterator支持从指定索引开始迭代
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public Iterator<E> iterator() {
return new Itr();
}
多看集合容器源码对于我们理解和使用容器是很有好处的,而且可以更好的在编写并发代码
并发处理一定要良好的运用各个集合容器,以及扩展的concurrent下的线程安全容器(并非一定安全)
如果仅仅使用像vector一样的全部方法synchronized的集合的话,那么效率会非常低;
跑题了,希望能够一起进步吧...
分享到:
相关推荐
在了解ArrayList的源码分析时,我们主要探讨其在Java Development Kit (JDK) 1.8中的实现。ArrayList是一个非常重要的集合框架,用于动态数组的实现,其功能类似于数组,但可以在运行时动态调整大小。它是一个非线程...
通过分析Java 1.8源码,开发者可以深入学习类库的设计模式,理解内部算法,以及如何更高效地利用Java API。例如,源码可以帮助你了解Collections框架的实现细节,或者如何利用反射来动态操作类和对象。此外,源码还...
7. **I/O流**:`java.io`和`java.nio`包提供了丰富的输入/输出流接口和类,源码分析有助于理解文件操作、网络通信等底层逻辑。 8. **异常处理**:`java.lang.Throwable`及其子类的源码揭示了异常的创建、传播和捕获...
《硬核ArrayList源码分析——深入理解Java集合框架》 ArrayList是Java集合框架中的一个重要组成部分,它是基于动态数组实现的列表。在Java 1.8版本中,ArrayList的实现细节和内部工作原理对于理解其性能和行为至关...
Java源码分析可以从以下几个方面进行: 1. **基础类库解析**:JDK 1.8源码中包含了大量Java基础类库,如`java.lang`、`java.util`、`java.io`等。这些类库提供了大量的工具类和接口,如`String`、`ArrayList`、`...
源码分析是深入理解Java平台工作原理的关键,对于开发者来说,能够查看和学习JDK的源代码是提升技能的重要途径。在这个压缩包中,包含了一些主要的Java核心库的源代码,如`com`, `org`, `launcher`, `java`, 和 `...
缓慢更新一些个人学习java相关源码过程中的笔记,在这里你将不可避免地看到以下情况: 个别不懂/没想好的地方留空待补全 限于个人水平出现的解读错误 编辑错误 排版不统一 如发现有错,欢迎指正! 如果对你有用,...
《Java2全方位学习》源码是一份非常宝贵的...通过学习和分析《Java2全方位学习》的源码,不仅可以加深对Java语言的理解,还能提升实际编程技能。每个知识点都可以作为深入研究的起点,引领你逐步成为Java开发的专家。
Java 1.8源码是Java开发者深入理解Java平台核心机制的重要参考资料,它揭示了Java标准库中的类和方法的工作原理。在这个版本1.8.0_241中,我们可以深入探究Java语言的实现细节,包括其核心类库、垃圾收集器、并发...
JDK1.8的源码分析对于深入理解Java语言的运行机制至关重要。通过阅读`src.zip`中的源代码,开发者可以洞察到类的内部实现,如`ArrayList`的扩容策略,`StringBuilder`的拼接原理,以及`HashMap`的冲突解决方式等。这...
此外,源码分析也是Java面试中常见的题目,因此熟悉这些基本数据结构的实现对于找工作非常有利。 项目环境配置方面,使用了Java 1.8,这是目前广泛使用的版本,具备良好的向下兼容性和稳定性。Maven 3.6作为构建...
Java官方英文版源码是Java 1.8版本的原始代码,这些源代码提供了Java平台标准版(Java SE)的核心库。对于任何Java开发者来说,深入理解这些源码都是提升技术水平的重要步骤,它能帮助我们了解Java语言底层的工作...
Java JDK 1.8.121 源码分析 Java Development Kit(JDK)是Java编程语言的核心组件,它包含编译器、运行时环境、调试工具和其他必要的工具,使得开发者能够编写、测试和运行Java应用程序。JDK 1.8.121是Java 8的一...
**JDK 1.8 源码详解** JDK(Java Development Kit)是Java编程语言的核心组件,它包含了编译器、运行时环境、工具集合以及...同时,源码分析也有助于学习Java编程的最佳实践和设计模式,对于提升专业技能大有裨益。
Java集合框架是Java编程语言中非常重要的组成部分,它为Java开发者提供了大量用于存储数据的结构。Java集合框架主要包括两大类,单列集合和双列集合。单列集合中,Set接口的集合主要用于存储不重复的元素,而List...
在源码分析中,我们需要关注以下关键点: 1. **接口与实现类的关系**:理解`Collection`接口如何通过不同的实现类(如`ArrayList`、`LinkedList`等)来满足不同场景的需求。 2. **数据结构**:了解数组、链表、哈希...
Java集合框架是Java编程中非常重要的部分,它提供了一种高效、灵活的数据组织方式。本文主要探讨了几个关键...通过对源码的深入分析,我们可以更好地掌握Java集合框架的工作原理,并根据实际需求选择最适合的数据结构。
源码分析 : ArrayList 源码+扩容机制分析 HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) ...
源码分析能够帮助开发者提升编程技能,优化代码性能,并了解 Java 核心库的工作方式。 在 JDK 1.8.0 源码中,我们可以看到诸如 `java`, `javax`, `sun` 等核心包的实现。这些包包含了 Java 语言的核心类,如 `java....