JDK源码阅读-ArrayList
2021/6/29 20:50:43
本文主要是介绍JDK源码阅读-ArrayList,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
注释版本JDK代码地址:https://gitee.com/bingbinggo/jdk-source-learn.git
ArrayList总结
- 底层数组实现,使用默认构造方法初始化出来的容量是10
- 扩容的长度是在原长度基础上加二分之一
- 实现了RandomAccess接口,底层又是数组,get读取元素性能很好
- 线程不安全,所有的方法均不是同步方法也没有加锁,因此多线程下慎用
- 顺序添加很方便
- 删除和插入需要复制数组 性能很差(可以使用LinkindList)
1 类定义
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList实际上是一个动态数组,容量可以动态的增长,其继承了AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
RandomAccess接口,被List实现之后,表明List提供了随机访问功能,也就是通过下标获取元素对象的功能。
- RandomAccess接口,标记接口,表明List提供了随机访问功能,也就是通过下标获取元素对象的功能。之所以是标记接口,是该类本来就具有某项能力,使用接口对其进行标签化,便于其他的类对其进行识别(instanceof)。
- ArrayList数组实现,本身就有通过下标随机访问任意元素的功能。那么需要细节上注意的就是随机下标访问和顺序下标访问(LinkedList)的不同了。也就是为什么LinkedList最好不要使用循环遍历,而是用迭代器遍历的原因。
- 实现RandomAccess同时意味着一些算法可以通过类型判断进行一些针对性优化,例子有Collections的shuffle方法,源代码就不粘贴了,简单说就是,如果实现RandomAccess接口就下标遍历,反之迭代器遍历 实现了Cloneable, java.io.Serializable意味着可以被克隆和序列化。
Java中的遍历(遍历集合或数组的几种方式)
2 初始化
创建一个ArrayList对象
ArrayList<String> list = new ArrayList<>();
源码:
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
多次new出来的新对象,都执行同一个引用。
3 重要方法
方法一:Add方法
/** * 在数组末尾添加元素 * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
1 扩容检查
2 将来元素赋值到数组[size]的地方
3 size+1
看下扩容检查及扩容源码:
/** * 扩容检查 * @param minCapacity */ private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) // 数组已满 grow(minCapacity); } /** * 数组扩容 * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //oldCapacity>>1 表示将oldCapacity右移一位(位运算),相当于除2。再加上1,相当于新容量扩容1.5倍。 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拷贝到一个新的容量中 elementData = Arrays.copyOf(elementData, newCapacity); }
方法二:add(int index, E element)在指定位置添加元素
这个方法可以看到在数组中间位置添加元素,要把该位置后面的元素都移动一次,成本开销还是挺大的。
/** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { // 越界异常检测 如果越界就会抛出下标越界异常 rangeCheckForAdd(index); //扩容检查 ensureCapacityInternal(size + 1); // Increments modCount!! //将指定下标空出 具体作法就是index及其后的所有元素后移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); //将要添加元素赋值到空出来的指定下标处 elementData[index] = element; // 长度加一 size++; }
ArrayList支持两种删除元素的方式
- remove(int index) 按照下标删除 常用
- remove(Object o) 按照元素删除 会删除和参数匹配的第一个元素
下面我们看一下ArrayList的实现
方法三:remove(int index) 删除指定位置的元素
/** * 移除list中指定位置的元素 * Removes the element at the specified position in this list. * 所有后续元素左移 下标减1 * Shifts any subsequent elements to the left (subtracts one from their * indices). * 参数是要移除元素的下标 * @param index the index of the element to be removed * 返回值是被移除的元素 * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { // 检查下标是否合法 rangeCheck(index); //修改次数统计 modCount++; //获取这个下标上的值 E oldValue = elementData(index); //将该元素后面的元素前移,最后一个元素置空 //计算出需要移动的元素个数 (因为需要将后续元素左移一位 此处计算出来的是后续元素的位数) int numMoved = size - index - 1; //如果这个值大于0 说明后续有元素需要左移 是0说明被移除的对象就是最后一位元素 if (numMoved > 0) //索引index之后的所有元素左移一位 覆盖掉index位置上的元素 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 最后一个元素置为空 这样就可以被gc回收了 elementData[--size] = null; // clear to let GC do its work //返回index位置上的元素 return oldValue; }
方法四:remove(Object o) 移除特定的元素。会删除和参数匹配的第一个元素
/** * //移除特定元素 * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ public boolean remove(Object o) { //如果元素是null 遍历数组移除第一个null if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { //遍历找到第一个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 remove method that skips bounds checking and does not * return the value removed. */ 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 }
4 总结
ArrayList总结
- 底层数组实现,使用默认构造方法初始化出来的容量是10
- 扩容的长度是在原长度基础上加二分之一
- 实现了RandomAccess接口,底层又是数组,get读取元素性能很好
- 线程不安全,所有的方法均不是同步方法也没有加锁,因此多线程下慎用
- 顺序添加很方便
- 删除和插入需要复制数组 性能很差(可以使用LinkindList)
5 ArrayList面试题
1 为什么ArrayList的elementData是用transient修饰的?
transient修饰的属性意味着不会被序列化,也就是说在序列化ArrayList的时候,不序列化elementData。
为什么要这么做呢?
- 不总是满的,每次都序列化,会浪费时间和空间
- writeObject 保证序列化的时候虽然不序列化全部 但是有的元素都序列化
所以说不是不序列化 而是不全部序列化。
/** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). * * @serialData The length of the array backing the <tt>ArrayList</tt> * instance is emitted (int), followed by all of its elements * (each an <tt>Object</tt>) in the proper order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
2 ArrayList和Vector的区别
标准答案
- 是线程不安全的,Vector是线程安全的
- ArrayList扩0.5倍,Vector扩1倍
那么问题来了
ArrayList有没有办法线程安全?
Collections工具类有一个synchronizedList方法
可以把list变为线程安全的集合,但是意义不大,因为可以使用Vector
Vector为什么是线程安全的?
Vector的关键方法都使用了synchronized修饰。
参考文章:https://juejin.cn/post/6844903550129012743,https://juejin.cn/post/6863108420552261646
这篇关于JDK源码阅读-ArrayList的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求