文档章节

01.Java 集合 - ArrayList

oxf
 oxf
发布于 2017/02/23 23:04
字数 2258
阅读 25
收藏 1

##基本概念

在分析 ArrayList 前,需要明白几个词的概念:线性表、数组。

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表有两种存储方式:

  • 一种是顺序存储结构
  • 另一种是链式存储结构

数组,是一种典型的顺序存储结构。具有以下特点:

  • 是物理存储连续、逻辑存储连续的顺序表。

  • 利于查询。这种存储方式的优点是查询的时间复杂度为O(1),通过首地址和偏移量就可以直接访问到某元素。

  • 不利于修改。插入和删除的时间复杂度最坏能达到O(n),如果你在第一个位置插入一个元素,你需要把数组的每一个元素向后移动一位,如果你在第一个位置删除一个元素,你需要把数组的每一个元素向前移动一位。

  • 容量的固定性。就是当你不确定元素的数量时,你开的数组必须保证能够放下元素最大数量,遗憾的是如果实际数量比最大数量少很多时,你开的数组没有用到的内存就只能浪费掉了。


原理分析

以下源码均来自 JDK 1.7。

###1.内部结构

首先来介绍 ArrayList 的两个重要成员变量

// 内部数组,用 transient 关键字修饰,表示该变量不会被序列化
private transient Object[] elementData;

// 数组中的元素个数
private int size;

通过这两个成员变量,可以猜测 ArrayList 内部是通过数组来储存元素的。再来看看它是怎么被创建的。

// 构造函数
public ArrayList() {
    this(10);
}

// 构造函数
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0) {
        // 抛出异常...
    }

	// 关键 -> 创建指定固定大小的数组
    this.elementData = new Object[initialCapacity];
}

从代码可以看出,在创建 ArrayList 时如果不指定其容量,那么默认就会创建一个固定大小为 10 的数组。若指定了容量则会创建指定大小的数组。


###2.扩容检测

数组有个明显的特点就是它的容量是固定不变的,一旦数组被创建则容量则无法改变。所以在往数组中添加指定元素前,首先要考虑的就是其容量是否饱和。

若接下来的添加操作会时数组中的元素超过其容量,则必须对其进行扩容操作。受限于数组容量固定不变的特性,扩容的本质其实就是创建一个容量更大的新数组,再将旧数组的元素复制到新数组当中去。

这里以 ArrayList 的 添加操作为例,来看下 ArrayList 内部数组扩容的过程。

public boolean add(E e) {
	// 关键 -> 添加之前,校验容量
	ensureCapacityInternal(size + 1); 
	
	// 修改 size,并在数组末尾添加指定元素
	elementData[size++] = e;
	return true;
}

可以发现 ArrayList 在进行添加操作前,会检验内部数组容量并选择性地进行数组扩容。在 ArrayList 中,通过私有方法 ensureCapacityInternal 来进行数组的扩容操作。下面来看具体的实现过程:

  • 扩容操作的第一步会去判断当前 ArrayList 内部数组是否为空,为空则将最小容量 minCapacity 设置为 10。
// 内部数组的默认容量
private static final int DEFAULT_CAPACITY = 10;

// 空的内部数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 关键 -> minCapacity = seize+1,即表示执行完添加操作后,数组中的元素个数 
private void ensureCapacityInternal(int minCapacity) {
	// 判断内部数组是否为空
	if (elementData == EMPTY_ELEMENTDATA) {
		// 设置数组最小容量(>=10)
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}
  • 接着判断添加操作会不会导致内部数组的容量饱和。
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	
	// 判断结果为 true,则表示接下来的添加操作会导致元素数量超出数组容量
	if (minCapacity - elementData.length > 0){
		// 真正的扩容操作
		grow(minCapacity);
	}
}
  • 数组容量不足,则进行扩容操作,关键的地方有两个:扩容公式、通过从旧数组复制元素到新数组完成扩容操作。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
	
	int oldCapacity = elementData.length;
	
	// 关键-> 容量扩充公式
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	
	// 针对新容量的一系列判断
	if (newCapacity - minCapacity < 0){
		newCapacity = minCapacity;
	}
	if (newCapacity - MAX_ARRAY_SIZE > 0){
		newCapacity = hugeCapacity(minCapacity);
	}
		
	// 关键 -> 复制旧数组元素到新数组中去
	elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0){
		throw new OutOfMemoryError();
	}
			
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

关于 ArrayList 扩容操作,整个过程如下图:

输入图片说明


3.添加操作

通过上面的分析,可以了解到针对 ArrayList 增加改查其实本质就是操作数组

ArrayList 的添加操作,也就是往其内部数组添加元素的过程。首先要确保就是数组有足够的空间来存放元素,因此也就有了扩容检测这一步骤。

该操作可分为两种方式:指定位置(添加到数组指定位置)、不指定位置(添加到数组末尾)

  • 不指定位置时,则默认将新元素存放到数组的末尾位置。过程相对简单,这里不再分析。

  • 指定位置时,即将新元素存在到数组的指定位置。若该位置不是数组末尾(即该位置后面还存有元素),则需要将该位置及之后的元素后移一位,以腾出空间来存放新元素。

public void add(int index, E element) {

	// 校验添加位置,必须在内部数组的容量范围内
	rangeCheckForAdd(index);
	
	// 扩容检测
	ensureCapacityInternal(size + 1);
	
	// 关键 -> 数组内位置为 index 到 (size-1)的元素往后移动一位,这里仍然采用数组复制实现
	System.arraycopy(elementData, index, elementData, index + 1, size - index);
	
	// 腾出新空间添加新元素
	elementData[index] = element;
	
	// 修改数组内的元素数量
	size++;
}

private void rangeCheckForAdd(int index) {
	if (index > size || index < 0){
		// 抛出异常...
	}
}

分析代码,在没有扩容操作的情况下,整个过程如下:

输入图片说明


###4.修改操作

修改操作,就是替换指定位置上的元素。原理相对简单,这里直接贴出源码。

public E set(int index, E element) {
	rangeCheck(index);
	
	E oldValue = elementData(index);
	elementData[index] = element;
	return oldValue;
}

5.删除操作

ArrayList 的删除操作同样存在两种方式:删除指定位置的元素、删除指定元素。后者相较于前者多了一个查询指定元素所处位置的过程。

删除指定位置的元素时,需判断该位置是否在数组末尾,若是则将该位置的元素置空让 GC 自动回收;若不是,则需要将该位置之后的元素前移一位,覆盖掉该元素以到达删除的效果,同时需要清空末尾位置的元素。

public E remove(int index) {
	
	rangeCheck(index);
	modCount++;
	
	// 取得该位置的元素
	E oldValue = elementData(index);

	// 判断该位置是否为数组末尾
	int numMoved = size - index - 1;

	// 若是,则将数组中位置为 idnex+1 到 size -1 元素前移一位
	if (numMoved > 0){
		System.arraycopy(elementData, index + 1, elementData, index, numMoved);
	}
		
	// 关键 -> 清空末尾元素让 GC 生效,并修改数组中的元素个数(实现的十分巧妙)
	elementData[--size] = null; 

	return oldValue;
}

E elementData(int index) {
	return (E) elementData[index];
}

分析代码,若指定位置不在数组末尾时的删除过程如下:

输入图片说明

再来看下移除指定元素的过程,与上面介绍的删除方法相比,该方法主要多了查找指定元素位置的过程,若存在该元素则删除并返回 true,否则返回 false。

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;
}

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; 
}

###5.查询操作

查询操作可分为查询指定位置的元素、查询指定元素。

  • 前者就是直接取得数组指定位置的元素。
public E get(int index) {
	rangeCheck(index);
	return elementData(index);
}
  • 同样地,后者比前者多了一步确定指定元素位置的过程,原理在删除操作时已介绍过。
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;
}

##总结

总的来说,与 LinkedList 相比,ArrayList 适用于频繁查询的场景,而不适用于频繁修改的场景; 与 Vector 相比,ArrayList 的所有操作都是非线程安全的。

© 著作权归作者所有

共有 人打赏支持
oxf

oxf

粉丝 4
博文 15
码字总数 18485
作品 0
莆田
程序员
私信 提问
返回某集合的所有子集

/** * 功能:返回某集合的所有子集。 / 三种方法: 方法一:迭代 [java] view plain copy //迭代 /* * 注意:每次加入集合后会改变原来的集合,无法继续从集合中取出元素。 * 必须通过一个中间...

一贱书生
2016/11/22
4
0
Java:Collection集合、泛型

1、Collection集合-概述 1)、集合是一个装”引用类型”的”容器” 2)、Java内部提供了很多”集合类”,每种集合类对元素的存储采用了不同的”数据结构”–集合存储数据的方式。 3)、这些数...

烟火式Java
09/13
0
0
ArrayList 源码分析 -- 扩容问题及序列化问题

目录 一、前言 二、ArrayList 的继承与实现关系 2.1 ArrayList.java 2.2 抽象类AbstractList.java 2.3 接口List.java 2.4 接口RandomAccess.java 2.5 接口Cloneable 2.6 接口Serializable 三......

niaonao
08/16
0
0
Java基础复习-----集合Vector

Vector与ArrayList差不多,只不过Vector是线程安全,这也意味着性能会比ArraList差 1、定义 与ArrayList继承、实现接口都一样 2.内部使用数组对象进行存储 使用无参构造方法初始化时,数组大...

baibuxiha
2016/03/23
26
0
day17 java 语言中的---list集合

day17 java 语言中的---List集合 一: list集合概述: 在day16中已经讲了一下具体的set集合,今天在这个基础上在说一点list集合。主要包含有“ArrayList集合”和“linkedlist集合”以及“vec...

孤独一夜
2017/10/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

EOS官方钱包keosd

EOS官方钱包的名称是keosd,它负责管理你的私钥,并且帮你进行交易的签名。 不过不幸的是,keosd钱包对普通用户并不友好,它是一个命令行程序,目前还没有像以太坊的mist那样的图形化界面,而...

汇智网教程
今天
20
0
ArrayList的实现原理以及实现线程安全

一、ArrayList概述 ArrayList是基于数组实现的,是一个动态的数字,可以自动扩容。 ArrayList不是线程安全的,效率比较高,只能用于单线程的环境中,在多线程环境中可以使用Collections.syn...

一看就喷亏的小猿
今天
20
0
Netty 备录 (一)

入职新公司不久,修修补补1个月的bug,来了点实战性的技术---基于netty即时通信 还好之前对socket有所使用及了解,入手netty应该不是很难吧,好吧,的确有点难,刚看这玩意的时候,可能都不知道哪里...

_大侠__
昨天
30
0
Django简单介绍和用户访问流程

Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。 Django是一个开放源代码的Web应用框架,由Python写成。 Django遵守BSD版权,初...

枫叶云
昨天
36
0
Spring Cloud Stream消费失败后的处理策略(四):重新入队(RabbitMQ)

应用场景 之前我们已经通过《Spring Cloud Stream消费失败后的处理策略(一):自动重试》一文介绍了Spring Cloud Stream默认的消息重试功能。本文将介绍RabbitMQ的binder提供的另外一种重试...

程序猿DD
昨天
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部