java源码----集合系列1----ArrayList，linkedList-Toy模板网

这篇具有很好参考价值的文章主要介绍了java源码----集合系列1----ArrayList，linkedList。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Arraylist

基础信息

底层是一个object数组

Arraylist 是java里面Collection 标准的一个集合，其底层是一个object数组。当new一个空参的ArrayList的时候，会默认生成一个空数组。

java源码----集合系列1----ArrayList，linkedList

Arraylist上限是 Integer.MAX_VALUE - 8(Integer.MAX_VALUE = 2^31-1);

超过上限会报内存溢出

java源码----集合系列1----ArrayList，linkedList

这里为什么是Integer.MAX_VALUE-8 ，源码上的解释就一句话

Some VMs reserve some header words in an array

一些虚拟机会在数组中保留一些头字。解释起来就是：

Java对象在堆内存中的存储布局可以分为三部分：对象头（object header），实例数据（Instance Data）和对齐填充（Padding）；

对象头包括

Mark Word：用于对象自身的运行时数据存储，如HashCode，GC分代年龄，锁状态标志，线程持有的锁，偏向线程ID和偏向时间戳等；
Klass Pointer：对象指向它类元数据的指针，JVM通过这个指针长度来确定对象是哪个类的实例。
数组长度（只有数组对象才有）：记录数组对象的长度。

8 bytes（Mark Word的最大占用） + 8 bytes（Klass Pointer的最大占用） + 4 bytes（数组长度）+ 8 bytes（引用指针的最大占用：数组中存放的是对象的引用） + 4 bytes（padding：为了方便寻址，JVM要求对象大小要求是8的倍数，不够就填充） ==32 bytes

而int类型 1位占4个byte， 8 int（整数）就等于32 bytes（字节），所以是Integer.MAX_VALUE-8。但在实际使用时因为考虑到虚拟机堆大小，实际arraylist大小要远远小于Integer.MAX_VALUE-8 。

ArrayList 默认长度是10，使用Arrays.copyOf()进行扩容，每次=扩容size是原size的一半 (oldCapacity + (oldCapacity >> 1));

java源码----集合系列1----ArrayList，linkedList

Arrays.copyOf()源码其实是调用了System.arraycopy

java源码----集合系列1----ArrayList，linkedList

System.arraycopy 是原生方法。

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

相当于新建了一个空数组，再用原生方法把老数组的值复制进去。从这一点可以看出ArrayList每次扩容都需要创建新的数组，并且将原数组的值复制进新的数组，新增的速度相对要慢。

查询的时候先校验是否存在数组下标越界

java源码----集合系列1----ArrayList，linkedList