最近在回顾数据结构,想到 JDK 这样好的代码资源不利用有点可惜,这是第一篇,花了心思。篇幅有点长,希望想看的朋友认真看下去,提出宝贵的意见。 :)
ArrayList 的 3 个字段
ArrayList 保存的真的是对象吗?
- private transient Object[] elementData; //对象数组,用于存储 持有对象的 引用
- private int size; //代表了 ArrayList 的长度。随着插入 删除 添加 而改变。
- protected transient int modCount = 0; //从AbstractList继承得到,这个字段最后介绍,先忽视它。
空 ArrayList 的优化 : new 一个空的 ArrayList 是很常见的做法,为了不让每个空 ArrayList 都创建一个空数组实例,ArrayList 内部有一个用于共享,静态的空数组对象。当创建空的 ArrayList 时,内部的 elementData 就会指向这个共享的空数组: EMPTY_ELEMENTDATA
同时也会发现:当 new 一个空 ArrayList 时,不会马上在内存中分配 DEFAULT_CAPACITY =10 个长度的 elementData 数组,而是等到第一个元素被添加时,才会去申请分配默认长度 为 10 的 elementData 数组。
- private static final Object[] EMPTY_ELEMENTDATA = {}; //用于所有空ArrayList共享的 空数组,注意它是静态字段。
- private static final int DEFAULT_CAPACITY = 10; //第一次分配容量时,默认的初始容量大小
- //////////////////////////////////////////////
- public ArrayList() {
- super();
- this.elementData = EMPTY_ELEMENTDATA; //指向空数组
- }
当然,如果在 new 时指定了 初始容量 initCapacity,就会立刻 创建一个 长度为 initialCapacity 大小的 elementData 数组
也可以从另一个一个集合构造
- public ArrayList(int initialCapacity) {
- super();
- if (initialCapacity < 0)
- throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
- this.elementData = new Object[initialCapacity];
- }
- public ArrayList(Collectionextends E> c) {
- elementData = c.toArray();
- size = elementData.length;
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- }
虽然 ArrayList 号称 动态数组,其长度自动调整,但是内部 保存持有对象的引用的数组 elementData 却是一个普通的数组(Java 数组的长度是不可变的),因此,ArrayList 就必须实现容量扩展操作,在 elementData 满 时,让 elementData 指向长度更大的数组。
以保证在任何时候:elementData.length >= size
elementData 的长度就 是 ArrayList 的容量(capacity)。
以下是关于容量调配的 API(绿色标记的是 public 方法,红色的是 private)
查看源码时,我发现,向 ArrayList 中添加新元素的时,都会先 使用 ensureCapacityInternal 这个函数去检查容量是否够用。如图中,参数为 size+1 ,也就是要保证容量至少为 size+1 个,这样新元素才能放得下。我们去看看这个函数的实现。
- /*
- 函数作用:用于确保 ArrayList 的容量至少有 参数指定的minCapacity个
- */
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == EMPTY_ELEMENTDATA) { //这个if用于处理 往 空ArrayList中添加第一个元素时的情况
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity); //内部又委托了这个函数,继续往下看
- }
- /*
- 函数作用:用于确保 ArrayList 的容量至少有 参数指定的minCapacity个
- */
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length > 0) //如果当前容量 真的比 要求的 minCapacity 小
- grow(minCapacity); //那就交给grow函数去扩张容量去吧。
- }
最终的增长逻辑都是委托 grow() 方法实现的。只要调用了 grow 这个函数,就一定会使容量增加。我们来看看容量到底是怎么增加的。
总结如下,有 3 种情况:
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- int newCapacity = oldCapacity + (oldCapacity >> 1); //先让 newCapacity = 原来的1.5倍,这是默认的增长策略。
- //再接着来判断这个策略是否合适
- if (newCapacity - minCapacity < 0) //如果变为原来的1.5倍还是不够
- newCapacity = minCapacity; //那就要多少给多少吧。
- if (newCapacity - MAX_ARRAY_SIZE > 0) //如果要求的容量超大,(大于MAX_ARRAY_SIZE),这个时候就必须慎重。怎么办?
- newCapacity = hugeCapacity(minCapacity); //交给 hugeCapacity函数去决定到底给多少,这个函数会返回 MAX_ARRAY_SIZE 或者 Integer.MAX_VALUE。
- elementData = Arrays.copyOf(elementData, newCapacity); //经过一轮轮的判断,终于定下了新的容量,好,调整elementData的容量为 newCapacity!
- }
注:newCapacit 为需求容量,oldCapacity 原来的容量
1、oldCapacity < newCapacit <= oldCapacity * 1.5
平缓增长的正常情况。例如原来容量为 10 ,现在期望达到 11 个,则会扩展 调整到 10 + (10>> 1) =15 个 ,也就是变为 原来的 1.5 倍。
2、oldCapacity*1.5 < newCapacit <= MAX_ARRAY_SIZE
默认的 1.5 倍增长还不够,期望的容量有点大。例如原来容量为 10 ,现在请求 100 个,那么就会实打实的扩展到 100 个的容量。
3、MAX_ARRAY_SIZE < newCapacit <= Interger.MAX_VALUE
极端情况,期望的容量超大 。在这个情况下,newCapacity 的值最终是由 hugeCapacity 函数决定的,它会返回 MAX_ARRAY_SIZE 或者 Integer.MAX_VALUE
所以,ArrayList 的最多容量不要超过 MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8) , 也就是 2147483639 个 (疯子才会使用这么多吧),否则是会抛异常的。下面还有 2 个是公开的接口公开接口:避免多余的浪费,让容量裁剪为和 size 一样大
- //有些Java虚拟机会在数组内存的头部保留 一些字节的容量来存储这个内存块的相关信息,因此,数组的 安全最大长度是 : Integer.MAX_VALUE - 8
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- public void trimToSize() {
- modCount++;
- if (size < elementData.length) {
- elementData = Arrays.copyOf(elementData, size);
- }
- }
公开接口:一次性决定 ArrayList 的最大容量,避免半路上不断的调整容量带来开销(如果你真的很确定你需要的 ArrayList 的最大长度,否则没必要)
总结:默认情况下,ArrayList 平缓增长时,每次增长为原来的容量的 1.5 倍。
- public void ensureCapacity(int minCapacity) {
- int minExpand = (elementData != EMPTY_ELEMENTDATA)
- // any size if real element table
- ? 0
- // larger than default for empty table. It's already supposed to be
- // at default size.
- : DEFAULT_CAPACITY;
- if (minCapacity > minExpand) {
- ensureExplicitCapacity(minCapacity);
- }
- }
来源: http://www.cnblogs.com/lulipro/p/6553816.html