HikariCP 源码分析 -- FastList

栏目: IT技术 · 发布时间: 4年前

内容简介：在前面的文章今天，继续再介绍 HikariCP 中另一个很关键的数据结构：

在前面的文章 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 相当于给了我们一些优化程序的思路。

关于优化程序，大家有什么自己的看法吗？欢迎留言讨论…


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍
谷歌时代的柏拉图

谷歌时代的柏拉图

[美] 丽贝卡·戈尔茨坦 / 李鹏程 / 中信出版集团·新思文化 / 2017-12-10 / 69.00元

我愿意用我所有的科技去换取和苏格拉底相处的一个下午。 ——史蒂夫•乔布斯 谷歌时代，科技昌明，众声喧哗，哲学提出的许多问题，科学似乎都已经给出了答案。若是如此，为什么我们今天还需要哲学？这个由古希腊城邦时代的哲人苏格拉底和柏拉图开创的学科，真的过时了吗？ 已经2400岁 的柏拉图对此有话要说。哲学家兼小说家、美国国家人文奖章获得者戈尔茨坦史海钩沉，从经典著作中复活了柏拉图，让他来......一起来看看 《谷歌时代的柏拉图》 这本书的介绍吧!

码农工具
Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

  • New
  • 文章
  • 话题
  • 教程
    • 关注 码农网 公众号
    版权所有，保留一切权利！© 2018-2024 码农网 粤ICP备17054400号-3