【Android面试基础】ArrayList的随机访问和顺序访问的区别？-六虎

面试官问：ArrayList的随机拜访和次序拜访的差异？

我：嗯…，什么是随机拜访和次序拜访？

OOS：（只需自己不为难，为难的便是别人）

咱们知道Java中的ArrayList是一个可调整巨细的数组完成，是一种能够动态改动数组巨细的数据结构。ArrayList增加删去比较低效，查找很高效。随机拜访功率高,随机插入、随机删去功率低。

1.随机拜访&次序拜访

关于ArrayList来说，因为它是依据动态数组完成的，所以随机拜访和次序拜访的功率都很高。

随机拜访

若你需求拜访ArrayList中特定方位的元素，例如，list.get(5)会立即回来数组中第六个元素（索引从0开端），这种直接依据下标获取元素的办法为随机拜访，ArrayList的随机拜访是十分功率的，它允许你直接经过数组索引以常数时间复杂度O(1)拜访任何方位的元素。
次序拜访

当你需求遍历整个ArrayList时，创立一个迭代器Iterator目标，并经过调用hasNext()和next()办法进行遍历，这种次序遍历拜访的办法为次序拜访。ArrayList次序拜访也功率很高的办法。 ArrayList运用随机拜访和次序拜访原理上都是经过数组索引获取元素，可是因为迭代器的运用，每次迭代都会调用Iterator的next()办法，而这些办法调用会引进一定的开支。实际运用会总体上较慢的，咱们来看一个比方。

 public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList();
        for(int i =0;i < 100000000;i++){
            list.add(new Integer(i));
        }
        long time = System.currentTimeMillis();
        for(int i =0;i < 100000000;i++){
            list.get(i);
        }
        System.out.println("cost 随机拜访 time:"+(System.currentTimeMillis()-time));
        //次序拜访
        long time1 = System.currentTimeMillis();
        for(Integer i:list){
            //list.get(i);
        }
        System.out.println("cost  次序拜访2 time:"+(System.currentTimeMillis()-time1));
        Iterator iterator = list.iterator();
        long time2 = System.currentTimeMillis();
        //次序拜访
        while (iterator.hasNext()){
            iterator.next();
        }
        System.out.println("cost 次序拜访2 time:"+(System.currentTimeMillis()-time2));
    }

运转成果：

咱们发现第一种for循环的随机拜访更高效，运用iterator比增强型for(Object i:list)高效。 增强型for循环的办法为啥是最慢的，原因是增强型for循环遍历ArrayList时，底层会创立一个Iterator目标，并经过调用hasNext()和next()办法进行遍历。而一般for循环是直接经过索引来拜访元素，没有额定创立Iterator目标和调用办法next()的开支。

当然这是ArrayList调集数据量很大的时分比照。当数据调集在比较小的时分，比方小于1000，根本上ArrayList的上面三种遍历办法就没有差异了。

此外ArrayList中的数组都是Object目标。假如是寄存根本类型数据，会有主动装箱和拆箱的开支,获取元素的功率就很较低。


    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList();
        for(int i =0;i < 100000000;i++){
            list.add(i); //直接寄存int 根本类型，主动装箱
        }
        long time = System.currentTimeMillis();
        for(int i =0;i < 100000000 ;i++){
            int o = list.get(i);// 主动拆箱
        }
        System.out.println("cost 随机拜访 time:"+(System.currentTimeMillis()-time));
        //次序拜访
        long time1 = System.currentTimeMillis();
        for(int i:list){// 主动拆箱
            list.get(i);
        }
        System.out.println("cost  次序拜访2 time:"+(System.currentTimeMillis()-time1));
        Iterator iterator = list.iterator();
        long time2 = System.currentTimeMillis();
        //次序拜访
        while (iterator.hasNext()){
            int o = (int) iterator.next();//拆箱
        }
        System.out.println("cost 次序拜访2 time:"+(System.currentTimeMillis()-time2));
    }

运转成果如下：

ArrayList的随机拜访和次序拜访搞理解了，随机拜访和次序拜访功率都很高，因为ArrayList次序拜访额定创立Iterator目标和调用办法next()的开支，在数据量很大的时分，ArrayList的随机拜访功率高于次序拜访。

咱们再来仔细看看这个简单却又不简单的ArrayList类的其他细节，学习java封装的高雅。下回假如遇到面试官说“便是做了一个封装，这也没什么技能突出点”的时分，拿这个Josh Bloch大佬的Collection的封装举例怼他。

2.符号忆接口

咱们先看看ArrayList的声明，如图所示，ArrayList除了完成List接口，还完成了RandomAccess，Cloneable，Serializable等符号忆接口。

List接口供给了调集Collection和Iterable操作办法和定义，比方LinkedList,Vector都是List的具体完成。RandomAccess，Cloneable，Serializable等符号忆接口。

RandomAccess

RandomAccess便是随机拜访的意思，用以符号完成的List调集具有快速随机拜访的才能。源码中注释说明也说了这个符号接口，表明List的随机拜访快于次序拜访的才能

一切的List完成都支持随机拜访的，仅仅依据根本结构的不同，完成的速度不同罢了，这里的快速随机拜访，那么就不是一切List调集都支持了。比方，ArrayList和Vector依据数组完成，天然带下标，能够完成常量级的随机拜访，而LinkedList依据链表完成，随机拜访需求依托遍历完成，复杂度为O(n) ，所以ArrayList和Vector具有快速随机拜访功用，而LinkedList没有。

Cloneable

Cloneable接口没有包含clone()办法，仅仅符号类是否支持克隆，假如不完成此接口，调用目标的clone()就会抛出反常。即使重写Object的clone(),可是没有加上Cloneable接口也会报错。

ArrayList中关于Object的clone()。咱们看到是依据Arrays.copyOf(elementData, size)给元素复制。注释说这是一个a shallow copy of this ArrayList instance,便是一个浅拷贝。原因是Arrays.copyOf()是依据System.arraycopy()完成的，所以ArrayList中的其他元素也都是copy原型目标的地址。都是指向一个目标。

Serializable

Serializable相同归于符号接口，他表明类的目标能够完成序列化的才能。关于序列化先关常识原理或许咱们都理解，我就不赘述了。咱们只需看看ArrayList他是怎样完成的。看源码有完成writeObject和readObject办法，for循环将每个元素写入和读出。而其中每个元素目标也需求完成序列化。不然就会报NotSerializableException反常

咱们看到截图代码中有一个if (modCount != expectedModCount)的判别，不相等就会出现ConcurrentModificationException。modCount是啥？这个便对错线程安全的原因。

3.非线程安全

ArrayList非线程安全的，modCount为列表在结构上被修正的次数。

注释的意思是，此字段由迭代器和list Iterator办法回来的迭代器与列表迭代器完成运用。假如此字段的值意外更改，迭代器（或列表迭代器）将抛出ConcurrentModificationException，也便是咱们每次增删操作或许改动列表巨细的操作，modCount就会加1。如下源码：

    public boolean add(E e) {
        //最终在ensureExplicitCapacity办法修正modCount
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    private void ensureExplicitCapacity(int minCapacity) {
         //修正
        modCount++;
        //省掉
        .......
    }
    private void fastRemove(int index) {
         //修正
        modCount++;
        //省掉
        .......
    }
    public void clear() {
        //修正
        modCount++;
         //省掉
        .......
    }
    //每次new Itr(),初始化iterator的expectedModCount为当时modCount
    public Iterator<E> iterator() {
        return new Itr();
    }
    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
         //省掉
        .......
        int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        public E next() {
            //判别修正版本
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //省掉
            .......
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        public void remove() {
            //省掉
            .......
            //断修正版本
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;//修正expectedModCount
                limit--;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        //省掉
        .......
    }

所以在iterator进行遍历的时分，对list进行增加或许删去都会报ConcurrentModificationException反常。假如想要在遍历过程中删去元素，能够运用迭代器本身iterator的remove()办法，因为他有对本身的expectedModCount从头赋值。

能够思考怎样优化ArrayList的新增删去的优化。新增上优化方向便是削减扩容的次数。关于删去的优化方向是削减每次remove的System.arraycopy操作.

4.扩容计划

ArrayList是一个动态数组，它是怎样完成扩容的呢。上面咱们发现 ensureExplicitCapacity 在每次增加元素的时分就会调用。咱们先看看ArrayList的初始巨细

    /**
   * Default initial capacity.
   */
  private static final int DEFAULT_CAPACITY = 10;
  /**
   * Shared empty array instance used for empty instances.
   */
  private static final Object[] EMPTY_ELEMENTDATA = {};
  /** 
   * first element is added.
   */
  private static final Object[] DEFAULTCAPACITY_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);
      }
  }
  /**
   * Constructs an empty list with an initial capacity of ten.
   */
  public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

发现有一个DEFAULT_CAPACITY常量。可是初始化时分，并没有运用，默许在不设置initialCapacity的情况下，都是空数组{}。当咱们开端增加元素的时分，才开端初始化数组的初始容量。


public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      elementData[size++] = e;
      return true;
}
private void ensureCapacityInternal(int minCapacity) {
      //假如为空数组，初始化数组的初始容量DEFAULT_CAPACITY，当minCapacity大于DEFAULT_CAPACITY的时分，就开端新的扩容
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
      // 判别是需求扩容
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      //在本来的oldCapacity根底上 扩展1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      //判别是否超越最大值  MAX_ARRAY_SIZE，假如超越，扩容到最大的Integer.MAX_VALUE
      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);
  }
  private static int hugeCapacity(int minCapacity) {
      //假如minCapacity现已开端小于0了，现已超出int的最大字节数，比Integer.MAX_VALUE还大，那么抛出OutOfMemoryError反常。
      if (minCapacity < 0) // overflow
          throw new OutOfMemoryError();
          //不然直接给到Integer.MAX_VALUE最大的巨细
      return (minCapacity > MAX_ARRAY_SIZE) ?
          Integer.MAX_VALUE :
          MAX_ARRAY_SIZE;
  }

从源码中，咱们总结ArrayList的扩容计划，ArrayList没有指定初始容量的情况下，默许elementData为空数组，再增加元素的时分，判别是否需求扩容，每次扩容为当时容量的1.5倍，当数组长度大于Integer.MAX_VALUE - 8的时分，开端设置超大容量Integer.MAX_VALUE，当容量超越Integer.MAX_VALUE的时分，就抛出OutOfMemoryError反常。

和ArrayList不同的是Vector是线程安全的，是因为Vector关于操作运用synchronized加锁了。

5.总结

ArrayList的随机拜访和次序拜访功率都很高，因为ArrayList次序拜访额定创立Iterator目标和调用办法next()的开支，在数据量很大的时分，ArrayList的随机拜访功率高于次序拜访。
ArrayList完成RandomAccess，Cloneable，Serializable等符号接口，具有快速拜访的才能，又具有克隆和序列化的才能。其中克隆是浅拷贝，序列化过程中元素也需求对应完成序列化才能。
ArrayList对错线程安全的，主要在迭代器关于modCount在列表在结构上被修正的次数的预期判别。
ArrayList没有指定初始容量的情况下，默许elementData为空数组，再增加元素的时分，判别是否需求扩容，每次扩容为当时容量的1.5倍，当数组长度大于Integer.MAX_VALUE - 8的时分，开端设置超大容量Integer.MAX_VALUE，当容量超越Integer.MAX_VALUE的时分，就抛出OutOfMemoryError反常。

【Android面试基础】ArrayList的随机访问和顺序访问的区别？

1.随机拜访&次序拜访

2.符号忆接口

3.非线程安全

4.扩容计划

5.总结

相关文章

targetSdkVersion升级到28一些修改的地方(持续更新)

聊聊陈旧的插件化

TypeScript 高级数据类型 ｜ 青训营笔记

RT-Thread记录（十三、I/O 设备模型之PIN设备）

作者信息

TypeScript 高级数据类型｜青训营笔记