Java中ArrayList的工作原理详解_Java教程

Java中ArrayList的工作原理详解

2020-08-24 10:46躲在魚缸里的徐小波 Java教程

本文主要介绍了Java中ArrayList的工作原理，具有很好的参考价值。下面跟着小编一起来看下吧

以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy（）复制到新的数组。因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。按数组下标访问元素－get（i）、set（i,e）的性能很高，这是数组的基本优势。如果按下标插入元素、删除元素－add（i,e）、remove（i）、remove（e），则要用System.arraycopy（）来复制移动部分受影响的元素，性能就变差了。越是前面的元素，修改时要移动的元素越多。直接在数组末尾加入元素－常用的add（e），删除最后一个元素则无影响。

ArrayList是一个相对来说比较简单的数据结构，最重要的一点就是它的自动扩容。

2.构造方法

ArrayList提供了三个构造方法：

									ArrayList(int initialCapacity)：指定容量

									ArrayList()：构造一个默认容量为10的ArrayList

									ArrayList(Collection<? extends E> c)：构造一个指定Collection的ArrayList

3.add

									// 添加指定元素到list末尾

									 public boolean add(E e) {

									   // 检查是否需要扩容

									   ensureCapacityInternal(size + 1); // Increments modCount!!

									   // 赋值

									   elementData[size++] = e;

									   return true;

									 }

									 private void ensureCapacityInternal(int minCapacity) {

									   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

									     // 比较默认的容量10和传入的容量，返回大点的数

									     minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

									   }

									   //扩容

									   ensureExplicitCapacity(minCapacity);

									 } 

									 private void ensureExplicitCapacity(int minCapacity) {

									   // 记录修改次数

									   modCount++;

									   // overflow-conscious code

									   if (minCapacity - elementData.length > 0)

									     grow(minCapacity);

									 }

									 private void grow(int minCapacity) {

									   // overflow-conscious code

									   // 记录当前list的容量

									   int oldCapacity = elementData.length;

									   // 扩展为原来的1.5倍

									   int newCapacity = oldCapacity + (oldCapacity >> 1);

									   // 如果扩展1.5倍还不能满足，直接扩展为需求值

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

									 }

也就是说，当增加数据的时候，如果ArrayList的大小已经不满足需求时，那么数组大小就会变为原来的1.5倍，之后就是把老的数据拷贝新的数组里面。例如我创建的list的容量时10，当我们已经添加了10个元素的之后，再添加就会进行自动扩容到15。

get，set

									public E get(int index) {

									  rangeCheck(index);

									  return elementData(index);

									}

									public E set(int index, E element) {

									  rangeCheck(index);

									  E oldValue = elementData(index);

									  elementData[index] = element;

									  return oldValue;

									}

get()和set()就比较简单了，进行范围检查后就可以进行对应的操作了。由于ArrayList是动态数组，所以我们完全可以根据下标来获取ArrayList中的元素，而且速度还比较快，故ArrayList长于随机访问。

remove

									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;

									}