阅读java.util.ArrayList源码Note

原创
2020/04/14 13:36
阅读数 59

随笔,格式不工整!看到一块则记录一点

类图:

笔记

方法

List#toArray() 返回类型是Object List#toArray(T[] a)返回类型和集合的元素类型一致,如果数组空间比集合大,则原数组返回;否则会构建一个新的数组。 contains比较 o == null ? e == null : o.equals(e) java.util.function.UnaryOperator 入参和出参的类型一致 java.util.ListIterator 更强大的Iterator,双向遍历,同时可更改和删除元素、替换元素 sort: 指定的comparator为null时,元素必须实现comparable接口,同时实现比较方法没使用此方法进行排序 java.util.Comparator java.lang.Comparable 默认的比较实现借鉴于: http://svn.python.org/projects/python/trunk/Objects/listsort.txt

专注看下subList以及spliterator java.util.Spliterator 用于分隔元素列表,列表可以是集合、数组、IO Channel等

subList提供了一个视图,任何变动都是双向影响的。不要试图更改原始list的结构(size变化)

ArrayList

c.toArray might (incorrectly) not return Object[] (see 6260652) 此问题涉及到了构造器,使用传入的集合,生成一个新的集合。默认会调用集合的toArray()方法,获得一个数组,将此数组赋值到内部持有的数组对象上。 如果toArray返回的不是object类型的数组,则后续往里面加元素时会产生问题,数组的类型是子类型,无法将父类型放入数组中,因此,需将数组的类型设置为 object[],因此,可以将任何类型的实例放入集合中。 借鉴文章 c.toArray might (incorrectly) not return Object[] (see 6260652)

扩容

扩容一般都是使用 java.util.Arrays#copyOf(T[], int),扩容默认是按照原始大小的一半,意即:原始为8,扩容后为 12. 与指定的大小比较,去两者中较大的一个。

contains方法底层使用了indexOf方法,判断返回的索引>=0; indexOf: o == null ? e == null : o.equals(e)

集合中元素存放在底层数组的前size个位置上

java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>) 创建了新的数组 java.lang.System#arraycopy copy数组元素至另外一个数组

toArray(T[] a), 如果a的length大于集合的size,则直接将集合的元素复制到数组中,从0位开始覆盖!,并在数组的size位置设置为null,此举是为了方便判断集合的大小,如果调用者明确的知道集合中不含有null的话。

集合增加因素之前需考虑扩容 java.util.ArrayList#ensureCapacityInternal

  1. 如果集合的数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,则取指定的扩容大小和默认的10之间的最大值
  2. 将modCount递增,不管扩容是否成功,都会增加此值
  3. 若计算后得到的扩容大小大于数组的length时,才可扩容
  4. 默认扩容大小为原始数组长度的一半,例如数组长度是20,则扩容后大小为20 + 10 = 30
  5. 比较计算得到的扩容大小和指定的扩容大小,取其中较大值
  6. 处理超大集合的问题,与MAX_ARRAY_SIZE(Integer的最大值-8)比较,若超过它,则取integer的最大值。
  7. 注意扩容过程中,数值的溢出 overflow
  8. 最后创建新数据,复制原始数据元素,并将新数组赋值给elementData

add、addAll

  1. 扩容
  2. 赋值数组size位置的元素值为指定的入参
  3. size++ add(index,o)、addAll(index, c)
  4. 扩容
  5. 确定是否需后移,若是则将index位置及后续的元素往后异动一位或c的size,
  6. 将index位置的元素赋值为0或者复制c的元素
  7. size++ remove
  8. 根据规则找到位置,o == null ? 找到数组第一个null元素 : 找到数组第一个o.equals(e)
  9. 将index后续的元素迁移一位
  10. 将数组size位置的元素设置为null
  11. size-- 数组扩容和移动元素时使用java.lang.System#arraycopy

java.util.ArrayList#batchRemove此方法写的很巧妙,遍历集合中的所有元素,将符合条件的元素复制至数组的头部,从0位开始。 最后若复制的个数不等于size,则将复制数组的前w个元素,后续的元素全部置位null,同时减少size 注意: 此操作即使出现了异常,也会将后续未处理的元素复制至前面。

Java中Class.this和this的区别: 当inner class(内部类)必顺使用到outer class(外部类)的this instance(实例)时,或者匿名内部类要使用外部类的实例

赋值的同时返回赋值后的结果 int i = 0; System.out.println(i=2); // 2

java.util.BitSet 可看下作用及用法 java.util.Splitetrator: 为Stream流式处理而加!可参考 https://segmentfault.com/q/1010000007087438

首先先直接给一个答案:Spliterator(splitable iterator可分割迭代器)接口是Java为了并行遍历数据源中的元素而设计的迭代器,这个可以类比最早Java提供的顺序遍历迭代器Iterator,但一个是顺序遍历,一个是并行遍历

从最早Java提供顺序遍历迭代器Iterator时,那个时候还是单核时代,但现在多核时代下,顺序遍历已经不能满足需求了...如何把多个任务分配到不同核上并行执行,才是能最大发挥多核的能力,所以Spliterator应运而生啦

因为对于数据源而言...集合是描述它最多的情况,所以Java已经默认在集合框架中为所有的数据结构提供了一个默认的Spliterator实现,相应的这个实现其实就是底层Stream如何并行遍历(Stream.isParallel())的实现啦,因此平常用到Spliterator的情况是不多的...因为Java8这次正是一次引用函数式编程的思想,你只需要告诉JDK你要做什么并行任务,关注业务本身,至于如何并行,怎么并行效率最高,就交给JDK自己去思考和优化速度了(想想以前写如何并发的代码被支配的恐惧吧)作为调用者我们只需要去关心一些filter,map,collect等业务操作即可

所以想要看Spliterator的实现,可以直接去看JDK对于集合框架的实现,很多实现类你可以在Spliterators中找到的,也可以直接去你对应集合的stream方法中找到,比如ArrayList点进去的是Collection的默认实现,只需要提供一个Spliterator的实现,然后用StreamSupport就可以构造一个Stream了,相当方便

对于Spliterator接口的设计思想,应该要提到的是Java7的Fork/Join(分支/合并)框架,总得来说就是用递归的方式把并行的任务拆分成更小的子任务,然后把每个子任务的结果合并起来生成整体结果。带着这个理解来看看Spliterator接口提供的方法

第一个方法tryAdvance就是顺序处理每个元素,类似Iterator,如果还有元素要处理,则返回true,否则返回false 第二个方法trySplit,这就是为Spliterator专门设计的方法,区分与普通的Iterator,该方法会把当前元素划分一部分出去创建一个新的Spliterator作为返回,两个Spliterator变会并行执行,如果元素个数小到无法划分则返回null 第三个方法estimateSize,该方法用于估算还剩下多少个元素需要遍历 第四个方法characteristics,其实就是表示该Spliterator有哪些特性,用于可以更好控制和优化Spliterator的使用,具体属性你可以随便百度到,这里就不再赘言

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部