前置知识:
数组
baseAddress:数组的首地址
dataTypeSize:数组中元素类型的大小,如int为4字节
为什么数组索引从0开始,假如从1开始不行吗?
在根据数组索引获取元素的时候,会用索引和寻址公式来计算内存所对应的元素数据,寻址公式是:数组的首地址+索引*存储数据的类型大小
这样对于CPU来说,增加了一个减法指令,影响性能
时间复杂度
随机查找(通过下标)时间复杂度O(1)
查找元素(未知下标)时间复杂度O(n)
查找元素(未知下标但排序)通过二分查找的时间复杂度O(logn)
插入元素和删除元素的时候,为了保证数组的内存连续性,需要挪动数组元素,平均时间复杂度为O(n)
ArrayList
源码分析【jdk8】
elementData 为数组,我们所有的操作都在该数组上
无参构造的时候调用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
有参构造的时候调用的是EMPTY_ELEMENTDATA
以上两个集合虽然都为空集合,但是在后续判断的时候用来做区分【下面有代码】
区分我这个集合是通过有参(大小为0)创建的还是无参创建的,如果是无参的,那么我第一次计划会和default_capacity(10)进行比较,如果是有参的,则直接返回size+1
第一次添加数据的时候,即假设我们是通过无参构造生成的ArrayList【数组容量为0,因为空数组,size为0】,然后往里面第一次加数据的时候,会先去调用ensureCapacityInternal方法,将成员变量elementData和minCapacity传进去,因为elementData是通过无参构造器(赋的值),所以此时elementData == defaultCapacity_EMPTY_elmentdata,所以判断,如果size+1比10(默认的)小,则计划容量为10,否则计划至size+1。计划完成之后,还需要确保容量是否够,调用ensureExplicitCapacity,够用则不会扩容,正常情况下1-10次add都不会扩容,第十一次的时候,每次扩容为原来的1.5(接近)倍(增加原来的一半,如果是奇数会缺失小数部分)
ArrayList底层的实现原理:
ArrayList list = new ArrayList(10) 中list扩容了几次?
该语句中只是声明和实例了一个ArrayList,指定了容量为10,未扩容。
如何实现数组和List之间的转换?
数组转换成List:调用数组的静态方法 Arrays.asList(数组名) 【该方法转成的集合不可变】
使用JDK中java.util.Arrays工具类的asList方法
List转换成数组:使用List的toArray方法。toArray方法返回Object数组,传入类型和长度。
Arrays.asList转换List之后,如果修改了数组的内容,list会受到影响,因为它的底层集合的构造器中,把我们传入的这个集合进行了包装而已,最终它们指向的都是同一个内存地址。
toArray转数组后,如果修改了list内容,数组不会受影响,当调用toArray后,底层进行了数组的拷贝,跟原来的元素没关系(new了一个新的)
ArrayList和LinkedList区别?
底层数据结构:
ArrayList是动态数组的数据结构实现【动态是因为进行扩容,然后进行拷贝】
LinkedList是双向链表的数据结构实现
操作数据效率:
ArrayList按照下标查询的时间复杂度O(1)【内存是连续的,根据寻址公式】,LinkedList不支持下标查询
查找(未知索引):ArrayList需要遍历,链表也需要遍历,时间复杂度都是O(n)
新增和删除
ArrayList尾部插入和删除,时间复杂度未O(1);其他部分增删需要挪动数组,时间复杂度为O(n)
LinkedList头尾接待你增删时间复杂度是O(1)【双向链表】,其他都需要遍历链表,时间复杂度O(n)
内存空间占用
ArrayList底层是数组,内存连续,节省内存
LinkedList是双向链表需要存储数据和两个指针,更占用内存
线程安全
ArrayList和LinkedList都不是线程安全的
如果需要保证线程安全,有两种方案
1.在方法内使用,局部遍历是线程安全的
2.使用线程安全的ArrayList和LinkedList【使用Collections下的synchroniedList封装】当然性能会低