JDK 1.8ソース読みJava.util.ArrayList


JDK 1.8ソース読みJava.util.ArrayList
文書ディレクトリ
  • JDK 1.8ソース読みJava.util.ArrayList
  • コンストラクタ方法
  • 無パラメトリックコンストラクタ
  • 有パラメトリックコンストラクタ
  • addメソッド
  • removeメソッド
  • contians法とindexOf法
  • cloneメソッド
  • trimToSizeメソッド
  • 最大容量

  • コンストラクタメソッド
    パラメトリックコンストラクタなし
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
         };
    transient Object[] elementData; // non-private to simplify nested class access
    
    //  elementData       。
    //        ,           ,            10。
    public ArrayList() {
         
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    パラメトリックコンストラクタ
    private static final Object[] EMPTY_ELEMENTDATA = {
         };
    
    //            。
    public ArrayList(int initialCapacity) {
         
        if (initialCapacity > 0) {
         
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
         
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
         
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    //       ArrayList   
    public ArrayList(Collection<? extends E> c) {
         
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
         
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
         
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

    addメソッド
    手順:
  • は、intがInteger
    //    cache     ,int     [-128,127]
    // cache[0]=-128
    public static Integer valueOf(int i) {
           
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }
    
  • に変換するなど、挿入された基礎データ型をパッケージ化する.
  • データを挿入する前に、配列容量が十分であることを確保する必要がある
    private int size;
    transient Object[] elementData; // non-private to simplify nested class access
    
    //   ensureCapacityInternal          ,         
    // size  ArrayList           
    public boolean add(E e) {
           
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    //           。
    //  index               
    public void add(int index, E element) {
           
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    // elementData   ArrayList     
    private void ensureCapacityInternal(int minCapacity) {
           
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
  • .
  • 計算に必要な容量
    private static final int DEFAULT_CAPACITY = 10;
    
    //          elementData   minCapacity,          。
    //   ArrayList     ,       ,      DEFAULT_CAPACITY,   10
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
           
           if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           
               return Math.max(DEFAULT_CAPACITY, minCapacity);
           }
           return minCapacity;
       }
    
  • 拡張
    protected transient int modCount = 0;
    
    // modeCount      ListArray   +1 ,                 
    //   :             elementData            
    private void ensureExplicitCapacity(int minCapacity) {
           
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
  • が必要かどうかを確認する.
  • 拡張
    //          1.5 ,             ,       。
    //            
    private void grow(int minCapacity) {
           
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //          ,             0
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    は、ステップ2のsize++を実行し続け、要素を配列に入れ、true
  • に戻る.
    removeメソッド
    public E remove(int index) {
         
    	//         
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        //                 
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
    	//         
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }
    
    //     remove
    //         ,        remove     。        check   
    public boolean remove(Object o) {
         
        if (o == null) {
         
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
         
                    fastRemove(index);
                    return true;
                }
        } else {
         
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
         
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    private void fastRemove(int index) {
         
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }
    

    contiansメソッドとindexOfメソッド
    //     boolean,        
    public boolean contains(Object o) {
         
        return indexOf(o) >= 0;
    }
    
    //       ,           
    public int indexOf(Object o) {
         
        if (o == null) {
         
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
         
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    
    //     
    public int lastIndexOf(Object o) {
         
        if (o == null) {
         
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
         
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    

    cloneメソッド
    //    ,          。           ,    v     ,             
    public Object clone() {
         
        try {
         
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
         
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    

    trimToSizeメソッド
    //       ,             。
    //       10,     5   。
    public void trimToSize() {
         
        modCount++;
        if (size < elementData.length) {
         
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
    

    最大容量
    //             ,       Integer.MAX_VALUE-8
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;