从今天开始从源码去学习一些 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 和保存的值不等则抛出异常
总结:
1. 初始不指定容量时设置为 10
2. 每次扩充为实际长度的 1.5 倍与所需最小容量比较
3.arraylist 是非线程安全的
4. 其最大值为 2 的 31 次 - 1
5. 为避免连续扩容消耗内存, 能初始化容量大小尽量指定容量
6. 为啥会非线程安全, 因为方法内部并非原子操作
参考:
- 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://www.cnblogs.com/tr1ple/p/12662603.html