网站服务费一年多少钱,手机端网站尺寸规范,太原网站建设联系方式,为什么要用模板建站写在前面#xff1a; 小伙伴儿们#xff0c;大家好#xff01;上一篇我们介绍了HashMap相关知识点——了解HashMap数据结构#xff0c;超详细#xff01; 今天来学习ArrayList相关内容#xff0c;作为面试必问的知识点#xff0c;来深入了解一波#xff01; 思维导图 小伙伴儿们大家好上一篇我们介绍了HashMap相关知识点——了解HashMap数据结构超详细 今天来学习ArrayList相关内容作为面试必问的知识点来深入了解一波 思维导图 ArrayList学习图
1ArrayList底层数据结构
ArrayList就是动态数组是List接口的可调整大小的数组实现除了实现List接口之外该类还提供了一些方法来操纵内部使用的存储列表的数组大小。它的主要底层实现是数组Object[] elementData。
数组的特点大家都知道遍历查询速度快——数组在内存是连续空间可以根据地址索引的方式快速获取对应位置上的元素。但是它的增删速度慢——每次删除元素都需要更改数组长度、拷贝以及移动元素位置。 ArrayList类架构图
ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList 实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口所以ArrayList 是支持快速访问、复制、序列化的。
与ArrayList类似的是LinkedList但是LinkedList底层是链表它的数组遍历速度慢但增删速度很快。
小结
ArrayList底层是数组实现的存储查询效率高增删效率低。
2ArrayList构造方法
下面是查看API中构造方法 构造方法
2.1无参构造方法
我们看源码中的无参构造方法 无参构造使用默认的size为10的空数组在构造方法中没有对数组长度进行设置会在后续调用add方法的时候进行扩容。 无参构造
里面是一个赋值操作右边是一个空容量数组左边则是存储数据的容器以下是参照源码分析
//默认空容量数组长度为0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};//集合真正存储数据的容器
transient Object[] elementData; 2.2参数为指定初始化容量的构造方法
来看看源码中的int型构造方法 指定初始化容量构造 参数大于0elementData初始化为initialCapacity大小的数组参数等于0elementData初始化为空数组参数小于0抛出异常 2.3参数为Collection类型的构造方法
来看看构造方法的源码 Collection类型构造 将一个参数为Collection的集合转变为ArrayList(实际上就是将集合中的元素换为了数组的形式)如果传入的集合为null会抛出空指针异常。c.toArray()可能不会正确地返回一个 Object[]数组那么使用Arrays.copyof()方法。如果集合转换成数组之后数组长度为0那就直接使用自己的空成员变量初始化elementData。 总结
上面的构造方法理解起来比较简单无参构造和初始化容量构造的目的都是初始化底层数组elementData(this.elementDataXXX) 无参构造方法会将elementData初始化一个空数组插入元素时扩容将会按默认值重新初始化数组有参构造方法会将elementData初始化为参数值大小0的数组 如果在构造 ArrayList 实例时指定初始化值初始化容量或者集合那么就会创建指定大小的 Object 数组并把该数组对象的引用赋值给 elementData如果不指定初始化值在第一次添加元素值时会使用默认的容量大小 10 作为 elementData 数组的初始容量使用 Arrays.conpyOf() 方法创建一个 Object[10] 数组。
一般情况下我们用默认的构造方法即可。上面说到使用无参构造时会调用add方法并进行扩容下面来看看add方法以及扩容的细节。
3添加add()方法分析
看看ArrayList的add()添加方法 add()添加方法
3.1列表的末尾添加指定元素
public boolean add(E e)先来看看源码分析 add()源码
我们先来看第一个添加方法add(E e)具体流程如下
//将添加的数据传入给e
public boolean add(E e) { //调用方法对内部容量进行校验 ensureCapacityInternal(size 1); elementData[size] e; return true;
} 我们看到add方法中在添加元素之前会先判断size的大小所以我们来看看ensureCapacityInternal方法的细节之处
private void ensureCapacityInternal(int minCapacity) { //判断集合存数据的数组是否等于空容量的数组 if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //通过最小容量和默认容量 出较大值 (用于第一次扩容) minCapacity Math.max(DEFAULT_CAPACITY, minCapacity); } //将if中计算出来的容量传递给下一个方法,继续校验 ensureExplicitCapacity(minCapacity); } 当 要 add 进第1个元素时minCapacity为(size101)1在Math.max()方法比较后minCapacity 为10。然后紧接着调用ensureExplicitCapacity更新modCount的值并判断是否需要扩容。接下来看ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) { //实际修改集合次数 (在扩容的过程中没用,主要是用于迭代器中) modCount; //判断最小容量 - 数组长度是否大于 0 if (minCapacity - elementData.length 0) //将第一次计算出来的容量传递给 核心扩容方法 grow(minCapacity); }然后是扩容的核心**grow()**方法
private void grow(int minCapacity) { //记录数组的实际长度,此时由于木有存储元素,长度为0 int oldCapacity elementData.length; //核心扩容算法 原容量的1.5倍 int newCapacity oldCapacity (oldCapacity 1); //判断新容量-最小容量是否小于0, 如果是第一次调用add方法必然小于if (newCapacity - minCapacity 0) //还是将最小容量赋值给新容量 newCapacity minCapacity; //判断新容量-最大数组大小是否0,如果条件满足就计算出一个超大容量if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); // 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData elementData Arrays.copyOf(elementData, newCapacity);
}执行流程 3.2指定位置添加指定元素
public void add(int index, E element)先来看看源码分析
//在元素序列index位置处插入
public void add(int index, E element) {rangeCheckForAdd(index);//1检测是否需要扩容ensureCapacityInternal(size 1); // Increments modCount!!//2将index及其之后的元素都向后移一位System.arraycopy(elementData, index, elementData, index 1,size - index);// 3. 将新元素插入至 index 处elementData[index] element;size;
}
private void rangeCheckForAdd(int index) {//这里判断的indexsizeindex小于0超出指定范围就报错if (index size || index 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}我们再看看它的使用方法
import java.util.ArrayList;/*** author 公众号:程序员的时光* create 2020-11-03 17:05* description*/
public class Test03 {public static void main(String[] args) {ArrayListString listnew ArrayList();list.add(海心焰);//在index为1的位置处添加数据list.add(1,玄黄炎);System.out.println(list);}
}运行结果 结果
3.3按照指定的元素顺序将所有元素添加到此列表的尾部
public boolean addAll(Collection? extends E c);这个方法的描述是按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
简单来讲就是将一个集合的元素全部添加到另外一个集合中去。 代码
运行结果 结果
3.4将指定集合中的所有元素插入到此列表中从指定位置开始
public boolean addAll(int index, Collection? extends E c);这个方法和上面的方法都是把一个集合中的元素添加到另外一个集合中去不同的在于上面的方法是默认添加至目标集合的尾部而此方法是包含索引的也就是在指定位置开始插入元素。 代码
运行结果 结果
4其他方法分析
ArrayList包括很多方法我们来简单回顾一下。
//移除指定位置上的元素
public E remove(int index);
//移除此列表中首次出现的指定元素如果存在
boolean remove(Object o);
//修改集合元素
public E set(int index, Object o);
//查找集合元素
public E get(int index);
//清空集合所有数据
public void clear();
//判断集合是否包含指定元素
public boolean contains(Object o);
//判断集合是否为空
public boolean isEmpty()5常见面试题精华
5.1ArrayList是如何扩容的
这个请参照3.1章节的扩容步骤来看看它的核心扩容方法 grow()扩容方法
总结 扩容的大小是原先数组的1.5倍 若值newCapacity比传入值minCapacity还要小则使用传入minCapacity若newCapacity比设定的最大容量大则使用最大整数值 5.2ArrayList频繁扩容导致性能下降如何处理
比方说现在需要往数组里添加10w条数据我们来看看前后的时间变化 使用指定初始化容量的构造方法
结果是 结果 ArrayList底层是数组实现的那么每次添加数据时会不断地扩容这样的话会占内存性能低所以导致时间很长。 我们可以用ArrayList的指定初始化容量的构造方法来解决性能低的问题。 5.3ArrayList在增删元素的时候是怎么进行的还有为何很慢
在前面我们说过它有按照索引添加也有直接添加的。在这之前需要校验长度问题ensureCapacityInternal如果长度不够则需要进行扩容操作。
而前面的扩容是扩大原来的1.5倍采用位运算右移一位。 如果后面的数据量级过大在100万条数据中新增一个元素后面的元素都要拷贝以及移动位置所以说效率很低。
5.4ArrayList是线程安全的吗
ArrayList线程是不安全的。线程安全的数组容器是Vector它的原理是把所有的方法都加上synchronized。
我们来测试一下先准备一个线程任务类 然后定义测试类对任务类进行测试 我们来看结果 可以看到会报异常错误有的线程还是为null这说明ArrayList线程是不安全的。
当然可以用线程安全的集合Vector来代替ArrayList Vector集合
或者我们可以直接加synchronized关键字把不安全的线程变成安全的 加关键字synchronized
这样也是可以保证线程安全的。
为啥ArrayList线程不安全
线程不安全 线程安全就是多线程访问时采用了加锁机制当一个线程访问该类的某个数据时进行保护其他线程不能进行访问直到该线程读取完其他线程才可使用。不会出现数据不一致或者数据污染。 线程不安全就是不提供数据访问保护有可能出现多个线程先后更改数据造成所得到的数据是脏数据。 List接口下面有两个实现一个是ArrayList另外一个是Vector。从源码的角度分析因为Vector的方法前加了synchronized关键字。
ArrayList在添加一个元素时有两步来完成1. 在 Items[Size] 的位置存放此元素2. 增大 Size 的值。 在单线程运行的情况下如果 Size 0添加一个元素后此元素在位置 0而且 Size1 而如果是在 多线程情况下比如有两个线程线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素因为此时 Size 仍然等于 0注意哦我们假设的是添加一个元素是要两个步骤哦而线程A仅仅完成了步骤1所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行都增加 Size 的值。 那好我们来看看 ArrayList 的情况元素实际上只有一个存放在位置 0而 Size 却等于 2。这就是“线程不安全”了。 5.5ArrayList和LinkedList区别 底层数据结构ArrayList底层使用的是数组LinkedList底层使用的是双向链表 插入和删除元素操作ArrayList采用的是数组存储所以插入和删除元素是跟元素的位置有关系。LinkedList采用的是链表存储删除元素是不受元素位置影响的如果是要在指定位置i插入和删除的话add(int indexE element时间复杂度近似为O(n)因为需要先移动再插入。 随机访问ArrayList对于随机元素访问的效率明显比LinkedList高。随机访问就是通过元素的索引来获取元素也就是set和get(int index)方法。 线程不安全ArrayList和LinkedList都是不同步的也就是说都是线程不安全的。 接口实现ArrayList实现了RandomAccess可以支持随机元素访问而LinkedList实现了Deque可以当做队列使用 内存空间占用情况ArrayList的空间占用主要体现在list列表的末尾会有一定的容量空间它的优势在于内存的连续性CPU的内部缓存结构会缓存连续的内存片段可以大幅度降低内存的性能开销提高效率LinkedList的空间占用体现在每一个元素都需要消耗空间内存要存放前驱后继等数据。 当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能 当操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,使用LinkedList会更好。
