什么是数组？
数组是一种数据结构，用于存储一组类型相同的数据
特点
- 数组也是对象，存储在堆中，变量通过引用地址访问数组
- 数组在内存中的地址是相邻的，内存为数组分配一段连续的空间存储数据
- 数组的大小是不可变的，创建数组的时候指定了大小，后续就不能更改
- 基本类型的数组，分配空间的默认值是基本数据类型的默认值，引用类型的默认值是 null
- String[] str = { } 只是创建了一个空数组对象，没有指定数组大小，所以不会分配数据空间，堆中存储的只是空的数组对象。后续赋值运行时会报下标过界的异常
public static void main( String[] args ) {
String[] str = { };
str[0] = "a"; //java.lang.ArrayIndexOutOfBoundsException
System.out.println( str[0] );
String[] str1 = new String[3];
System.out.println( JSONUtil.toJsonStr( str1 ) ); // []
str1[2] = "a";
System.out.println( JSONUtil.toJsonStr( str1 ) ); //["a"]
System.out.println( str1[0] ); //null
System.out.println( str1[1] ); //null
System.out.println( str1[2] ); //"a"
int[] int0 = { 1, 2, 3 };
System.out.println( int0[1] ); //2
int[] int1 = new int[3];
int1[2] = 3;
System.out.println( JSONUtil.toJsonStr( int1 ) ); //[0,0,3]
}为什么有了数组还需要Java集合？
-
数组定长不可变，集合可以自动扩容
-
支持泛型，提高了类型的安全性和代码的可读性
-
提供了丰富的操作接口，极大的简化了对数据的操作
-
集合能更高效的处理复杂的数据
ArrayList
基于动态数组实现的集合类
特点
- 动态扩容：数组容量不够了会自动扩容
- 随机访问：可以通过数组下标(索引)快速访问元素(数据)
- 允许null元素：可以存入null值(后续获取这个元素进行后续操作会报空指针)
- 不是线程安全的
扩容机制
当list中容量不足的时候，会自动进行扩容，一般情况下是按照原数组的50%扩容
扩容的时候会创建一个新的数组，将原数组中的元素复制到新数组中
//扩容：minCapacity：扩容的最小容量 newCapacity：按照原有的容量扩容50%
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果是空数组扩容，在默认的10和minCapacity之间选个大的
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
//扩容50%后的容量比MAX_ARRAY_SIZE小，就选择扩容newCapacity大小，
//否则按照hugeCapacity方法中规则扩容
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}数组在扩容的时候，要创建新的数组并且复制数据，时间复杂度为O(n)，要避免频繁扩容
常用方法
构造方法
提供了3种构造
- 无参构造：创建默认容量为10的空数组
- 初始化容量构造：创建一个入参指定大小的空数组
- 特定集合构造：创建一个包含特定集合元素的数组
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10; //默认初始化容量
private static final Object[] EMPTY_ELEMENTDATA = {}; //入参为初始化容量的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //无参构造的空数组
transient Object[] elementData; //存储数据的数组
private int size;
//无参构造函数：创建的是初始化容量为10的空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//有参构造函数：入参为初始化容量，initialCapacity > 0，创建大小为入参的数组；
//initialCapacity == 0 创建一个空数组
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);
}
}
//入参为集合的构造函数：创建一个包含指定集合元素的数组。
//elementData 接收的是一个新数组
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
}添加元素
尾部添加元素
时间复杂度为O(1)
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow(); //下标(索引)为数组长度，扩容
elementData[s] = e;
size = s + 1;
}
//在list尾部添加元素
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}指定位置添加元素
时间复杂度为O(n)，添加位置后的元素都要后移
//指定索引位(下标)添加元素
public void add(int index, E element) {
rangeCheckForAdd(index); //检查索引是否超过数组长度，超过抛出IndexOutOfBoundsException异常
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow(); //数组实际元素个数等于数据长度，扩容
System.arraycopy(elementData, index,
elementData, index + 1,
s - index); //添加索引位后元素后移
elementData[index] = element; //设置值
size = s + 1;
}list中添加集合元素
//向list中添加指定集合元素
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
//如果加入的Collection长度大于elementData剩余容量，扩容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
//拷贝数据
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}删除元素
删除指定索引位元素
删除尾部，时间复杂度为O(1)；删除其他位置，时间复杂度为O(n)
//删除指定索引位元素
public E remove(int index) {
Objects.checkIndex(index, size); //检查索引位是否越界
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
//数组数据复制(删除索引位之后的数据前移)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}删除指定元素
循环遍历数组找到指定元素，再删除元素，时间复杂度为O(n)
//删除指定元素：如果被删除的元素是 null 值，循环判断es[i] == null；
//如果元素不是 null 值，循环判断 o.equals(es[i])
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
//删除元素
fastRemove(es, i);
return true;
}获取元素
时间复杂度为O(1)
//获取指定索引位元素
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}删除所有元素
public void clear() {
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
