[关闭]
@kiraSally 2018-03-12T18:48:28.000000Z 字数 11451 阅读 1885

集合番@ArrayList一文通(1.8版)

JAVA COLLECTIONS 源码 1.8版


1.ArrayList上级接口的变化

  1. public class ArrayList<E> extends AbstractList<E>
  2. implements List<E>, RandomAccess, Cloneable, java.io.Serializable

QQ截图20170809181720.png-42kB

  1. public interface Collection<E> extends Iterable<E> {
  2. .....
  3. //1.8新增方法:提供了接口默认实现,返回分片迭代器
  4. @Override
  5. default Spliterator<E> spliterator() {
  6. return Spliterators.spliterator(this, 0);
  7. }
  8. //1.8新增方法:提供了接口默认实现,返回串行流对象
  9. default Stream<E> stream() {
  10. return StreamSupport.stream(spliterator(), false);
  11. }
  12. //1.8新增方法:提供了接口默认实现,返回并行流对象
  13. default Stream<E> parallelStream() {
  14. return StreamSupport.stream(spliterator(), true);
  15. }
  16. /**
  17. * Removes all of the elements of this collection that satisfy the given
  18. * predicate. Errors or runtime exceptions thrown during iteration or by
  19. * the predicate are relayed to the caller.
  20. * 1.8新增方法:提供了接口默认实现,移除集合内所有匹配规则的元素,支持Lambda表达式
  21. */
  22. default boolean removeIf(Predicate<? super E> filter) {
  23. //空指针校验
  24. Objects.requireNonNull(filter);
  25. //注意:JDK官方推荐的遍历方式还是Iterator,虽然forEach是直接用for循环
  26. boolean removed = false;
  27. final Iterator<E> each = iterator();
  28. while (each.hasNext()) {
  29. if (filter.test(each.next())) {
  30. each.remove();//移除元素必须选用Iterator.remove()方法
  31. removed = true;//一旦有一个移除成功,就返回true
  32. }
  33. }
  34. //这里补充一下:由于一旦出现移除失败将抛出异常,因此返回false指的仅仅是没有匹配到任何元素而不是运行异常
  35. return removed;
  36. }
  37. }
  38. public interface Iterable<T>{
  39. .....
  40. //1.8新增方法:提供了接口默认实现,用于遍历集合
  41. default void forEach(Consumer<? super T> action) {
  42. Objects.requireNonNull(action);
  43. for (T t : this) {
  44. action.accept(t);
  45. }
  46. }
  47. //1.8新增方法:提供了接口默认实现,返回分片迭代器
  48. default Spliterator<T> spliterator() {
  49. return Spliterators.spliteratorUnknownSize(iterator(), 0);
  50. }
  51. }
  52. public interface List<E> extends Collection<E> {
  53. //1.8新增方法:提供了接口默认实现,用于对集合进行排序,主要是方便Lambda表达式
  54. default void sort(Comparator<? super E> c) {
  55. Object[] a = this.toArray();
  56. Arrays.sort(a, (Comparator) c);
  57. ListIterator<E> i = this.listIterator();
  58. for (Object e : a) {
  59. i.next();
  60. i.set((E) e);
  61. }
  62. }
  63. //1.8新增方法:提供了接口默认实现,支持批量删除,主要是方便Lambda表达式
  64. default void replaceAll(UnaryOperator<E> operator) {
  65. Objects.requireNonNull(operator);
  66. final ListIterator<E> li = this.listIterator();
  67. while (li.hasNext()) {
  68. li.set(operator.apply(li.next()));
  69. }
  70. }
  71. /**
  72. * 1.8新增方法:返回ListIterator实例对象
  73. * 1.8专门为List提供了专门的ListIterator,相比于Iterator主要有以下增强:
  74. * 1.ListIterator新增hasPrevious()和previous()方法,从而可以实现逆向遍历
  75. * 2.ListIterator新增nextIndex()和previousIndex()方法,增强了其索引定位的能力
  76. * 3.ListIterator新增set()方法,可以实现对象的修改
  77. * 4.ListIterator新增add()方法,可以向List中添加对象
  78. */
  79. ListIterator<E> listIterator();
  80. }

2.ArrayList的变化

3.ArrayList的属性变化

  1. /**
  2. * The array buffer into which the elements of the ArrayList are stored.
  3. * The capacity of the ArrayList is the length of this array buffer.
  4. * Any empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
  5. * DEFAULT_CAPACITY when the first element is added.
  6. * 数组缓存,跟1.7版本相比,主要有两个变化:
  7. * 1.去掉private属性,使用默认的friendly作用域,开放给同包类使用
  8. * 2.一个空数组的elementData将设置为EMPTY_ELEMENTDATA直到第一个元素新增时
  9. * 使用DEFAULT_CAPACITY(10)完成有容量的初始化 -- 优化:这里选择将内存分配后置,而从尽可能节省空间
  10. */
  11. transient Object[] elementData; // non-private to simplify nested class access
  12. /**
  13. * Shared empty array instance used for empty instances.
  14. * 当时用空构造时,给予数组(elementData)默认值
  15. */
  16. private static final Object[] EMPTY_ELEMENTDATA = {};
  1. /**
  2. * Constructs an empty list with an initial capacity of ten.
  3. * 1.8版的默认构造器,只会初始化一个空数组
  4. */
  5. public ArrayList() {
  6. super();
  7. this.elementData = EMPTY_ELEMENTDATA;//初始化一个空数组
  8. }
  9. /**
  10. * Constructs an empty list with an initial capacity of ten.
  11. * 1.7版的默认构造器,会直接初始化一个10容量的数组
  12. */
  13. public ArrayList() {
  14. this(10);
  15. }

4.ArrayList的方法变化

  1. /**
  2. * 1.8版的trimToSize,跟1.7版相比:
  3. * 可以明显的看到去掉了oldCapacity这一临时变量
  4. * 笔者认为这进一步强调了HashMap是非线程安全的,因此直接用length即可
  5. */
  6. public void trimToSize() {
  7. modCount++;
  8. if (size < elementData.length) {
  9. elementData = Arrays.copyOf(elementData, size);
  10. }
  11. }
  12. /**
  13. * 1.7版的trimToSize
  14. */
  15. public void trimToSize() {
  16. modCount++;
  17. int oldCapacity = elementData.length;
  18. if (size < oldCapacity) {
  19. elementData = Arrays.copyOf(elementData, size);
  20. }
  21. }

5.ArrayList的新增方法

5.1 forEach方法

  1. /**
  2. * Performs the given action for each element of the {@code Iterable}
  3. * until all elements have been processed or the action throws an
  4. * exception. Unless otherwise specified by the implementing class,
  5. * actions are performed in the order of iteration (if an iteration order
  6. * is specified). Exceptions thrown by the action are relayed to the
  7. * caller.
  8. * 1.8新增方法,重写Iterable接口的forEach方法
  9. * 提供对数组的遍历操作,由于支持Consumer因此在遍历时将执行传入的方法
  10. */
  11. @Override
  12. public void forEach(Consumer<? super E> action) {
  13. Objects.requireNonNull(action);
  14. final int expectedModCount = modCount;
  15. @SuppressWarnings("unchecked")
  16. final E[] elementData = (E[]) this.elementData;
  17. final int size = this.size;
  18. for (int i=0; modCount == expectedModCount && i < size; i++) {
  19. action.accept(elementData[i]);//执行传入的自定义方法
  20. }
  21. if (modCount != expectedModCount) {
  22. throw new ConcurrentModificationException();
  23. }
  24. }
  25. --------------
  26. List<String> list = new ArrayList<>();
  27. list.add("有村架纯");
  28. list.add("桥本环奈");
  29. list.add("斋藤飞鸟");
  30. list.forEach(s -> System.out.print(s + "!!")); //输出:有村架纯!!桥本环奈!!斋藤飞鸟!!

5.2 removeIf方法

  1. /**
  2. * Removes all of the elements of this collection that satisfy the given
  3. * predicate. Errors or runtime exceptions thrown during iteration or by
  4. * the predicate are relayed to the caller.
  5. * 1.8新增方法,重写Collection接口的removeIf方法
  6. * 移除集合内所有复合匹配条件的元素,迭代时报错会抛出异常 或 把断言传递给调用者(即断言中断)
  7. * 该方法主要干了两件事情:
  8. * 1.根据匹配规则找到所有符合要求的元素
  9. * 2.移除元素并转移剩余元素位置
  10. * 补充:为了安全和快速,removeIf分成两步走,而不是直接找到就执行删除和转移操作,写法值得借鉴
  11. */
  12. @Override
  13. public boolean removeIf(Predicate<? super E> filter) {
  14. Objects.requireNonNull(filter);
  15. // figure out which elements are to be removed any exception thrown from
  16. // the filter predicate at this stage will leave the collection unmodified
  17. int removeCount = 0;
  18. //BitSet用于按位存储,这里用作存储待移除元素(即符合匹配规则的元素)
  19. //BitSet能够通过位图算法大幅减少数据占用存储空间和内存,尤其适合在海量数据方面,这里是个很明显的优化
  20. //有机会会在基础番中解析一下BitSet的奇妙之处
  21. final BitSet removeSet = new BitSet(size);
  22. final int expectedModCount = modCount;
  23. final int size = this.size;
  24. //每次循环都要判断modCount == expectedModCount!
  25. for (int i=0; modCount == expectedModCount && i < size; i++) {
  26. @SuppressWarnings("unchecked")
  27. final E element = (E) elementData[i];
  28. if (filter.test(element)) {
  29. removeSet.set(i);
  30. removeCount++;
  31. }
  32. }
  33. if (modCount != expectedModCount) {
  34. throw new ConcurrentModificationException();
  35. }
  36. // shift surviving elements left over the spaces left by removed elements
  37. // 当有元素被移除,需要对剩余元素进行位移
  38. final boolean anyToRemove = removeCount > 0;
  39. if (anyToRemove) {
  40. final int newSize = size - removeCount;
  41. for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
  42. i = removeSet.nextClearBit(i);
  43. elementData[j] = elementData[i];
  44. }
  45. for (int k=newSize; k < size; k++) {
  46. elementData[k] = null; // Let gc do its work
  47. }
  48. this.size = newSize;
  49. if (modCount != expectedModCount) {
  50. throw new ConcurrentModificationException();
  51. }
  52. modCount++;
  53. }
  54. //正常情况下,一旦匹配到元素,应该删除成功,否则将抛出异常,当没有匹配到任何元素时,返回false
  55. return anyToRemove;
  56. }
  57. --------------
  58. List<String> list = new ArrayList<>();
  59. list.add("有村架纯");
  60. list.add("桥本环奈");
  61. list.add("斋藤飞鸟");
  62. list.forEach(s -> System.out.print(s + "!!")); //输出:有村架纯!!桥本环奈!!斋藤飞鸟!!
  63. System.out.println(list.removeIf(s -> s.startsWith("斋藤")));//输出:true
  64. list.forEach(s -> System.out.print(s + ",")); //输出:有村架纯!!桥本环奈!!
  65. --------------
  66. //这里补充一点,使用Arrays.asList()生成的ArrayList是Arrays自己的私有静态内部类
  67. //强行使用removeIf的话会抛出java.lang.UnsupportedOperationException的异常(因为它没实现这个方法)

5.3 replaceAll方法

  1. /**
  2. * Replaces each element of this list with the result of applying the operator to that element.
  3. * Errors or runtime exceptions thrown by the operator are relayed to the caller.
  4. * 1.8新增方法,重写List接口的replaceAll方法
  5. * 提供支持一元操作的批量替换功能
  6. */
  7. @Override
  8. @SuppressWarnings("unchecked")
  9. public void replaceAll(UnaryOperator<E> operator) {
  10. Objects.requireNonNull(operator);
  11. final int expectedModCount = modCount;
  12. final int size = this.size;
  13. for (int i=0; modCount == expectedModCount && i < size; i++) {
  14. elementData[i] = operator.apply((E) elementData[i]);
  15. }
  16. if (modCount != expectedModCount) {
  17. throw new ConcurrentModificationException();
  18. }
  19. modCount++;
  20. }
  21. --------------
  22. List<String> list = new ArrayList<>();
  23. list.add("有村架纯");
  24. list.add("桥本环奈");
  25. list.add("斋藤飞鸟");
  26. list.forEach(s -> System.out.print(s + "!!")); //输出:有村架纯!!桥本环奈!!斋藤飞鸟!!
  27. list.replaceAll(t -> {
  28. if(t.equals("桥本环奈")) t = "逢泽莉娜";//这里我们将"桥本环奈"替换成"逢泽莉娜"
  29. return t;//注意如果是语句块的话一定要返回
  30. });
  31. list.forEach(s -> System.out.print(s + "!!")); //输出:有村架纯!!逢泽莉娜!!斋藤飞鸟!!

5.4 sort方法

  1. /**
  2. * Sorts this list according to the order induced by the specified
  3. * 1.8新增方法,重写List接口的sort方法
  4. * 支持对数组进行排序,主要方便于Lambda表达式
  5. */
  6. @Override
  7. @SuppressWarnings("unchecked")
  8. public void sort(Comparator<? super E> c) {
  9. final int expectedModCount = modCount;
  10. //Arrays.sort底层是结合归并排序和插入排序的混合排序算法,有不错的性能
  11. //有机会在基础番对Timsort(1.8版)和ComparableTimSort(1.7版)进行解析
  12. Arrays.sort((E[]) elementData, 0, size, c);
  13. if (modCount != expectedModCount) {
  14. throw new ConcurrentModificationException();
  15. }
  16. modCount++;
  17. }
  18. --------------
  19. List<String> list = new ArrayList<>();
  20. list.add("有村架纯");
  21. list.add("桥本环奈");
  22. list.add("斋藤飞鸟");
  23. list.forEach(s -> System.out.print(s + "!!")); //输出:有村架纯!!桥本环奈!!斋藤飞鸟!!
  24. list.sort((prev, next) -> prev.compareTo(next));//这里我们选用自然排序
  25. list.forEach(s -> System.out.print(s + "!!"));//输出:斋藤飞鸟!!有村架纯!!桥本环奈!!

6.ArrayList的新增并行分片迭代器

  • 并行分片迭代器是Java为了并行遍历数据源中的元素而专门设计的迭代器
  • 并行分片迭代器借鉴了Fork/Join框架的核心思想:用递归的方式把并行的任务拆分成更小的子任务,然后把每个子任务的结果合并起来生成整体结果
  • 并行分片迭代器主要是提供给Stream,准确说是提供给并行流使用,使用时推荐直接用Stream即可
  1. default Stream<E> parallelStream() {//并行流
  2. return StreamSupport.stream(spliterator(), true);//true表示使用并行处理
  3. }
  4. static final class ArrayListSpliterator<E> implements Spliterator<E> {
  5. private final ArrayList<E> list;
  6. //起始位置(包含),advance/split操作时会修改
  7. private int index; // current index, modified on advance/split
  8. //结束位置(不包含),-1 表示到最后一个元素
  9. private int fence; // -1 until used; then one past last index
  10. private int expectedModCount; // initialized when fence set
  11. /** Create new spliterator covering the given range */
  12. ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
  13. int expectedModCount) {
  14. this.list = list; // OK if null unless traversed
  15. this.index = origin;
  16. this.fence = fence;
  17. this.expectedModCount = expectedModCount;
  18. }
  19. /**
  20. * 获取结束位置,主要用于第一次使用时对fence的初始化赋值
  21. */
  22. private int getFence() { // initialize fence to size on first use
  23. int hi; // (a specialized variant appears in method forEach)
  24. ArrayList<E> lst;
  25. if ((hi = fence) < 0) {
  26. //当list为空,fence=0
  27. if ((lst = list) == null)
  28. hi = fence = 0;
  29. else {
  30. //否则,fence = list的长度
  31. expectedModCount = lst.modCount;
  32. hi = fence = lst.size;
  33. }
  34. }
  35. return hi;
  36. }
  37. /**
  38. * 对任务(list)分割,返回一个新的Spliterator迭代器
  39. */
  40. public ArrayListSpliterator<E> trySplit() {
  41. //二分法
  42. int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
  43. return (lo >= mid) ? null : // divide range in half unless too small 分成两部分,除非不够分
  44. new ArrayListSpliterator<E>(list, lo, index = mid,expectedModCount);
  45. }
  46. /**
  47. * 对单个元素执行给定的执行方法
  48. * 若没有元素需要执行,返回false;若可能还有元素尚未执行,返回true
  49. */
  50. public boolean tryAdvance(Consumer<? super E> action) {
  51. if (action == null)
  52. throw new NullPointerException();
  53. int hi = getFence(), i = index;
  54. if (i < hi) {//起始位置 < 终止位置 -> 说明还有元素尚未执行
  55. index = i + 1; //起始位置后移一位
  56. @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
  57. action.accept(e);//执行给定的方法
  58. if (list.modCount != expectedModCount)
  59. throw new ConcurrentModificationException();
  60. return true;
  61. }
  62. return false;
  63. }
  64. /**
  65. * 对每个元素执行给定的方法,依次处理,直到所有元素已被处理或被异常终止
  66. * 默认方法调用tryAdvance方法
  67. */
  68. public void forEachRemaining(Consumer<? super E> action) {
  69. int i, hi, mc; // hoist accesses and checks from loop
  70. ArrayList<E> lst; Object[] a;
  71. if (action == null)
  72. throw new NullPointerException();
  73. if ((lst = list) != null && (a = lst.elementData) != null) {
  74. if ((hi = fence) < 0) {
  75. mc = lst.modCount;
  76. hi = lst.size;
  77. }
  78. else
  79. mc = expectedModCount;
  80. if ((i = index) >= 0 && (index = hi) <= a.length) {
  81. for (; i < hi; ++i) {
  82. @SuppressWarnings("unchecked") E e = (E) a[i];
  83. action.accept(e);
  84. }
  85. if (lst.modCount == mc)
  86. return;
  87. }
  88. }
  89. throw new ConcurrentModificationException();
  90. }
  91. /**
  92. * 计算尚未执行的任务个数
  93. */
  94. public long estimateSize() {
  95. return (long) (getFence() - index);
  96. }
  97. /**
  98. * 返回当前对象的特征量
  99. */
  100. public int characteristics() {
  101. return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
  102. }
  103. }
  104. --------------
  105. List<String> list = new ArrayList<>();
  106. list.add("有村架纯");
  107. list.add("桥本环奈");
  108. list.add("斋藤飞鸟");
  109. Spliterator<String> spliterator = list.spliterator();
  110. spliterator.forEachRemaining(s -> System.out.print(s += "妹子!!"));
  111. //输出:有村架纯妹子!!桥本环奈妹子!!斋藤飞鸟妹子!!
  112. //因为这个类是提供给Stream使用的,因此可以直接用Stream,下面的代码作用等同上面,但进行了并发优化
  113. Stream<String> parallelStream = list.parallelStream();
  114. parallelStream.forEach(s -> System.out.print(s += "妹子!!"));
  115. //输出:桥本环奈妹子!!有村架纯妹子!!斋藤飞鸟妹子!! --> 因为引入并发,所有执行顺序会有些不同

集合番@ArrayList一文通(1.8版)黄志鹏kira 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。

本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注