底层是如何实现的?"/>
【Java】ArrayList 底层是如何实现的?
- ArrayList 底层基于数组实现,查询效率是非常高,增删效率非常低——错误
- ArrayList 底层基于数组实现,根据index下标查询效率非常高——正确(误区——不是查询效率比较高)
- 增——底层基于数组实现 扩容——效率低
ArrayList底层是基于数组实现的
根据index下标查询效率非常高,时间复杂度为O(1)
如果根据元素值查询 效率非常低 时间复杂度O(n)
ArrayList 新增 如果底层数组容量不够的情况下
就会触发动态扩容机制 效率非常低的
ArrayList 删除操作,将删除后面的元素向前移动一位
效率也是非常低。
package com.collection.Demo07;import java.util.ArrayList;public class Test01 {public static void main(String[] args) {/*** ArrayList 底层基于数组实现的* ArrayList 根据index 下标查询效率非常高,而不是查询效率非常高*/ArrayList<String> arrayList = new ArrayList<>();
// arrayList.get(0);//get(index)
// arrayList.set(0,"mayikt");//set(index,"值")
// Object[] objects = new Object[10];
// objects[0]="mayikt01";
// objects[1]="mayikt02";
// objects[2]="mayikt03";}/*** 时间复杂度* O(1): 基于数组的下标 index 查询 只需要查询一次,例如:Array[0]* O(n): 从头查询到尾部,例如:根据元素查询 将整个数组遍历 从头遍历到尾部*//*** ArrayList.get(index) 根据index下标查询的* 时间复杂度 O(1)* 如果 需要根据元素值查询 需要开发者 自定义* .set()也是一样,是根据index下标查询并更改的* 时间复杂度 O(1)* 如果是根据元素的值 修改 效率是非常的低的——时间复杂度 O(n)*//*** 为什么arrayList集合增加删除效率非常低* 数组——原生数组没有扩容的机制* ArrayList 最开始底层默认初始化数组的容量——10** 动态扩容如何实现的?——扩容机制 效率非常低* 当10个空间满了,想存入第11个元素时,就会动态的创建一个原来数组的1.5倍(15)的新数组* 然后将旧数组中的10个元素copy到新的数组中,之后才可以添加第11个元素** 删除效率也是非常低的?* 加入现在就10个元素,删除第2个元素* 当删除之后,后面的下标为3-9的元素整体向前移一位,* 然后将下标为9的位置置为null*/
}
底层源码实现
ArrayList<String> arrayList = new ArrayList<>();
- 数组 初始化是没有容量的
- 懒加载的形式,正真需要使用的时候才会加载,例如(arrayList.add())
package com.collection.Demo07;public class MayiktArrayList<E> {/*** 分析源码的技巧* 1. 先看构造函数,通过无参构造函数可以得出* public ArrayList() {* this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;* }* transient Object[] elementData;* 默认底层初始化了一个空数组** 2. 看方法实现* 2.1 分析add()底层实现* 2.1.1 判断是否需要扩容* 2.1.2 直接通过index赋值*/private Object[] elementData;//集合需要存放元素private int size; //默认0public MayiktArrayList() {//无参构造函数 默认初始化容量大小 10elementData = new Object[10];}public void add(E e) {//第1次存放元素——index=0//第2次存放元素——index=1//所以这里定义了变量 sizeelementData[size++] = e;}
}
下一篇文章:Vector 与 ArrayList 集合区别
更多推荐
【Java】ArrayList 底层是如何实现的?
发布评论