一点一点看JDK源码（三）java.util.ArrayList 前偏-白红宇

一点一点看JDK源码（三）java.util.ArrayList 前偏
阅读量：7069 次
发布时间：2019-06-28
本文共 34020 字，大约阅读时间需要 113 分钟。
一点一点看JDK源码（三）java.util.ArrayList
liuyuhang原创，未经允许禁止转载
本文举例使用的是JDK8的API
1 public class ArrayList
     
       extends AbstractList
      
        implements List
       
        , RandomAccess, Cloneable, java.io.Serializable{   2     /**   3      * 序列化版本号   4      */   5     private static final long serialVersionUID = 8683452581122892189L;   6     /**   7      * 默认容量。   8      */   9     private static final int DEFAULT_CAPACITY = 10;  10   11     /**  12      * 以object数组作为类内共享实例容器。  13      */  14     private static final Object[] EMPTY_ELEMENTDATA = {};  15   16     /**  17      * 以object数组作为类内共享实例容器，使用默认容量实例化时使用。  18      */  19     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  20   21     /**  22      * 以object数组作为容器缓自排序冲数组，注意没有private关键字，用于排序，当地一个元素添加的时候将转为默认容量  23      */  24     transient Object[] elementData; // non-private to simplify nested class access  25   26     /**  27      * 缓存的size大小，  28      */  29     private int size;  30   31     /**  32      * 带参构造，手动设置容器初始大小，若实例化时能确定大小，最好别使用默认扩展容量，将提高运行效率  33      */  34     public ArrayList(int initialCapacity) {  35         if (initialCapacity > 0) {  36             this.elementData = new Object[initialCapacity]; //使用自排序缓冲数组  37         } else if (initialCapacity == 0) {  38             this.elementData = EMPTY_ELEMENTDATA; //使用默认数组  39         } else {  40             throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); //容量扩充参数异常  41         }  42     }  43   44     /**  45      * 无参构造，使用默认容器初始化大小  46      */  47     public ArrayList() {  48         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  49     }  50   51     /**  52      * 带参构造器,将参数集合用数组工具类转成数组,并存入缓冲数组,对缓冲数组进行校验.  53 * 若转换后的数组并非object数组（内嵌套无法直接引用情况下），则使用数组工具类将该数组使用深度拷贝  54      */  55     public ArrayList(Collection
         c) {  56         elementData = c.toArray();  57         if ((size = elementData.length) != 0) {  58             // c.toArray might (incorrectly) not return Object[] (see 6260652)  59             if (elementData.getClass() != Object[].class)  60                 elementData = Arrays.copyOf(elementData, size, Object[].class);  61         } else {  62             // replace with empty array.  63             this.elementData = EMPTY_ELEMENTDATA;  64         }  65     }  66   67     /**  68      * 去除多余的数组申请空间，在内存紧张时会用到  69      */  70     public void trimToSize() {  71         modCount++;//修改次数  72         if (size < elementData.length) {  73             elementData = (size == 0)  74               ? EMPTY_ELEMENTDATA  75               : Arrays.copyOf(elementData, size);  76         }  77     }  78   79     /**  80      * 对底层缓冲数组进行扩容的优化方法,如果已知该ArrayList容量,则可执行一次性扩容,  81      * 否则将在数组add的过程中进行动态扩容,效率较低  82      */  83     public void ensureCapacity(int minCapacity) {  84         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;  85         if (minCapacity > minExpand) {  86             ensureExplicitCapacity(minCapacity);  87         }  88     }  89     /**  90      * 重新计算ArrayList的size,在使用构造和扩容时调用  91      */  92     private static int calculateCapacity(Object[] elementData, int minCapacity) {  93         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  94             return Math.max(DEFAULT_CAPACITY, minCapacity);  95         }  96         return minCapacity;  97     }  98   99     /** 100      * 被add调用,内部调用calculatecapacity,用于扩容 101      */ 102     private void ensureCapacityInternal(int minCapacity) { 103         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 104     } 105  106     /** 107      * 被ensureCapacity调用,内部调用calculatecapacity,用于扩容或优化 108      */ 109     private void ensureExplicitCapacity(int minCapacity) { 110         modCount++; 111         // overflow-conscious code 112         if (minCapacity - elementData.length > 0) 113             grow(minCapacity); 114     } 115  116     /** 117      * 目标分配数组的容器大小,最大值要小于Integer.MAX_VALUE-8 118      */ 119     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 120  121     /** 122      * 扩容 123      */ 124     private void grow(int minCapacity) { 125         int oldCapacity = elementData.length; //原容量 126         int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量,扩容1.5倍,自查>>位运算 127         if (newCapacity - minCapacity < 0) //容量不足,则扩容 128             newCapacity = minCapacity; 129         if (newCapacity - MAX_ARRAY_SIZE > 0) //扩容超支,使用最大容 130             newCapacity = hugeCapacity(minCapacity); 131         // minCapacity is usually close to size, so this is a win: 132         elementData = Arrays.copyOf(elementData, newCapacity); 133     } 134 /** 135      * 被grow方法调用,扩容为最大 136      */ 137     private static int hugeCapacity(int minCapacity) { 138         if (minCapacity < 0) //参数错误,抛出异常 139             throw new OutOfMemoryError(); 140         return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; //返回最大容量 141     } 142  143     /** 144      * 获取当前size 145      */ 146     public int size() { 147         return size; 148     } 149  150     /** 151      * 判断当前是size是否为0,容器是否为空 152      */ 153     public boolean isEmpty() { 154         return size == 0; 155     } 156  157     /** 158      * 判断是否包含元素o,返回该元素的index是否大于等于0的判断,是为包含,否为不包含 159      */ 160     public boolean contains(Object o) { 161         return indexOf(o) >= 0; 162     } 163  164     /** 165      * 获取查询元素的index,若备查元素为null,则寻找空元素,返回index 166      * 若备查元素不为null，则使用equal判断该元素是否存在，并返回index 167      * 不存在则返回-1 168      * 被contains调用 169      */ 170     public int indexOf(Object o) { 171         if (o == null) { 172             for (int i = 0; i < size; i++) 173                 if (elementData[i]==null) 174                     return i; 175         } else { 176             for (int i = 0; i < size; i++) 177                 if (o.equals(elementData[i])) 178                     return i; 179         } 180         return -1; 181     } 182  183     /** 184      * 倒叙查询第一个出现的被查元素 185      */ 186     public int lastIndexOf(Object o) { 187         if (o == null) { 188             for (int i = size-1; i >= 0; i--) 189                 if (elementData[i]==null) 190                     return i; 191         } else { 192             for (int i = size-1; i >= 0; i--) 193                 if (o.equals(elementData[i])) 194                     return i; 195         } 196         return -1; 197     } 198  199     /** 200      * clone本实例数组，返回类型为Object，使用根类意为可转换为其他格式容器 201      */ 202     public Object clone() { 203         try { 204             ArrayList
         v = (ArrayList
        ) super.clone(); 205             v.elementData = Arrays.copyOf(elementData, size); 206             v.modCount = 0; 207             return v; 208         } catch (CloneNotSupportedException e) { 209             throw new InternalError(e); 210         } 211     } 212  213     /** 214      * 将本实例转换为object数组，调用数组工具类拷贝 215      */ 216     public Object[] toArray() { 217         return Arrays.copyOf(elementData, size); 218     } 219  220     /** 221      * 将本实例转换为指定类型数组，调用数组工具类拷贝，并获得泛型的Class 222      */ 223     @SuppressWarnings("unchecked") 224     public 
        
          T[] toArray(T[] a) { 225         if (a.length < size) 226             // Make a new array of a's runtime type, but my contents: 227             return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 228         System.arraycopy(elementData, 0, a, 0, size); 229         if (a.length > size) 230             a[size] = null; 231         return a; 232     } 233  234     /** 235      * 获取指定index的元素，被get方法调用，get方法内进行check，util包内的类可调用 236      */ 237     @SuppressWarnings("unchecked") 238     E elementData(int index) { 239         return (E) elementData[index]; 240     } 241  242     /** 243      * 获取指定元素的方法，使用rangeCheck进行index的check 244      */ 245     public E get(int index) { 246         rangeCheck(index); 247         return elementData(index); 248     } 249  250     /** 251      * 将指定index的值设置为指定值，使用rangeCheck进行index的check 252      */ 253     public E set(int index, E element) { 254         rangeCheck(index); 255         E oldValue = elementData(index); 256         elementData[index] = element; 257         return oldValue; 258     } 259  260     /** 261      * 容量+1的，在容器尾部添加元素 262      */ 263     public boolean add(E e) { 264         ensureCapacityInternal(size + 1);  // Increments modCount!! 265         elementData[size++] = e; // 这个在数组尾部追加元素的写法很好用,前提是扩容 266         return true; // 有返回值的,应当接收 267     } 268  269     /** 270      * 在指定index添加指定元素,首先使用rangeCheckForAdd进行check,为保证数组操作的正确性,使用arraycopy来移动数组元素 271      */ 272     public void add(int index, E element) { 273         rangeCheckForAdd(index); 274         ensureCapacityInternal(size + 1);  // Increments modCount!! 275         System.arraycopy(elementData, index, elementData, index + 1, size - index); 276         elementData[index] = element; 277         size++; 278     } 279  280     /** 281      * remove指定index的元素,并重构本实例 282      */ 283     public E remove(int index) { 284         rangeCheck(index); 285         modCount++; 286         E oldValue = elementData(index); 287         int numMoved = size - index - 1; 288         if (numMoved > 0) 289             System.arraycopy(elementData, index+1, elementData, index, numMoved); 290         elementData[--size] = null; // clear to let GC do its work 291         return oldValue; 292     } 293  294     /** 295      * remove指定元素,返回是否找到该元素并移除成功的boolean标记 296      */ 297     public boolean remove(Object o) { 298         if (o == null) { 299             for (int index = 0; index < size; index++) 300                 if (elementData[index] == null) { 301                     fastRemove(index); 302                     return true; 303                 } 304         } else { 305             for (int index = 0; index < size; index++) 306                 if (o.equals(elementData[index])) { 307                     fastRemove(index); 308                     return true; 309                 } 310         } 311         return false; 312     } 313  314     /* 315      * 内部使用,快速移除指定index的元素 316      */ 317     private void fastRemove(int index) { 318         modCount++; 319         int numMoved = size - index - 1; 320         if (numMoved > 0) 321             System.arraycopy(elementData, index+1, elementData, index, 322                              numMoved); 323         elementData[--size] = null; // clear to let GC do its work 324     } 325  326     /** 327      * 清除本实例内部的所有元素,加速gc回收 328      */ 329     public void clear() { 330         modCount++; 331         // clear to let GC do its work 332         for (int i = 0; i < size; i++) 333             elementData[i] = null; 334         size = 0; 335     } 336  337     /** 338      * 添加指定集合到本实例中Object数组末尾 339      */ 340     public boolean addAll(Collection
          c) { 341         Object[] a = c.toArray(); 342         int numNew = a.length; 343         ensureCapacityInternal(size + numNew);  // Increments modCount 344         System.arraycopy(a, 0, elementData, size, numNew); 345         size += numNew; 346         return numNew != 0; 347     } 348  349     /** 350      * 从指定元素开始添加指定集合到本实例 351      */ 352     public boolean addAll(int index, Collection
          c) { 353         rangeCheckForAdd(index); 354         Object[] a = c.toArray(); 355         int numNew = a.length; 356         ensureCapacityInternal(size + numNew);  // Increments modCount 357         int numMoved = size - index; 358         if (numMoved > 0) 359             System.arraycopy(elementData, index, elementData, index + numNew, 360                              numMoved); 361         System.arraycopy(a, 0, elementData, index, numNew); 362         size += numNew; 363         return numNew != 0; 364     } 365  366     /** 367      * 本类和子类可使用,移除指定范围的index的所有元素 368      */ 369     protected void removeRange(int fromIndex, int toIndex) { 370         modCount++; 371         int numMoved = size - toIndex; 372         System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); 373         int newSize = size - (toIndex-fromIndex); 374         for (int i = newSize; i < size; i++) { 375             elementData[i] = null; 376         } 377         size = newSize; 378     } 379  380     /** 381      * 内部的index超限检测方法,当index超过size的时候,抛出index超限异常,在本类中被多次调用 382      */ 383     private void rangeCheck(int index) { 384         if (index >= size) 385             throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 386     } 387  388     /** 389      * 同上,但是在add和addAll中专用 390      */ 391     private void rangeCheckForAdd(int index) { 392         if (index > size || index < 0) 393             throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 394     } 395  396     /** 397      * index超限抛异常时使用,用来提示size和index的值 398      */ 399     private String outOfBoundsMsg(int index) { 400         return "Index: "+index+", Size: "+size; 401     } 402  403     /** 404      * 从本类实例中移除指定集合中所有元素的方法,返回值应接收 405      */ 406     public boolean removeAll(Collection
          c) { 407         Objects.requireNonNull(c); 408         return batchRemove(c, false); 409     } 410  411     /** 412      * 从本类实例中保留指定集合中所有元素的方法,与removeAll相反 413      */ 414     public boolean retainAll(Collection
          c) { 415         Objects.requireNonNull(c); 416         return batchRemove(c, true); 417     } 418  419     /** 420      * 内部调用,如果参数集合发生更改,则返回true 421      */ 422     private boolean batchRemove(Collection
          c, boolean complement) { 423         final Object[] elementData = this.elementData; //获取本实例的所有元素 424         int r = 0, w = 0; //r用于遍历,w用于记录相同元素的数量,也用于记录容器的扩容标记 425         boolean modified = false; //标志位 426         try { 427             for (; r < size; r++) 428                 if (c.contains(elementData[r]) == complement) //判断该元素是否被包含 429                     elementData[w++] = elementData[r]; //包含则w++ 430         } finally { 431             // Preserve behavioral compatibility with AbstractCollection, 432             // even if c.contains() throws. 433             if (r != size) {
   //集合有变化 434                 System.arraycopy(elementData, r, elementData, w, size - r); 435                 w += size - r; 436             } 437             if (w != size) {
   //容量不相等 438                 // clear to let GC do its work 439                 for (int i = w; i < size; i++) 440                     elementData[i] = null; 441                 modCount += size - w; 442                 size = w; 443                 modified = true; //容量有变化,说明有交集,则返回true 444             } 445         } 446         return modified; 447     } 448  449     /** 450      * 将本实例对象写入流中,实际上只写入了modCount,size和element[i],其余的内容在实例化时候是不必要的,或者可恢复的 451      */ 452     private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ 453         // Write out element count, and any hidden stuff 454         int expectedModCount = modCount; 455         s.defaultWriteObject(); 456         // Write out size as capacity for behavioural compatibility with clone() 457         s.writeInt(size); 458         // Write out all elements in the proper order. 459         for (int i=0; i
         
           0) { 478             // be like clone(), allocate array based upon size not capacity 479             int capacity = calculateCapacity(elementData, size); 480             SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); 481             ensureCapacityInternal(size); 482             Object[] a = elementData; 483             // Read in all elements in the proper order. 484             for (int i=0; i
          
            listIterator(int index) { 494 if (index < 0 || index > size) 495 throw new IndexOutOfBoundsException("Index: "+index); 496 return new ListItr(index); 497 } 498 499 /** 500 * 获得本实例的默认List迭代器 501 */ 502 public ListIterator
           
             listIterator() { 503 return new ListItr(0); 504 } 505 506 /** 507 * 获得本实例的默认迭代器 508 */ 509 public Iterator
            
              iterator() { 510 return new Itr(); 511 } 512 513 /** 514 * 内部使用的迭代器,重写自Iterator接口,为内部类 515 */ 516 private class Itr implements Iterator
             
               { 517 int cursor; // index of next element to return 迭代器指针 518 int lastRet = -1; // index of last element returned; -1 if no such 末尾标记 519 int expectedModCount = modCount; 520 Itr() {} 521 public boolean hasNext() { 522 return cursor != size; 523 } 524 @SuppressWarnings("unchecked") 525 //重写迭代器提供next方法,可能unchecked报错 526 public E next() { 527 checkForComodification(); 528 int i = cursor; 529 if (i >= size) 530 throw new NoSuchElementException(); 531 Object[] elementData = ArrayList.this.elementData; 532 if (i >= elementData.length) 533 throw new ConcurrentModificationException(); 534 cursor = i + 1; 535 return (E) elementData[lastRet = i]; 536 } 537 //重写迭代器提供remove方法 538 public void remove() { 539 if (lastRet < 0) 540 throw new IllegalStateException(); 541 checkForComodification(); 542 try { 543 ArrayList.this.remove(lastRet); 544 cursor = lastRet; 545 lastRet = -1; 546 expectedModCount = modCount; 547 } catch (IndexOutOfBoundsException ex) { 548 throw new ConcurrentModificationException(); 549 } 550 } 551 552 @Override 553 @SuppressWarnings("unchecked")//重写迭代器接口下的forEachRemaining方法,可能unchecked报错,可使用lambda迭代 554 public void forEachRemaining(Consumer
               consumer) { 555 Objects.requireNonNull(consumer); 556 final int size = ArrayList.this.size; 557 int i = cursor; 558 if (i >= size) { 559 return; 560 } 561 final Object[] elementData = ArrayList.this.elementData; 562 if (i >= elementData.length) { 563 throw new ConcurrentModificationException(); 564 } 565 while (i != size && modCount == expectedModCount) { 566 consumer.accept((E) elementData[i++]); 567 } 568 // update once at end of iteration to reduce heap write traffic 569 cursor = i; 570 lastRet = i - 1; 571 checkForComodification(); 572 } 573 //校验modCount修改次数的方法 574 final void checkForComodification() { 575 if (modCount != expectedModCount) 576 throw new ConcurrentModificationException(); 577 } 578 } 579 580 /** 581 * 另一个内部提供ListItr的迭代器,继承自上述内部类,实现ListIteraotr接口,本内部类将允许使用固定长度的迭代器 582 */ 583 private class ListItr extends Itr implements ListIterator
              
                { 584 ListItr(int index) { 585 super(); 586 cursor = index; 587 } 588 //是否有前一个元素 589 public boolean hasPrevious() { 590 return cursor != 0; 591 } 592 //获取下一个index 593 public int nextIndex() { 594 return cursor; 595 } 596 //获取前一个index 597 public int previousIndex() { 598 return cursor - 1; 599 } 600 //获取前一个元素,可能因为unchecked报错 601 @SuppressWarnings("unchecked") 602 public E previous() { 603 checkForComodification(); 604 int i = cursor - 1; 605 if (i < 0) 606 throw new NoSuchElementException(); 607 Object[] elementData = ArrayList.this.elementData; 608 if (i >= elementData.length) 609 throw new ConcurrentModificationException(); 610 cursor = i; 611 return (E) elementData[lastRet = i]; 612 } 613 //对迭代器内当index的元素设置为指定值 614 public void set(E e) { 615 if (lastRet < 0) 616 throw new IllegalStateException(); 617 checkForComodification(); 618 try { 619 ArrayList.this.set(lastRet, e); 620 } catch (IndexOutOfBoundsException ex) { 621 throw new ConcurrentModificationException(); 622 } 623 } 624 625 public void add(E e) { 626 checkForComodification(); 627 628 try { 629 int i = cursor; 630 ArrayList.this.add(i, e); 631 cursor = i + 1; 632 lastRet = -1; 633 expectedModCount = modCount; 634 } catch (IndexOutOfBoundsException ex) { 635 throw new ConcurrentModificationException(); 636 } 637 } 638 } 639 640 /** 641 * 从fromIndex到toIndex拆分数组，内部调用subListRangeCheck方法对本实例进行check 642 */ 643 public List
               
                 subList(int fromIndex, int toIndex) { 644 subListRangeCheck(fromIndex, toIndex, size); 645 return new SubList(this, 0, fromIndex, toIndex); //调用复写的内部类,十分巨大 646 } 647 /** 648 * 被内部调用，进行拆分时的参数check校验 649 */ 650 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 651 if (fromIndex < 0) 652 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 653 if (toIndex > size) 654 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 655 if (fromIndex > toIndex) 656 throw new IllegalArgumentException("fromIndex(" + fromIndex +") > toIndex(" + toIndex + ")"); 657 } 658 659 /** 660 * 重写继承的AbstractList中的SubList类,对于该类提供和list基本相同的功能进行重新封装 661 */ 662 private class SubList extends AbstractList
                
                  implements RandomAccess { 663 private final AbstractList
                 
                   parent; 664 private final int parentOffset; 665 private final int offset; 666 int size; 667 //构造 668 SubList(AbstractList
                  
                    parent, 669 int offset, int fromIndex, int toIndex) { 670 this.parent = parent; 671 this.parentOffset = fromIndex; 672 this.offset = offset + fromIndex; 673 this.size = toIndex - fromIndex; 674 this.modCount = ArrayList.this.modCount; 675 } 676 //内部类的set方法 677 public E set(int index, E e) { 678 rangeCheck(index); 679 checkForComodification(); 680 E oldValue = ArrayList.this.elementData(offset + index); 681 ArrayList.this.elementData[offset + index] = e; 682 return oldValue; 683 } 684 //内部类的get方法 685 public E get(int index) { 686 rangeCheck(index); 687 checkForComodification(); 688 return ArrayList.this.elementData(offset + index); 689 } 690 //内部类的size方法 691 public int size() { 692 checkForComodification();//复用 693 return this.size; 694 } 695 //内部类的add方法 696 public void add(int index, E e) { 697 rangeCheckForAdd(index); //复用 698 checkForComodification();//复用 699 parent.add(parentOffset + index, e); 700 this.modCount = parent.modCount; 701 this.size++; 702 } 703 //内部类的remove方法 704 public E remove(int index) { 705 rangeCheck(index); //复用 706 checkForComodification();//复用 707 E result = parent.remove(parentOffset + index); 708 this.modCount = parent.modCount; 709 this.size--; 710 return result; 711 } 712 //从本内部类实例中移除指定范围的元素并重构本实例 713 protected void removeRange(int fromIndex, int toIndex) { 714 checkForComodification();//复用 715 parent.removeRange(parentOffset + fromIndex, 716 parentOffset + toIndex); //使用父类 717 this.modCount = parent.modCount; 718 this.size -= toIndex - fromIndex; 719 } 720 //内部类的addAll 721 public boolean addAll(Collection
                    c) { 722 return addAll(this.size, c); 723 } 724 //内部类的addAll,从指定index开始 725 public boolean addAll(int index, Collection
                    c) { 726 rangeCheckForAdd(index); //复用 727 int cSize = c.size(); 728 if (cSize==0) 729 return false; 730 checkForComodification();//复用 731 parent.addAll(parentOffset + index, c); 732 this.modCount = parent.modCount; 733 this.size += cSize; 734 return true; 735 } 736 //内部类的迭代器 737 public Iterator
                   
                     iterator() { 738 return listIterator(); 739 } 740 //内部类的迭代器,被内部调用 741 public ListIterator
                    
                      listIterator(final int index) { 742 checkForComodification();//复用 743 rangeCheckForAdd(index); //复用 744 final int offset = this.offset; 745 return new ListIterator
                     
                      () { 746 int cursor = index; 747 int lastRet = -1; 748 int expectedModCount = ArrayList.this.modCount; 749 public boolean hasNext() { 750 return cursor != SubList.this.size; 751 } 752 //内部类的迭代器的next 753 @SuppressWarnings("unchecked") 754 public E next() { 755 checkForComodification(); 756 int i = cursor; 757 if (i >= SubList.this.size) 758 throw new NoSuchElementException(); 759 Object[] elementData = ArrayList.this.elementData; 760 if (offset + i >= elementData.length) 761 throw new ConcurrentModificationException(); 762 cursor = i + 1; 763 return (E) elementData[offset + (lastRet = i)]; 764 } 765 //内部类的迭代器的判断是否有前一个元素 766 public boolean hasPrevious() { 767 return cursor != 0; 768 } 769 //内部类的获取前一个元素 770 @SuppressWarnings("unchecked") 771 public E previous() { 772 checkForComodification(); 773 int i = cursor - 1; 774 if (i < 0) 775 throw new NoSuchElementException(); 776 Object[] elementData = ArrayList.this.elementData; 777 if (offset + i >= elementData.length) 778 throw new ConcurrentModificationException(); 779 cursor = i; 780 return (E) elementData[offset + (lastRet = i)]; 781 } 782 //剩余元素的迭代,可以使用lambda表达式进行遍历 783 @SuppressWarnings("unchecked") 784 public void forEachRemaining(Consumer
                       consumer) { 785 Objects.requireNonNull(consumer); 786 final int size = SubList.this.size; 787 int i = cursor; 788 if (i >= size) { 789 return; 790 } 791 final Object[] elementData = ArrayList.this.elementData; 792 if (offset + i >= elementData.length) { 793 throw new ConcurrentModificationException(); 794 } 795 while (i != size && modCount == expectedModCount) { 796 consumer.accept((E) elementData[offset + (i++)]); 797 } 798 // update once at end of iteration to reduce heap write traffic 799 lastRet = cursor = i; 800 checkForComodification(); 801 } 802 //内部类的迭代器中获取下一个元素的index 803 public int nextIndex() { 804 return cursor; 805 } 806 //内部类的迭代器中获取上一个元素的index 807 public int previousIndex() { 808 return cursor - 1; 809 } 810 //内部类的迭代器中移除当前元素 811 public void remove() { 812 if (lastRet < 0) 813 throw new IllegalStateException(); 814 checkForComodification(); 815 try { 816 SubList.this.remove(lastRet); 817 cursor = lastRet; 818 lastRet = -1; 819 expectedModCount = ArrayList.this.modCount; 820 } catch (IndexOutOfBoundsException ex) { 821 throw new ConcurrentModificationException(); 822 } 823 } 824 //内部类的迭代器对当前元素设置成指定值 825 public void set(E e) { 826 if (lastRet < 0) 827 throw new IllegalStateException(); 828 checkForComodification(); 829 try { 830 ArrayList.this.set(offset + lastRet, e); 831 } catch (IndexOutOfBoundsException ex) { 832 throw new ConcurrentModificationException(); 833 } 834 } 835 //内部类的迭代器中add方法添加元素到迭代器末尾 836 public void add(E e) { 837 checkForComodification(); 838 try { 839 int i = cursor; 840 SubList.this.add(i, e); 841 cursor = i + 1; 842 lastRet = -1; 843 expectedModCount = ArrayList.this.modCount; 844 } catch (IndexOutOfBoundsException ex) { 845 throw new ConcurrentModificationException(); 846 } 847 } 848 //内部类的modCount校验 849 final void checkForComodification() { 850 if (expectedModCount != ArrayList.this.modCount) 851 throw new ConcurrentModificationException(); 852 } 853 }; 854 } 855 856 /** 857 * 内部类的拆分list的方法 858 */ 859 public List
                      
                        subList(int fromIndex, int toIndex) { 860 subListRangeCheck(fromIndex, toIndex, size); 861 return new SubList(this, offset, fromIndex, toIndex); 862 } 863 /** 864 * 内部类的index越界检查方法 865 */ 866 private void rangeCheck(int index) { 867 if (index < 0 || index >= this.size) 868 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 869 } 870 /** 871 * 同上,add和addAll专用 872 */ 873 private void rangeCheckForAdd(int index) { 874 if (index < 0 || index > this.size) 875 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 876 } 877 /** 878 * 内部类rangeCheckForAdd中抛异常调用,写明index和size 879 */ 880 private String outOfBoundsMsg(int index) { 881 return "Index: "+index+", Size: "+this.size; 882 } 883 /** 884 * 内部类的modCount校验 885 */ 886 private void checkForComodification() { 887 if (ArrayList.this.modCount != this.modCount) 888 throw new ConcurrentModificationException(); 889 } 890 /** 891 * 内部类的分离迭代器函数,调用ArrayList的ArrayListSpliterator内部类的构造器 892 */ 893 public Spliterator
                       
                         spliterator() { 894 checkForComodification(); 895 return new ArrayListSpliterator
                        
                         (ArrayList.this, offset, offset + this.size, this.modCount); 896 } 897 } 898 899 /** 900 * 重写继承的forEach方法,用于迭代 901 */ 902 @Override 903 public void forEach(Consumer
                          action) { 904 Objects.requireNonNull(action); 905 final int expectedModCount = modCount; 906 @SuppressWarnings("unchecked") 907 final E[] elementData = (E[]) this.elementData; 908 final int size = this.size; 909 for (int i=0; modCount == expectedModCount && i < size; i++) { 910 action.accept(elementData[i]); 911 } 912 if (modCount != expectedModCount) { 913 throw new ConcurrentModificationException(); 914 } 915 } 916 917 /** 918 * jd1.8更新 919 * 重写自父类,分离数组,默认使用本类内容,从0-末尾, 920 */ 921 @Override 922 public Spliterator
                         
                           spliterator() { 923 return new ArrayListSpliterator<>(this, 0, -1, 0); 924 } 925 926 /** 927 * jd1.8更新 928 * 重写自父类,实现Spliterator接口 929 * 本类用于分离ArrayList,前提是ArrayList暂定是不变的,否则将可能出现线程错误 930 */ 931 static final class ArrayListSpliterator
                          
                            implements Spliterator
                           
                             { 932 933 private final ArrayList
                            
                              list; 934 private int index; // current index, modified on advance/split 935 private int fence; // -1 until used; then one past last index 936 private int expectedModCount; // initialized when fence set 937 938 /** 939 * 内部类ArrayListSpliterator的构造器 940 */ 941 ArrayListSpliterator(ArrayList
                             
                               list, int origin, int fence, 942 int expectedModCount) { 943 this.list = list; // OK if null unless traversed 944 this.index = origin; 945 this.fence = fence; 946 this.expectedModCount = expectedModCount; 947 } 948 /** 949 * 内部类ArrayListSpliterator中很多方法都使用的初始化方法 950 */ 951 private int getFence() { // initialize fence to size on first use 952 int hi; // (a specialized variant appears in method forEach) 953 ArrayList
                              
                                lst; 954 if ((hi = fence) < 0) { 955 if ((lst = list) == null) 956 hi = fence = 0; 957 else { 958 expectedModCount = lst.modCount; 959 hi = fence = lst.size; 960 } 961 } 962 return hi; 963 } 964 /** 965 * 内部类ArrayListSpliterator的拆分arraylist方法,不保证结果正确 966 */ 967 public ArrayListSpliterator
                               
                                 trySplit() { 968 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 969 return (lo >= mid) ? null : // divide range in half unless too small 970 new ArrayListSpliterator
                                
                                 (list, lo, index = mid, expectedModCount); 971 } 972 973 /** 974 * 内部类ArrayListSpliterator的预拆分?尝试是否能够拆分 975 */ 976 public boolean tryAdvance(Consumer
                                  action) { 977 if (action == null) 978 throw new NullPointerException(); 979 int hi = getFence(), i = index; 980 if (i < hi) { 981 index = i + 1; 982 @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; 983 action.accept(e); 984 if (list.modCount != expectedModCount) 985 throw new ConcurrentModificationException(); 986 return true; 987 } 988 return false; 989 } 990 991 /** 992 * 内部类ArrayListSpliterator迭代 993 */ 994 public void forEachRemaining(Consumer
                                  action) { 995 int i, hi, mc; // hoist accesses and checks from loop 996 ArrayList
                                 
                                   lst; Object[] a; 997 if (action == null) 998 throw new NullPointerException(); 999 if ((lst = list) != null && (a = lst.elementData) != null) {1000 if ((hi = fence) < 0) {1001 mc = lst.modCount;1002 hi = lst.size;1003 }1004 else1005 mc = expectedModCount;1006 if ((i = index) >= 0 && (index = hi) <= a.length) {1007 for (; i < hi; ++i) {1008 @SuppressWarnings("unchecked") E e = (E) a[i];1009 action.accept(e);1010 }1011 if (lst.modCount == mc)1012 return;1013 }1014 }1015 throw new ConcurrentModificationException();1016 }1017 //内部类ArrayListSpliterator的size预估1018 public long estimateSize() {1019 return (long) (getFence() - index);1020 }1021 1022 //分离参数初始化1023 public int characteristics() {1024 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;1025 }1026 }1027 1028 /**1029 * 重写自父类,使用重写的filter接口进行筛选,符合条件的则移除1030 */1031 @Override1032 public boolean removeIf(Predicate
                                   filter) {1033 Objects.requireNonNull(filter);1034 // figure out which elements are to be removed1035 // any exception thrown from the filter predicate at this stage1036 // will leave the collection unmodified1037 int removeCount = 0;1038 final BitSet removeSet = new BitSet(size);1039 final int expectedModCount = modCount;1040 final int size = this.size;1041 for (int i=0; modCount == expectedModCount && i < size; i++) {1042 @SuppressWarnings("unchecked")1043 final E element = (E) elementData[i];1044 if (filter.test(element)) {1045 removeSet.set(i);1046 removeCount++;1047 }1048 }1049 if (modCount != expectedModCount) {1050 throw new ConcurrentModificationException();1051 }1052 1053 // shift surviving elements left over the spaces left by removed elements1054 final boolean anyToRemove = removeCount > 0;1055 if (anyToRemove) {1056 final int newSize = size - removeCount;1057 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {1058 i = removeSet.nextClearBit(i);1059 elementData[j] = elementData[i];1060 }1061 for (int k=newSize; k < size; k++) {1062 elementData[k] = null; // Let gc do its work1063 }1064 this.size = newSize;1065 if (modCount != expectedModCount) {1066 throw new ConcurrentModificationException();1067 }1068 modCount++;1069 }1070 return anyToRemove;1071 }1072 1073 /**1074 * 重写自父类,使用重写的operator接口进行替代本实例中匹配的元素1075 */1076 @Override1077 @SuppressWarnings("unchecked")1078 public void replaceAll(UnaryOperator
                                  
                                    operator) {1079 Objects.requireNonNull(operator);1080 final int expectedModCount = modCount;1081 final int size = this.size;1082 for (int i=0; modCount == expectedModCount && i < size; i++) {1083 elementData[i] = operator.apply((E) elementData[i]);1084 }1085 if (modCount != expectedModCount) {1086 throw new ConcurrentModificationException();1087 }1088 modCount++;1089 }1090 1091 /**1092 * 重写自父类,使用comparator接口对本实例进行排序1093 */1094 @Override1095 @SuppressWarnings("unchecked")1096 public void sort(Comparator
                                    c) {1097 final int expectedModCount = modCount;1098 Arrays.sort((E[]) elementData, 0, size, c);1099 if (modCount != expectedModCount) {1100 throw new ConcurrentModificationException();1101 }1102 modCount++;1103 }1104 }