疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

深入探索Java-ArrayList


 

   

  1. ArrayList概述

  ArrayList是List接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。ArrayList实现上是线程不安全的,这个和Hashmap类似。

  2. 用什么数据结构实现的

  使用数组实现

  private transient Object[] elementData;

  3. 数组如何做到动态增加或者删除元素

  对于ArrayList做元素的增删时,如果没有超出数组容量,数组会在对应位置增加或者删除元素,使用System.arraycopy函数去做复制搬移动作。

  以删除一个元素为例

  // 移除此列表中指定位置上的元素。

  public E remove(int index) {

  RangeCheck(index);

  modCount++;

  E oldValue = (E) elementData[index];

  int numMoved = size - index - 1;

  if (numMoved > 0)

  System.arraycopy(elementData, index+1, elementData, index, numMoved);

  elementData[--size] = null; // Let gc do its work

  return oldValue;

  }

  4. 数组如何做到动态扩容

  当向数组中添加元素时,添加后元素的个数超出当前数组的长度时,数组将会进行扩容。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前,我也可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增式再分配的数量。

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

  }

  }

  从上述代码中可以看出,数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造ArrayList实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量。