JAva ArrayListとHashMap拡張

ネット上で「ArrayList拡張メカニズム」を検索すると、多くのコンテンツが見つかりますが、ブログを何度も見てみると、いくつかの文章で説明されている知識点が同期していないことがわかります.ここで可能なのは、JDKバージョンが異なり、JDK 6とJDK 7+の内容が異なるためです.

ArrayList

JDK6

// JDK6     
public void ensureCapacity(int minCapacity) {  
    modCount++;  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {  
        Object oldData[] = elementData;  
        int newCapacity = (oldCapacity * 3)/2 + 1;  
            if (newCapacity < minCapacity)  
                newCapacity = minCapacity;  
      // minCapacity is usually close to size, so this is a win:  
      elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
}  

//        10
public ArrayList() {  
    this(10);  
} 

JDK7+

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
//      ，     1.5 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

/** JDK7+          0，    10 
 *，       ，   add         ，      10  ，
 *       ，            ，   0，    ，   10
 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
//       ，           ，
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

HashMap

JDK7:

jdk 7をインストールしていない環境では、他の人の結論を引用します:-容量デフォルト16、負荷因子デフォルト0.75-初回拡張が:数が容量より大きい場合拡張;2回目以降は、容量*負荷係数よりも数が多い場合に拡張します.

JDK 8:(後で補足しますが、一部はビット演算で、JDK 8の具体的な状況はまだ完全に理解していません)

まとめ:

拡張は実は配列の複製であり、古い配列を新しい配列に複製するには、配列の拡張をできるだけ減らすことが性能の最適化に必要である.

配列容量を知っている場合は、インスタンス化時に容量を指定する必要があります.

参照先:

ArrayList実装原理およびjdk 1.6とjdk 1.7での実装の違い

Java 8シリーズの再認識HashMap

http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-April/015585.html

【図解JDKソース】HashMapの容量サイズ増大原理(JDK 1.6/1.7/1.8)

jdk1.8.0_45ソースコード解読——HashMapの実現