一、前言
Java 集合类提供了一套设计良好的支持对一组对象进行操作的接口和类,JAVA常用的集合接口有4类,分别是:
- Collection:代表一组对象,每一个对象都是它的子元素
- Set:不包含重复元素的 Collection
- List:有顺序的 collection,并且可以包含重复元素
- Map:可以把键(key)映射到值(value)的对象,键不能重复。
JAVA集合的类关系可以用图表示如下:
类图说明:
- 实线边框是实现类,比如:ArrayList,LinkedList,HashMap等。
- 折线边框是抽象类,比如:AbstractCollection,AbstractList,AbstractMap等。
- 点线边框的是接口,比如:Collection,Iterator,List等
- 带颜色框的是工具类,比如:Collections,Arrays。
通过类图我们知道,所有的集合都继承了Iterator接口,也就是说,所有的集合都具有迭代器,可以通过迭代器去循环,事实上,很多集合的功能都是依托于迭代器去实现的。
二、ArrayList常用方法
方法名 | 功能 |
---|---|
size() | 返回当前集合的元素个数 |
isEmpty() | 判断当前集合是否是空元素 |
contains(Object o) | 判断当前集合是否包含某个对象 |
indexOf(Object o) | 获取某个对象位于集合的索引位置 |
lastIndexOf(Object o) | 获取最后一个位于集合的索引位置 |
get(int index) | 获取指定位置的集合对象 |
set(int index, E element) | 覆盖集合某个位置的对象 |
add(E e) | 添加对象进入集合 |
add(int index, E element) | 添加对象进入集合指定位置 |
remove(int index) | 移除索引位置的元素 |
remove(Object o) | 移除某个元素 |
我们一般使用ArrayList最常用的方法无非就是添加,查询和删除。我们接下来从源码层面上分析下ArrayList是如何进行添加,查询和删除的。
ArrayList源码属性
//默认容量长度
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;
ArrayList构造方法
//指定容量构造方法
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);
}
}
//默认无参数构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//指定集合构造方法
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//官方的一个bug,c.toArray()可能不是一个object数组,所以需要通过Arrays.copyOf创建1个Object[]数组,这样数组中就可以存放任意对象了
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
通过上面ArrayList的构造方法我们知道,ArrayList可以创建指定长度的list,也可以指定一个集合创建list,而默认的创建list是一个长度为10 的空数组。
ArrayList的add()方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 确认能否装得下size+1的对象
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果是默认长度,就比较默认长度和size+1,取最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//如果容量大于数组的长度
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
//取数组的长度
int oldCapacity = elementData.length;
//计算新长度,新长度=旧长度+旧长度/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
上面源码逻辑包括了,ArrayList的添加以及扩容,根据上面源码,我们知道,原来ArrayList的实际默认容量直到调用add()方法才会真正扩容到10,这里通过new ArrayList()在内存分配的是一个空数组,并没有直接new Object[10],这样设计是很巧妙的,可以节省很多空间。
ArrayList的add(int index, E element)方法
public void add(int index, E element) {
//判断是否越界
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 重新复制数组,把index+1位置往后的对象全部后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//覆盖index位置的对象
elementData[index] = element;
size++;
}
ArrayList的指定位置添加对象方法,需要把指定位置后面的全部对象后移,所以这样也是ArrayList相对于linkList添加耗时的地方。
ArrayList的get(int index)方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
ArrayList的get(int index) 方法比较简单,只有两步,第一,检查是否越界,第二,返回数组索引位置的数据。
ArrayList的remove(int index)方法
public E remove(int index) {
rangeCheck(index);
//父类的属性,用来记录list修改的次数,后续迭代器中会用到
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//把index位置后面的元素左移
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
ArrayList 的remove(int index)方法主要分为 3步,第一步,判断下标是否越界,第二步,记录修改次数,并左移index位置后面的元素,第三,把最后位置赋值为null,用于快速垃圾回收。
ArrayList在循环中使用remove方法需要注意的问题
- for循环
List<Integer> integers = new ArrayList<>(5);
integers.add(1);
integers.add(2);
integers.add(3);
integers.add(4);
integers.add(5);
for (int i = 0; i < integers.size(); i++) {
integers.remove(i);
}
System.out.println(integers.size());
这里首先申明一个长度为5的ArrayList的集合,然后添加五个元素,最后通过循环遍历删除,理论结果输出0,但是输出的结果却是2,为什么呢?之前分析remove源码我们知道,ArrayList每删除一次就会把后面的全部元素左移,以这5个元素为例,第一个正常删除没问题,删除后,元素就只剩下[2,3,4,5],这个时候remove(1),还剩[2,4,5],再remove(2),剩下[2,4],后面再remove没有元素了,所以最后size为2。
- foreach循环
List<Integer> integers = new ArrayList<>(5);
integers.add(1);
integers.add(2);
integers.add(3);
integers.add(4);
integers.add(5);
for (Integer integer : integers) {
integers.remove(integer);
}
System.out.println(integers.size());
这段代码只是在上面的代码上面把for循环改成了foreach循环,这里理论结果也是输出0,但是最后却报错了,报错信息:
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
这里我们发现是ArrayList的迭代器方法,ArrayList$Itr说明是ArrayList的内部类Itr中checkForComodification出问题了,我查看下源码,
//这是Itr内部的属性,初始化等于ArrayList中的modCount
int expectedModCount = modCount;
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
看到这里我们应该清楚了,我们调用ArrayList的remove方法,modCount的值修改了,但是迭代器中expectedModCount值没有修改,所以就抛出异常了。这时候肯定有人说,你这个是骗人的,我写的foreach删除就不会报错!恩,对!有一种情况是不会报错的,就是list中只有两个元素时,比如这样:
List<Integer> integers = new ArrayList<>(5);
integers.add(1);
integers.add(2);
for (Integer integer : integers) {
integers.remove(integer);
}
System.out.println(integers.size());
}
这时候输出结果为1,没有报错,为什么呢?我们知道foreach是for循环的增强,内部是通过迭代器实现的,看到刚刚报错的代码也证实了我们的猜想,所以,迭代器删除,过程是这样的,先判断iterator.hasNext(),迭代器有没有下一个元素,如果有就遍历,遍历就会调用iterator.next(),该源码如下:
public boolean hasNext() {
return cursor != size;
}
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
我们查看源码发现,以上过程只有调用next()会进行 checkForComodification()
,当我们删除了第一个元素时候,进入循环判断,hasNext这个时候为false,不会调用next(),所以也就不会执行checkForComodification()
,所以就能输出1。
三、总结
- ArrayList可以指定容量实例化,也可以指定一个集合内容初始化,默认初始化长度是10(在执行add方法后才会给真正的空间),
- ArrayList指定位置添加和删除,都会改变该位置之后的元素位置。
- ArrayList在循环中进行remove时候需要注意报错和下标的问题,建议用迭代器删除是最好的
推荐阅读
今天的文章带你走进Java集合之ArrayList分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/17549.html