在前面的文章 HikariCP 源碼分析 — ConcurrentBag 中，D瓜哥分析了一下 HikariCP 中一個非常重要的數據結構 ConcurrentBag 。

今天，繼續再介紹 HikariCP 中另一個很關鍵的數據結構： FastList 。

FastList 本身的實現非常簡單，要理解它的奧祕，就需要結合 Java 原生集合類的 ArrayList 來比較性地看。

構造函數

先來對比一下兩者的構造函數。先來看看 FastList ：

FastList 
public final class FastList<T> implements List<T>, RandomAccess, Serializable
{
   private static final long serialVersionUID = -4598088075242913858L;

   private final Class<?> clazz;
   private T[] elementData;
   private int size;

   /
    * Construct a FastList with a default size of 32.
    * @param clazz the Class stored in the collection
    */
   @SuppressWarnings("unchecked")
   public FastList(Class<?> clazz)
   {
      this.elementData = (T[]) Array.newInstance(clazz, 32);
      this.clazz = clazz;
   }

   /
    * Construct a FastList with a specified size.
    * @param clazz the Class stored in the collection
    * @param capacity the initial size of the FastList
    */
   @SuppressWarnings("unchecked")
   public FastList(Class<?> clazz, int capacity)
   {
      this.elementData = (T[]) Array.newInstance(clazz, capacity);
      this.clazz = clazz;
   }

再來看看 ArrayList ：

ArrayList 
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

    /
     * 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);
        }
    }

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

    /
     * 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) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

相同之處是，兩者都是通過數組來存放元素的。

兩者有如下不同之處：

  1. FastList 沒有對容量大小做判斷。畢竟是在內部使用，自己不會故意坑自己。所以，也就沒必要了。

  2. FastList 保存了元素的類型 Class ，在擴容時直接使用即可；而 ArrayList 則要麻煩一些。後面在細講。

  3. FastList 默認大小爲 32 ，而且直接初始化； ArrayList 是 10 ，默認是空數組，直到添加元素才創建數組。這裏，也要從適用性來說， FastList 是內部使用，創建出來就比如要存放元素。所以，直接初始化比較合適。而 ArrayList 外部使用，不確定是否必須要存放元素，直到確實存放元素時，再初始化比較節省空間。

  4. FastList 只實現了 List ； ArrayList 實現了 List 和 Cloneable 接口，顯示標註出克隆功能。其實，這兩個差別不大，畢竟 Object 也有 clone() 方法。

  5. ArrayList 多了一個 public ArrayList(Collection<? extends E> c) 構造函數，方便接受。

總體來講， FastList 的實現比較剋制，夠用即可；而 ArrayList 則更多考慮適用性，滿足儘可能多的場景。

添加元素

再來看看兩者如何處理添加元素的操作。還是先看 FastList 的實現：

FastList 
@Override
public boolean add(T element)
{
   if (size < elementData.length) {
      elementData[size++] = element;
   }
   else {
      // overflow-conscious code
      final int oldCapacity = elementData.length;
      final int newCapacity = oldCapacity << 1;
      @SuppressWarnings("unchecked")
      final T[] newElementData = (T[]) Array.newInstance(clazz, newCapacity);
      System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);
      newElementData[size++] = element;
      elementData = newElementData;
   }

   return true;
}

再來看看 ArrayList ：

ArrayList 
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

// grow() 代碼不再粘貼，將數組長度

兩者有這些地方需要注意：

  1. ArrayList 維護了一個 modCount 變量來保存修改次數。

  2. 在添加元素時，都需要對容量做一個判斷：

    1. FastList 在容量 OK 的情況下，直接添加元素；容量不夠時，創建一個 2 倍原數組的新數組，使用 System.arraycopy 將已有數據拷貝到新數組，然後再添加新元素。

    2. ArrayList 則是判斷數組是否已滿，滿了就創建一個 1.5 倍大小的新數組，將已有數據拷貝過來再添加新元素。這裏需要多說一句，由於 ArrayList 存數據的類型 Class 信息，在擴容時，通過反射獲取這個 Class 信息。所以，理論上來說，不如 FastList 。

獲得元素

再來看看獲取元素操作。先看 FastList ：

FastList 
@Override
public T get(int index)
{
    return elementData[index];
}

再來看看 ArrayList ：

ArrayList 
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

請注意： FastList 是直接從數組中根據 index 返回數據，沒有對 index 做任何校驗；而 ArrayList 則先做了校驗，合法後才返回元素。所以， FastList 操作更快！

刪除元素

來看看刪除元素的操作。刪除操作有兩組：①刪除某個元素；②刪除指定 index 的元素。

刪除某個元素

先看 FastList ：

FastList 
public T removeLast()
{
   T element = elementData[--size];
   elementData[size] = null;
   return element;
}

@Override
public boolean remove(Object element)
{
   for (int index = size - 1; index >= 0; index--) {
      if (element == elementData[index]) {
         final int numMoved = size - index - 1;
         if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
         }
         elementData[--size] = null;
         return true;
      }
   }

   return false;
}

再來看看 ArrayList ：

ArrayList 
public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

兩者的處理流程基本相同。不同之處在於 ArrayList 需要處理元素爲 null 的情況，而 FastList 不需要。另外， FastList 還對接口做了擴展，增加了 removeLast() 方法。而 ArrayList 維護了一個 modCount 變量來保存修改次數。

刪除指定 index 的元素

先看 FastList ：

FastList 
@Override
public T remove(int index)
{
    if (size == 0) {
        return null;
    }

    final T old = elementData[index];

    final int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }

    elementData[--size] = null;

    return old;
}

再來看看 ArrayList ：

ArrayList 
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

請注意： FastList 是直接通過向前複製來刪除元素，沒有對 index 做任何校驗；而 ArrayList 則先做了校驗，合法後才通過向前複製來刪除元素。所以， FastList 操作更快！

清空元素

來看看刪除元素的操作。先看 FastList ：

FastList 
@Override
public void clear()
{
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
    }

    size = 0;
}

再來看看 ArrayList ：

ArrayList 
public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

這兩者基本一致。 ArrayList 多了一點操作，維護了一個 modCount 變量來保存修改次數。

遍歷

來看看遍歷操作。先看 FastList ：

FastList 
@Override
public Iterator<T> iterator()
{
    return new Iterator<T>() {
        private int index;

        @Override
        public boolean hasNext()
        {
        return index < size;
        }

        @Override
        public T next()
        {
            if (index < size) {
                return elementData[index++];
            }

            throw new NoSuchElementException("No more elements in FastList");
        }
    };
}

再來看看 ArrayList ：

ArrayList 
public Iterator<E> iterator() {
    return new Itr();
}

/**
    * An optimized version of AbstractList.Itr
    */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i < size) {
            final Object[] es = elementData;
            if (i >= es.length)
                throw new ConcurrentModificationException();
            for (; i < size && modCount == expectedModCount; i++)
                action.accept(elementAt(es, i));
            // update once at end to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

兩者的遍歷操作，差別好大：

  1. FastList 只對當前 index 判斷，符合要求則直接返回，不符合要求拋出異常。

  2. ArrayList 則要複雜好多：

    1. 通過 checkForComodification() 方法檢查當前 ArrayList 對象是否被同步修改；

    2. 除了判斷 index 是否小於當前 size ，還要判斷 index 是否大於等於 elementData.length ，以應對同步修改的問題；

    3. 實現了 remove() 和 forEachRemaining(Consumer<? super E> action) 方法。

小結

總體來講 FastList 通過一下幾點來達到提速的目的：

  1. 刪除 index 合法性判斷； — 這是非常關鍵的一點。尤其是在獲取元素的時候。

  2. 刪除修改次數統計；

  3. 保存元素類型 Class 實例，便於擴容；

  4. 空置無用方法，達到瘦身目的。

所以， FastList 相當於給了我們一些優化程序的思路。

關於優化程序，大家有什麼自己的看法嗎？歡迎留言討論…

相關文章