天天看點
傳回

Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的對比研究——java集合深入了解1、ArrayList

與JDK1.7相比，JDK1.8對集合做了很多優化，這些優化裡有很多優秀的算法、思想等等值得學習，是以在這裡一一列出，便以後回顧，也希望對讀者有些幫助

我們可以從構造器、擴容機制、增删改查、疊代器、并發修改異常等各個方面來分析

Collection
List

ArrayList

LinkedList

Vecto

Set

HashSet

LinkedHashSet

TreeSet

Map

HashMap

LinkedHashMap

TreeMap

HashTable

Properties

1、ArrayList

構造器

擴容機制

增删改查方法

1.1、構造器

1.1.1、無參構造器

JDK1.7中

/**
* Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this(10);
}

JDK1.8中

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

我們可以看出，在JDK1.7中無參構造器初始化時就執行個體化了一個長度為10的數組；

而在JDK1.8中，無參構造器值引用了一個全局靜态的一個空數組；

這種改變有什麼好處呢？

  1. 首先我們在構造器中就初始化一個數組就好比“餓漢式”的一種設計模式，是以我們可以類比“餓漢式”來分析，“餓漢式”和“懶漢式”的最大差別是：
    1. “餓漢式”是用空間換時間，“懶漢式”是用時間換空間
    2. “餓漢式”是采用預先加載法，調用是反應速度快；“懶漢式”是資源使用率高，但是第一次調用時效率低
    3. 如何選擇？如果單例模式在系統中會經常用到那麼“餓漢式”是一個不錯的選擇，反之用“懶漢式”
    4. 是以我們在執行個體化一個ArrayList的時候，如果經常需要對ArrayList進行增删改就需要提前申請好足夠的容量，反之，就是要空參構造器（飽漢式）

1.1.2、初始化容量構造器

JDK1.7

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

JDK1.8

private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

JDK1.8隻是多出了一些條件判斷，當初始化容量為0的時候，依然隻引用了一個全局靜态空數組，靜态保證全局唯一，提高資源使用率

1.1.3、通過Collection建立ArrayList

JDK1.7

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

JDK1.8

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
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;
    }
}
           
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
  1. JDK1.8相較于JDK1.7還是隻多了一些判斷，但是！！！
  2. 在這個源碼中有一行注釋值得深究，即c.toArray might (incorrectly) not return Object[] (see 6260652)
  3. 那麼，為什麼c.toArray可能傳回的不是一個Object類型的數組呢，我們看ArrayList的源碼中toArray方法傳回的明明就是Object類型的數組呀？
  4. 上面的原因其實就是因為對象的多态性和ArrayList的泛型兩者混合導緻的一種bug

大家可以參考這一片部落格來加以了解：集合源碼中toArray方法的bug

1.2、擴容機制

首先，我們隻有向ArrayList中添加資料的時候，才有可能引發擴容，是以我們從add方法入手分析：

1.2.1、JDK1.7擴容機制 

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal：這個方法就是擴容機制對外暴露的接口，它隐藏了擴容的實作機制，我們無需知道擴容原理，就可直接實作擴容；

private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

modCount這個屬性，是處理并發修改的重要屬性，我們在分析疊代器的時候在仔細深究

在源碼中，隻要是minCapacity，我們都可以了解為是最小需求容量

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 擴容為原來的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果我們擴容（1.5倍）之後的容量還小于最小需求容量，那麼就直接把minCapacity作為容量
    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);
}

無非就是一些條件過濾

1.2.2、JDK1.8擴容機制 

public boolean add(E e) {
    // 我們可以看到JDK1.8中擴容對外暴露的接口與JDK1.7相同
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
           
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

以下方法是計算需求容量（minCapacity）的，無非就是與預設容量10相比，minCapacity < 10 ？ 10 ：minCapacity

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
           
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

至于JDK1.8的grow方法和JDK1.7完全一樣

擴容機制帶來的思想：

  1. 當我們需要實作一個功能的時候，現需要能不能将其分裝起來，實作為一個通用的功能，對外提供公共的接口，這樣我們在之後的功能擴充的時候，就無需在實作這個功能了

1.3、增删改的一些方法

1.3.1、add方法（兩個版本無修改）

我們可以看到将擴容方法封裝，對外暴露接口的好處：

  1. Increments modCount!!，我們隻要調用ensureCapacityInternal方法，就會修改/确定容量，并修改modCount，而且無需知道底層實作了
  2. 因為add方法可能會需要擴容，是以我們就封裝了一個擴容機制，而之後的remove方法，我們也封裝了一個fastRemove方法
  3. 因為add，remove移動，添加，删除數組，可能會導緻空指針、等并發修改異常的産生，是以都需要修改modCount屬性，是以在ensureCapacityInternal和fastRemove中都封裝了modCount++；這個在疊代器中仔細深究，現在隻要留一個心眼 
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
           
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++;
}

以上兩個添加單個元素的方法，無非就是确定容量、移動元素（數組拷貝），size++；判斷下标

public boolean addAll(Collection<? extends E> c) {
    // 這裡我們注意到，它和我們之前構造器中說過toArray可能産生異常，為什麼這個沒有呢？
    // 哈哈，那是因為我們這個方法的形參中使用上限通配符(?)規定了泛型的上限，是以方法内部不可能再産生類型轉換錯誤等異常了
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
           
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

在某個下标處添加、删除元素，無非就是死套路：

  1. 判斷下标合理性
  2. 是否需要擴容（涉及修改modCount）
  3. 移動元素（實際就是數組Copy）
  4. 修改size

1.3.2、remove方法

public boolean remove(Object o)：删除第一次出現的元素

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
}

public E remove(int index)：删除指定位置的元素

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;
}

public boolean removeAll(Collection<?> c)

public boolean removeAll(Collection<?> c) {
    //空值判斷，抛空指針異常
    Objects.requireNonNull(c);
    //batch...: 批量操作，在jdbcTemplate中也有這種方法
    return batchRemove(c, false);
}

// 這個batchRemove方法值得深究一下，removeAll和retainAll兩個方法都調用了這個方法
// 我們先說removeAll調用這個方法的執行流程
// 1.首先removeAll中傳入complement = false，這個是什麼意思呢？在代碼中會更好的體會
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 思路: 
        // 	1.complement為false: 周遊elementData中的元素，判斷在c集合中有沒有
        // 	如果沒有，就将其移至最前面，最後把後面的置null，這樣就實作了删除c集合中的元素，
        // 	即将elementData中獨有的元素移至前面保留下來
        // 	2.complement為true: 周遊elementData中的元素，判斷在c集合中有沒有
        // 	如果有，就将其移至前面，最後把後面的置null，這樣就實作了交集的操作，
        // 	即将elementData中的在c中也有的保留下來（交集）
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //上面的翻譯：保證與 AbstractCollection 的相容，防止c.contains抛異常
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

protected void removeRange(int fromIndex, int toIndex)：

  1. 删除[fromIndex，toIndex) 元素；
  2. protected修飾，是以我們在自定義ArrayList的時候可以用到，但是這個方法沒有檢查 index 的合理性 
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}
  1. 無非還是四步死套路
  2. clear to let GC do its work：當我們能夠手動釋放資源的時候就要手動釋放資源，友善GC快速回收，提高資源使用率（什麼Stream，connection連結什麼的都要手動釋放，否則…嘿嘿）

1.3.3、get方法 

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

1.3.4、set方法 

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

1.4、修剪方法

作用：将elementData數組的大小縮小為size；

/**
 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 * list's current size.  An application can use this operation to minimize
 * the storage of an <tt>ArrayList</tt> instance.
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

1.5、交集方法 

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

// 這個batchRemove方法值得深究一下，removeAll和retainAll兩個方法都調用了這個方法
// 我們先說removeAll調用這個方法的執行流程
// 1.首先removeAll中傳入complement = false，這個是什麼意思呢？在代碼中會更好的體會
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 思路: 
        // 	1.complement為false: 周遊elementData中的元素，判斷在c集合中有沒有
        // 	如果沒有，就将其移至最前面，最後把後面的置null，這樣就實作了删除c集合中的元素，
        // 	即将elementData中獨有的元素移至前面保留下來
        // 	2.complement為true: 周遊elementData中的元素，判斷在c集合中有沒有
        // 	如果有，就将其移至前面，最後把後面的置null，這樣就實作了交集的操作，
        // 	即将elementData中的在c中也有的保留下來（交集）
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //上面的翻譯：保證與 AbstractCollection 的相容，防止c.contains抛異常
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}
java集合 java arraylist 集合 源碼 jdk1.8
上一篇: 第九章 、 TreePanel
下一篇: java基礎-Java集合架構-Map接口-HashMap原理（jdk1.7和jdk1.8）Java集合架構-Map接口-HashMap原理和源碼

繼續閱讀