文档章节

01.Java 集合 - ArrayList

夕阳晒裤衩
 夕阳晒裤衩
发布于 2017/02/23 23:04
字数 2258
阅读 18
收藏 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 的所有操作都是非线程安全的。

© 著作权归作者所有

共有 人打赏支持
夕阳晒裤衩
粉丝 4
博文 15
码字总数 18485
作品 0
天津
程序员
返回某集合的所有子集

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

一贱书生
2016/11/22
4
0
day17 java 语言中的---list集合

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

孤独一夜
2017/10/22
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去除List中重复的元素

java去除List中重复的元素 如果用Set ,倘若list里边的元素不是基本数据类型而是对象, 那么请覆写Object的boolean equals(Object obj) 和int hashCode()方法. return new ArrayList(new Hash...

as007012012
2017/05/04
0
0
Java基础复习-----集合Vector

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

baibuxiha
2016/03/23
26
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

c语言之内存分配笔记

先看一个数组: short array[5] = {1,2} // 这儿定义的一个int类型的数组,数组第1和第2个元素值是1和2.其余后面默认会给值为0; 或者 short array[] = {1,2};//这儿数组第1和第2个元素,数组...

DannyCoder
今天
2
0
Shell | linux安装包不用选择Y/N的方法

apt-get install -y packageOR echo "y" | sudo apt-get install package

云迹
今天
2
0
Hadoop的大数据生态圈

基于Hadoop的大数据的产品圈 大数据产品的一句话概括 Apache Hadoop: 是Apache开源组织的一个分布式计算开源框架,提供了一个分布式文件系统子项目(HDFS)和支持MapReduce分布式计算的软件架...

zimingforever
今天
5
0
八大包装类型的equals方法

先看其中一个源码 结论:八大包装类型的equals方法都是先判断类型是否相同,不相同则是false,相同则判断值是否相等 注意:包装类型不能直接用==来等值比较,否则编译报错,但是数值的基本类型...

xuklc
今天
2
0
NoSQL , Memcached介绍

什么是NoSQL 非关系型数据库就是NoSQL,关系型数据库代表MySQL 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很耗...

TaoXu
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部