ArrayList源码学习
前言
不知道大家有没有同感,看书或者看别人博客又或者看源码的时候,看的时候都觉得自己都看懂了,过了一段时间呢又都想不起来了。
以前学习的时候总认为看懂了就行了,没必要写下来,觉得网上那么多比自己写的好的多得是,看别人写的就行了。
最近在极客时间APP上看左耳朵耗子的专栏,有一段是对我比较有感触的。自己总结了有几点:第一要有总结,你可能每部分都看懂了(比如:数组扩容,检查数据是否存在数组内),但是没有从全局去思考,有可能给自己造成假象觉得自己都懂了其实只是一知半解而已。第二要写下来,写的过程就能检测自己是不是真的懂了,如果没懂是写不出来的,还有就是写的过程中能锻炼自己的语言组织能力,所有不管写的好坏都要尽力写下来。第三就是能够把学到的讲给别人听,能够真正用自己的语言讲给别人并且能让别人听得懂那么就真的掌握了这个技术点。
所以开始尝试把自己学习的东西记录下来,写的不对的地方欢迎各位指正,讨论。
下面进入正题
ArrayList源码学习
JDK版本:JDK9
ArrayList的原理其实就是维护了一个Object类型的数组,只不过内部实现了数组的扩容等一系列的操作
接下来先看下ArrayList的属性有哪些
一、属性
private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; // non-private to simplify nested class access
private int size;
1、DEFAULT_CAPACITY 默认数组容量大小 10
2、EMPTY_ELEMENTDATA , DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空的数组对象,一开始看的时候没搞懂为什么会有两个对象,看到后面才明白,这个到添加对象的时候再讲
3、elementData 这个就是我刚说的ArrayList背后维护的一个数组
4、size 数组的长度
二、构造函数
1 public ArrayList(int initialCapacity) { 2 if (initialCapacity > 0) { 3 this.elementData = new Object[initialCapacity]; 4 } else if (initialCapacity == 0) { 5 this.elementData = EMPTY_ELEMENTDATA; 6 } else { 7 throw new IllegalArgumentException("Illegal Capacity: "+ 8 initialCapacity); 9 } 10 } 11 12 /** 13 * Constructs an empty list with an initial capacity of ten. 14 */ 15 public ArrayList() { 16 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 17 } 18 19 /** 20 * Constructs a list containing the elements of the specified 21 * collection, in the order they are returned by the collection's 22 * iterator. 23 * 24 * @param c the collection whose elements are to be placed into this list 25 * @throws NullPointerException if the specified collection is null 26 */ 27 public ArrayList(Collection<? extends E> c) { 28 elementData = c.toArray(); 29 if ((size = elementData.length) != 0) { 30 // defend against c.toArray (incorrectly) not returning Object[] 31 // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652) 32 if (elementData.getClass() != Object[].class) 33 elementData = Arrays.copyOf(elementData, size, Object[].class); 34 } else { 35 // replace with empty array. 36 this.elementData = EMPTY_ELEMENTDATA; 37 } 38 }
1、第一个是指定数组初始长度的构造函数。先说下使用场景然后大家就能知道为什么会有一个指定初始长度的构造函数了,在你能预测到大概会有多少数据要存储到这个数值里的时候就可以用指定数组长度的构造函数来创建对象了,这样就能避免数组多次的扩容,影响性能。
着重关注下 initialCapacity == 0 的时候,elementData 的默认值是 EMPTY_ELEMENTDATA
2、第二个是不指定初始长度的构造函数。那么 elementData 的默认值是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ,跟指定初始值为0的情况下的默认值是不一样的
3、第三个就是构造一个包含指定元素的列表集合
着重看下 elementData.getClass() != Object[].class 的这个条件,是因为以前版本的JDK里getClass返回的类型不一定是Object[].class,所有做了一个判断,
Arrays.copyOf 有不懂的先自行查找。稍后我会写一篇介绍 Arrays.copyOf和System.arraycopy 的文章
另一个就是给定初始数据集合长度为0的时候 elementData 的默认值 EMPTY_ELEMENTDATA 跟指定数组长度为0的时候给的默认值一样
三、增
1 public boolean add(E e) { 2 modCount++; 3 add(e, elementData, size); 4 return true; 5 } 6 private void add(E e, Object[] elementData, int s) { 7 if (s == elementData.length) 8 elementData = grow(); 9 elementData[s] = e; 10 size = s + 1; 11 } 12 13 private Object[] grow() { 14 return grow(size + 1); 15 } 16 17 private Object[] grow(int minCapacity) { 18 return elementData = Arrays.copyOf(elementData, 19 newCapacity(minCapacity)); 20 } 21 private int newCapacity(int minCapacity) { 22 // overflow-conscious code 23 int oldCapacity = elementData.length; 24 int newCapacity = oldCapacity + (oldCapacity >> 1); 25 if (newCapacity - minCapacity <= 0) { 26 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 27 return Math.max(DEFAULT_CAPACITY, minCapacity); 28 if (minCapacity < 0) // overflow 29 throw new OutOfMemoryError(); 30 return minCapacity; 31 } 32 return (newCapacity - MAX_ARRAY_SIZE <= 0) 33 ? newCapacity 34 : hugeCapacity(minCapacity); 35 }