从JDK源码学习Arraylist

  • 2020 年 4 月 10 日
  • 筆記

从今天开始从源码去学习一些Java的常用数据结构,打好基础:)

Arraylist源码阅读:

jdk版本:1.8.0

首先看其构造方法:

构造方法一:

第一种支持初始化容量大小,其中声明一个对象数组,赋值给this.elementdata

构造方法二:

第二种无参构造函数,即不指定初始容量大小,则默认赋值this.elementdata为一个空的对象数组,但是由注释可以看到其无参构造实际上初始容量为10

 

在elementData的注释中也说了该变量是实际存储Arrylist数据的存储结构,任何空的arraylist,当第一次被调用add放进元素时,将会扩充容量为default_capacity也就是10

 

 

 

 

看看其add方法,因为arraylist也是有序的,因此加入的元素在列表尾部,在添加元素之前,调用ensureCapacityInternal,确保内部容量大小

在ensureCapacityInternal中将判断当前的elementdata的值是否为空数组,若为空则赋值minCapacity为默认容量和入口参数minCapacity的较大值,然后进一步调用ensureExplicitCapacity明确容量大小

 

在ensureExplicitCapacity中,modCount自增,判断当前最小容量和arraylist的实际元素个数差值若大于零,则调用grow函数来进行实际的容量扩充

 

 

扩容函数grow先取到当前arraylist的实际长度,然后将其扩大1.5倍,然后判断该值和最小容量的大小,若扩充1.5倍小于所需要的最小容量,则赋值新的容量为需要的最小容量,此时并判断是否产生溢出情况,也就是注释里面的overflow conscious mode的含义,所以arraylist不是无限扩容,看下其max_array_size的值

 

数组最大值为integer.max_value-8,也就是2的31次-1-8

至于为什么要-8,这里有些vm要存储其最大值的大小需要八个字节,如下图所示

 

 如果扩充的新容量比max还大,则调用hugeCapacity,判断最小的容量和2的31次-1的大小,若大于则赋值max_value,否则说明此时最小容量介于max_value-8和max_value之间,则赋值为max_value-8

 

然后调用Array.copyof将旧的arraylist中的值拷贝到新的扩充后的arraylist中,所以默认空数组的add操作后容量即为10

构造方法三:

可以传递任何实现了Collection接口的类,其调用collection的toarray方法返回一个对象数组,也就是将集合中的元素以对象数组形式返回,toarray的注释里也说明了这个方法是array和collection的桥梁

 

 

 为了防止重写toArray方法返回的并不是对象数组,因此这里判断一下elementData的类是否是对象数组,如果不是的话,则将element中的数组copy到对象数组中

比如有MySubClass是MyClass的子类。  Collection<MyClass> myCollection;  //myCollection里有很多元素。  Collection<MySubClass> mySubCollection;  //mySubCollection里有很多元素。  ArrayList<MyClass> myList = new ArrayList<MyClass>(myCollection);  也可以:  ArrayList<MyClass> myList = new ArrayList<MyClass>(mySubCollection);

意思就是这里用extends e,来指定定义一个父类的arraylist,则其所有子类的集合都能放进该父类的arraylist,从而编译器才能够知道放入的元素都是满足?也就是,初始定义arraylist的类型声明

关于线程安全:

 上面遗留了一个modcount++的自增操作的解释,看一下jdk对modcount的解释

 该参数是对arraylist容量大小修改的次数,也就是删减元素改变大小时可能会使正常的迭代过程出现错误,那么针对单线程而言,不存在又读又写,但在多线程情况下,可能存在读写同时进行的操作,参考知乎一个很精简明确的答案,看完真的是一目了然,如果结构发生变化则抛出ConcurrentModificationException

 

 通过调用上面这个方法来判断是否结构发生变化,调用add remove时都将修改modcount,通过迭代时先保存一份modcount,若迭代过程中再取modcount和保存的值不等则抛出异常

总结:

①.初始不指定容量时设置为10

②.每次扩充为实际长度的1.5倍与所需最小容量比较

③.arraylist是非线程安全的

④.其最大值为2的31次-1

⑤.为避免连续扩容消耗内存,能初始化容量大小尽量指定容量

⑥.为啥会非线程安全,因为方法内部并非原子操作

 

参考:

https://zhuanlan.zhihu.com/p/72296421  hashmap

https://zhuanlan.zhihu.com/p/73283922  linkedhashmap

https://zhuanlan.zhihu.com/p/72463637 hashset

https://zhuanlan.zhihu.com/p/72156592 arraylist

https://www.jianshu.com/p/f174d49b391c

https://www.cnblogs.com/LiaHon/p/11089988.html 

https://blog.csdn.net/u012859681/article/details/78206494 线程安全问题