I'll try anything once

人生苦短,何妨一试

ArrayList源码解读

前言

源码还要读的, 所以开始先从ArrayList开始了, 持续更新, 后面会继续完善

从构造函数开始

总结

  1. 常量EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了初始化elementData的。如果为无参构造函数,使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA;如果为含参构造函数,使用EMPTY_ELEMENTDATA
  2. 以无参构造方法创建arraylist时, 实际上初始化的值是一个空数组. 添加第一个元素时 扩容为10

ArrayList扩容机制

add 方法

ensureCapacityInternal 方法

在查看该方法时, 发现其调用了其他的方法, 然后其他的方法也调用了另外的方法, 所有全部粘上

逻辑分析

  • 当使用add方法 添加了第一个元素, elementData.length() == 0; (当前还是一个空的list) , 因为执行了ensureCapacityInternal(size + 1)方法, 通过calculateCapacity()方法, 使得minCapacity为10,

    同时ensureCapacityInternal()方法调用了ensureExplicitCapacity()方法, 因为minCapacity - elementData.length > 0 所以调用了grow()方法.

  • 当添加第二个元素的时候, minCapacity=2, 之后的步骤和添加第一个元素一样, 但是因为不满足minCapacity - elementData.length > 0所以不会执行grow方法.

  • 当添加第三个元素的时候, 同理

  • 最后添加第11个元素的时候, 才重新开始执行grow方法.

grow 方法

核心

当当前的容量满了之后, 每次的扩容都会变为原来的1.5背.int newCapacity = oldCapacity + (oldCapacity >> 1);

“>>”(移位运算符):>>1 右移一位相当于除2,右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源  

  • 当add第1个元素时,oldCapacity 为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity 不比 MAX_ARRAY_SIZE大,则不会进入 hugeCapacity 方法。数组容量为10,add方法中 return true,size增为1。
  • 当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中return true,size增为11。
  • 以此类推··

hugeCapacity方法

只有newCapacity >MAX_ARRAY_SIZE 才回调用该方法, 方法中使用三元运算, 意思是若果minCapacity> MAX_ARRAY_SIZEnewCapacity的容量大小为Integer.MAX_VALUE也就是2**31次方, 若是minCapacity< MAX_ARRAY_SIZEnewCapacity的容量大小为Integer.MAX_VALUE-8

Arrays.copyOf() 和 System.arraycopy()的区别

在看ArrayList的源码的时候, 会发现有很多的地方, 都是用来这两个函数, 这两个函数的具体区别, 通过阅读源码的方式, 发现, 其实copyOf()其实也是通过arraycopy()实现的

  1. copyOf()是返回一个新的数组, 并且该数组是系统自行创建的
  2. arrycopy()是将原数组拷贝的一个新的数组中, 并且新的数组可以自行定义, 也可以是原来的数组, 同时可以选择拷贝的起点和长度, 以及放入新数组中的位置.
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 2 =