ArrayList 扩容 Android Java 真的不一

以前学java基础的时候 看过ArrayList的扩容机制

实现原理是下面这样 当时做的笔记
ArrayList扩容机制 在jdk1.7前是 *3/2+1 在jdk1.7开始就是 old+(old>>1) ->1.5倍扩容

然后今天看内存优化的时候 突然看到这个 就看了看android的ArrayList的源码
一看吓一跳 原来和JDK里面的算法有点不一样

然后马上进入JDK里面的源码 看了ArrayList 版本 1.8.0

• JDK 1.8 ArrayList源码

默认容量是10 初始化是10
private static final int DEFAULT_CAPACITY = 10;

直接传入 size初始化不会扩容 就直接创建一个新的数组

Paste_Image.png

直接看Add方法 在add的时候 如果容量不够 肯定会扩容

Paste_Image.png Paste_Image.png

发现这个函数

Paste_Image.png

最后发现 实现代码在这里
来分析一下 实现方式

Paste_Image.png Paste_Image.png

所以可以总结 JDK里面实现方式是 先1.5倍扩容 如果扩容之后还是小于现在需要的 就设置size为需要的
然后得到新的size 拿到新的size去和最大的MAX_Array_SIZE去比较 按照他的规则实现
最后创建一个新的数组 把原来的加载新的前面 后面就是空的

• 再看看Android内部的实现

初始大小是12 还说什么 12要好点 凑个团圆吗？

Paste_Image.png

/**
* The minimum amount by which the capacity of an ArrayList will increase.
* This tuning parameter controls a time-space tradeoff. This value (12)
* gives empirically good results and is arguably consistent with the
* RI's specified default initial capacity of 10: instead of 10, we start
* with 0 (sans allocation) and jump to 12.
*/
private static final int MIN_CAPACITY_INCREMENT = 12;

同样的先看 add方法

Paste_Image.png

再看看addAll方法 观察 Android在这里做了处理 在addAll的时候 有新的扩容机制

Paste_Image.png

发现还是和上面add的时候一样 但是进去的size不同了

Paste_Image.png Paste_Image.png

最大的不同来了 Android是在old+newPartSize=newSize 之后 对newSize扩容 而JDK 不是 JDK是newSize=old+old>>2 在比较newSize与需要的Size的大小

所以这里得出总结

• JDK 中 ArrayList的扩容机制 需要的size
  1 新的Size1.5倍扩容 newSize=old+old>>1
  2 发现扩容之后 还是不够 就设置为 需要的Size 在经过一次判断 大于设置的最大就给设置为Int最大值 否则就是int最大值-8(也就是默认设置的最大值)

• Android实现原理
  1 newSize=oldSize+newPartSize 然后对这个新的newSize进行 <12就设置为12 否则就 1.5倍扩容

举个例子
oldSzie=20 addAll(newPart) newPartSize=50;

JDK 中 old+old>>1=35 35<70 newSize=70 ---> Size=70

Android中
20+50 ---->70 70-1=69>6--->69+34=103 size=103

看下测试数据
Android版本的

Paste_Image.png

JDK的 与 想法一致

Paste_Image.png

oldSzie=20 addAll(newPart) newPartSize=10;

 for (int i = 0; i < 20; i++) {
        data.add("Daemon" + i);

           Class d = data.getClass();

    /*
    * 得到类中的所有属性集合
    */
    try {
        Field fs = d.getDeclaredField("elementData");
        fs.setAccessible(true);
        System.out.println("elementData.size " +i+"---"+ ((Object[])fs.get(data)).length);
    } catch (NoSuchFieldException e) {
        e.printStackTrace();
    } catch (IllegalAccessException e) {
        e.printStackTrace();
    }

    }

前20个加载完 初始化10 第11个进来的时候1.5被扩容 15 第16个进来扩容22 20个加载完毕 然后 加载10个 扩容 33 最后为33

当addAll（10） 的时候 oldSize+oldSize/2=33 所以在33之前 都能加载进去 不会扩大

JDK 实现

Paste_Image.png

Android 版本的 初始化 12 第13个进来扩容1.5倍 18 第19个进来扩容1.5 27
以后addAll因为算大不一样是 size+newpartsize 即 20+10-1扩容 也就是 43正确

Paste_Image.png

下班了 在路上手机码完

ArrayList 扩容 Android Java 真的不一样