数组列表扩展机制
写在前面
数据在面试中基本上是经常被问到的，但是基本上都是用在一般的开发中，没有注意如何实现。
在数据结构中，链表是一种线性存储结构，也称为线性表。
概念：线性表是数据结构中的数据存储结构，数据元素之间存在“一对一”的逻辑关系。可以理解为把所有数据用一根线串起来，在存储到物理空间中.
顺序表ArrayList
概念：将数据依次存储在连续的整个物理空间中。这种存储结构称为顺序存储结构(简称顺序表)。用类似下图的线将它们连接起来，形成一个线性结构。
ArrayList就是属于这样的一种。
ArrayList是基于数组实现的，数组是最简单的数据结构。使用时，必须调整大小。在日常开发中，我们经常不知道分配给数组的空间有多少。阵列空间分配多了，内存浪费，分配少了，装不下。虽然数组列表在使用时可以添加多个元素，但是不需要指定大小，因为数组列表是动态扩展的。
类的继承关系
源码分析
类的属性
/**
*默认初始容量
*/
私有静态最终int DEFAULT _ CAPACITY=10
/**
*数组列表实际数据存储的数组
*存储数组列表元素的数组缓冲区。数组列表的容量是这个数组缓冲区的长度。
*添加第一个元素时，任何element data==DEFAULT CAPACITY _ empty _ element data的空数组列表都将扩展为DEFAULT_CAPACITY。
*/
瞬态对象[]元素数据；
/**
*共享空数组实例，用于默认大小的空实例。
*/
私有静态最终对象[]DEFAULTCAPACITY _ EMPTY _ element data={ }；
/**
* element data的大小
*/
私有int大小；
类的构造函数
public ArrayList(){ 0
this . element data=DEFAULT capacity _ EMPTY _ element data；
}
new ArrayList()做了什么
公共类TestClient {
公共静态void main(String[]args){ 0
listString list=new ArrayList()；
整数容量=getCapacity(列表)；
System.out.println('不添加元素的容量：' capacity ')；
System.out.println('不添加元素的大小：' list . size())；
list . add(' add element ')；
capacity=getCapacity(列表)；
System.out.println('添加1个元素时的容量：' capacity ')；
System.out.println('添加1个元素时的大小：' list . size())；
}
/**
*通过思考获得列表的容量
*
* @param列表
* @返回
*/
公共静态整数getCapacity(列表字符串列表){ 0
整数长度=null
class c=list . GetClass()；
f场；
尝试{
f=c . getdeclaredfield(' element data ')；
f . setaccessable(true)；
Object[]o=(Object[])f . get(list)；
长度=o.length
} catch(NoSuchFieldException e){ 0
e . printstacktrace()；
} catch(Illegalaccessexception e){ 0
e . printstacktrace()；
}
返回透镜
gth;
}
}
打印结果
没添加元素时的容量：0
没添加元素时的大小：0
添加1个元素时的容量：10
添加1个元素时的大小：1
因此，当new ArrayList()时，默认会有一个空的Object空数组，在没有添加有元素的时候，其初始化容量是0，只有当添加第一个元素的时候，容量才会设置成10。
基本方法
添加元素add(E e)
/**
* 将指定的元素追加到此列表的末尾
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
//直接赋值
elementData[size++] = e;
return true;
}
add(int index, E element)
在指定索引位置添加元素
String[] elementData = {"1", "2", "3", "4", "5", "6", "7", "8"};
int index = 4;
//从下标为4的位置开始复制，复制的长度为8-4=4(复制"5", "6", "7", "8")，从下标为4+1=5的位置开始替换为"5", "6", "7", "8"
System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);
ArrayList 扩容机制
ensureExplicitCapacity(int minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果其元素数量大于其容量，则进行扩容
if (minCapacity - elementData.length 0)
grow(minCapacity);
}
grow(int minCapacity)
/**
* 扩容
* @param minCapacity
*/
private void grow(int minCapacity) {
//原来的容量
int oldCapacity = elementData.length;
//新的容量 通过位运算右移一位 如，默认为10 101=5 右移过程：10的二进制为 1010 右移1位-0101 转十进制-5
//可以理解为oldCapacity 1 == oldCapacity/2 再加上原来的长度就扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity 1);
if (newCapacity - minCapacity 0)
newCapacity = minCapacity;
//如果大于ArrayList 可以容许的最大容量，则设置为最大容量
if (newCapacity - MAX_ARRAY_SIZE 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
想了解位运算的可以看看这篇文章
Java中的位运算
ArrayList 的内部实现，其实是用一个对象数组进行存放具体的值，然后用一种扩容的机制，进行数组的动态增长。
其扩容机制可以理解为，如果元素的个数，大于其容量，则把其容量扩展为原来容量的1.5倍。
拓展延伸
- ArrayList的大小是如何自动增加的
- 什么情况下你会使用ArrayList
- 在索引中ArrayList的增加或者删除某个对象的运行过程效率很低吗解释一下为什么
- ArrayList如何顺序删除节点
- ArrayList的遍历方法
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/116873.html