Java基础之ArrayList类
一、ArrayList
ArrayList继承了AbstractList分别实现了List、RandomAccess(随机访问)、Cloneable(可被克隆(复制的意思))、
Serializable(可序列化)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
1.1、RandomAccess(随机访问)
该接口是List实现来指示它们支持快速(通常是固定时间)随机访问。主这个接口的目的是允许通用算法改变它们行为提供良好的性能时,适用于随机或顺序访问列表。
操作随机访问列表的最佳算法
(如 ArrayList),
应用于可产生二次行为顺序访问列表(如LinkedList)。
通用的列表建议使用算法检查给定列表是否为
instanceof这个接口之前,应用的算法会
如果应用于顺序访问列表,则性能较差,
并在必要时改变他们的行为,以确保他们的行为是可接受的
性能。
例子:
若是列表很大时,某些List实现提供渐进的线性访问时间,但实际上的访问时间是固定的。这样的List实现通常应该实现此接口。实际经验证明,如果是下列情况,则
List实现
对于类的典型实例,这个循环:
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
运行速度比这个循环快:
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
1.2实现Cloneable接口的作用
类实现了Cloneable接口,以向Object.clone()方法表明,该方法对该类的实例进行字段对字段的复制是合法的。
没实现Cloneable接口的实例上调用Object(对象)的clone(克隆)方法将导致抛出异常CloneNotSupportedException。
按照惯例,实现此接口的类应该使用公共方法重写对象Object.clone(它是受保护的)。有关覆盖此方法的详细信息,请参阅java.lang.Object.clone()。
请注意,此接口不包含clone(克隆)方法。因此,仅凭对象实现此接口这一事实是不可能clone(克隆)对象的。即使反射性地调用clone(克隆)方法,也不能保证它会成功。
1.3实现Serializable接口的作用:
类的可序列化性是由实现java.io的类来启用的。Serializable接口。不实现此接口的类将不会对其任何状态进行序列化或反序列化。可序列化类的所有子类型本身都是可序列化的。序列化接口没有方法或字段,仅用于标识可序列化的语义。
2.ArrayList.class
2.1 ArrayList成员变量
/**
* 声明serialVersionUID的值,确保serialVersionUID值跨不同JAVA编译器实现的一致性(版本的兼容性)。
* 强烈建议使用Private修饰符显示声明serialVersionUID
* serialVersionUID字段作为继承成员没有用处
*/
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量。(ArrayList底层是数组结构)
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例。(当指定数组的容量为0时使用这个常量赋值)
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小的空实例的共享空数组实例。我们
* 将其与EMPTY_ELEMENTDATA区分开来,以了解何时膨胀多少
* 添加第一个元素。(默认空参构造函数时使用这个常量赋值)
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储ArrayList元素的数组缓冲区。
* ArrayList的容量是这个数组缓冲区的长度。
* 即元素数组:真正存放数据的对象数组,transient标识不被序列化
*/
transient Object[] elementData; // 非私有以简化嵌套类访问
/**
* ArrayList的大小(它包含的元素的数量)。
*/
private int size;
/**
* 分配的数组的最大值。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 修改次数
* /
protected transient int modCount = 0;
2.2 ArrayList构造方法
/**
*指定初始容量的大小。
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//在容量大于零的条件下,指定多大容量就是多大
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//没有指定容量大小,则为空数组
this.elementData = EMPTY_ELEMENTDATA;//构造一个空的List其size为DEFAULT_CAPACITY = 10的空列表。
} else {//如果指定容量大小为负责,抛出异常IllegalArgumentException
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 构造一个空的List其size为DEFAULT_CAPACITY = 10的空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 传入一个Collection初始化ArrayList
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//把给定的集合转换成Object[]数组
if ((size = elementData.length) != 0) {//判断转换成的数组不为空
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)//判断集合存的元素不是Object
elementData = Arrays.copyOf(elementData, size, Object[].class);
//复制的数组,返回副本的长度,返回副本的类→→→新的数组[]
} else {
//elementData的length为空,直接将ArrayList的数组转为空数组
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
//将ArrayList实例的容量调整为列表的当前大小。
//应用程序可以使用此操作最小化ArrayList实例的存储。
public void trimToSize() {
modCount++;//修改次数+1
if (size < elementData.length) {
//如果底层数组的length为空则置为EMPTY_ELEMENTDATA
//否则使用Arrays的方法对复制元素
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
2.3常用方法add
2.3.1add(E a)与add(int index,E element);
//将指定的元素追加到此列表的末尾。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//元素添加到此列表中
return true;
}
add调用了函数→ensureCapacityInternal(int size)代码如下:
private void ensureCapacityInternal(int minCapacity) {
//若当前数组是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//则比较加入的个数与默认个数(10)比较,取较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
我的理解是此函数是确认ArrayList底层数组elementData有适合的大小;
然后ensureCapacityInternal(int minCapacity)函数调用
ensureExplicitCapacity(minCapacity)代码如下:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改次数+1
// overflow-conscious code(溢出)
//判断数组真实元素个数加1后的长度与当前数组长度大小关系,
//如果小于0,返回,如果大于0,则
//调用grow(minCapacity)方法
if (minCapacity - elementData.length > 0)//数组放不下
grow(minCapacity);//扩容
}
ensureExplicitCapacity(int minCapacity)此函数调用了
grow(minCapacity)函数
/**
* 增加容量,以确保它至少可以容纳由最小容量参数指定的元素数量。
*/
private void grow(int minCapacity) {
// overflow-conscious code
//老容量
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);
// minCapacity is usually close to size, so this is a win:
//扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList动态增大主要是依赖于外汇常见问题grow(int minCapacity)方法调用
Arrays.copyOf(elementData, newCapacity);
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
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;
}
总结:
add函数的调用过程
ArrayList 内部使用数组存储元素,当数组长度不够时进行扩容,每增加自身一半的空间,ArrayList不会进行缩小容容量;
ArrayList默认初始化容量为10,底层是数组结构;
线程不安全;
Key有序,value不可重复的;
ArrayList 支持随机访问,通过索引访问元素快,时间复杂度为O(1);
ArrayList 添加元素到尾部快,平均时间复杂度为O(1);
ArrayList 添加元素到中间比较慢,因为要搬移元素,平均时间复杂度为O(n);
ArrayList 从尾部删除元素快,平均时间复杂度为O(1);
ArrayList 从中间删除元素比较慢,因为要搬移元素,平均时间复杂度为O(n);
————————————————
原文链接:https://blog.csdn.net/weixin_44903953/article/details/102880906
最新文章
- Java使用MyEclipse构建webService简单案例
- ABAP 客户报表
- Android 常用操作
- 【五】PHP数组操作函数
- VxWorks 6.9 内核编程指导之读书笔记 -- VxWorks kernel application (一)
- POJ 1166	The Clocks (爆搜 || 高斯消元)
- VC 无标题栏对话框移动(在OnLButtonDown里再次发送消息)
- web标准(复习)--6 html列表
- CSS属性值定义语法中的符号说名
- JAVA的网络编程【转】
- Python全栈开发第13天
- nginx之 nginx虚拟机配置
- Float精度丢失
- JavaScript单线程和异步机制
- 2017-10-29&mdash;英语发音的一些技巧总结
- net_device 内核中是如何组织的
- Linux下修改Mysql的用户(root)的密码的俩种方法
- oracle坏块处理记录
- phpstorm 配置 webpack @ 别名跳转
- [React] Refactor a Class Component with React hooks to a Function
热门文章
- 15.stop引发的数据不一致
- Tensorflow中的图(tf.Graph)和会话(tf.Session)详解
- PHP上传文件和下载
- permutations and combinations
- 【leetcode】576. Out of Boundary Paths
- shell 根据路径获取文件名和目录
- Python基础教程(008)--第一个Python程序
- .net文件下载的四种方法
- Oracle中使用REGEXP_SUBSTR,regexp_replace,wm_concat函数
- webstorm 分屏