咕泡P6:Java互联网高级架构师4期

mb61d56cf64b47d 2022-01-15 02:55:50 阅读数:45

java 编程语言 数组 数据

咕泡P6:Java互联网高级架构师4期

ArrayList源码剖析

1. 简介

  • ArrayList是List接口的完成类,是开发中运用比拟多的汇合工具类,寄存于java.util包下
  • ArrayList常用于寄存一系列数据类型相同的数据集
  • 2. 底层数据构造
  • ArrayList底层数据构造是一个​​数组​​(Object[] elementData),默许初始大小为10(是在第一次add时初始化数组容量的)​ ​download​
  • 3. 关键办法

3.1 结构

  • ​默许无参结构​​,在默许无参结构器中并未将容量赋值为默许初始容量10,而是将数组指向一个空数组,将数组容量的申请延后到第一次add中(下面add办法会剖析)
/** 默许结构 */
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个常量空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 传入初始容量值​​initialCapacity的结构器​​,传入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);
}
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 传入另一个Collection接口的完成汇合类(List、Set等)的结构器
// 传入另一个Collection接口的完成汇合类(List、Set等)的结构器
// 实质上是数组的Arrays.copy操作
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;
}
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.

3.2 add

  • add添加元素触及到数组elementData的扩容判别,modCount++(主要用于迭代时判别能否有被修正而抛异常)
  • 数组的赋值,存储元素的大小size++
// 添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 接着看确认容量的函数ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 实质上调用的是ensureExplicitCapacity办法,参数为calculateCapacity办法的返回值
// 用于计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 当elementData还是空数组即第一次add时,将容量置为默许初始容量10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则容量为size+1
return minCapacity;
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
// 用于扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 主要用于迭代时判别能否有被修正而抛异常
// overflow-conscious code
// 这里只会第一次和后面size超越数组自身容量才会扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 接着看实质上调用的扩容办法grow,每次扩容都是之前容量的1.5倍
// 扩容,初次为10、后面为之前的1.5倍
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 初始时elementData为空数组,这里为0
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为1.5倍
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);
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.

3.3 remove(int index)

  • 删除指定位置index,实质上是System.arraycopy复制,相当于移位​ ​download​
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.

3.4 remove(E element)

  • 删除指定元素(当有多个,只会移除最前面的一个)
// 遍历,找出相等的第一个元素运用fastRemove移除
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;
}
// 跟remove(index)大致相同,只是少了rangeCheck和返回值(毕竟不需求)
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
}
复制代码
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
4. 总结
  • 1.
  • ArrayList寄存于java.util包下是List接口(Coolection的子接口)的完成类
  • 用于寄存一系列相同类型的汇合数据
  • 底层数据构造是一个​​数组​​,会在第一次​​add时将10作为默许初始容量​​,每次​​扩容是之前的1.5倍​​并运用System.arraycopy将元素复制到扩容后的数组
  • 运用数组作为底层数据构造,故很容易保证元素​​存储的有序性​
  • 由于办法都是非同步办法,故​​无法保证线程平安​

 ​download​

版权声明:本文为[mb61d56cf64b47d]所创,转载请带上原文链接,感谢。 https://blog.51cto.com/u_15483878/4928977