java -- ArrayList

Java -- ArrayList

 

 

       ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。

 

 

 

优点

 

• 查找数据性能很快，跟Vector比也要快些
• 可以插入任何数据类型
• 以数组实现，节约空间，但有容量限制，默认初始化大小为10，当超出后，会自动扩容为原来的1/2（50%）的容量，即自动扩容机制。

 

 

缺点

 

• 非线程安全
• 更新删除性能会比较差，因为实质是数组
• 自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
• 需要连续的存储空间

 

 

工作原理

 

底层使用数组实现

 

private transient Object[] elementData;

 

 

 

构造方法

 

    ArrayList提供了三种方式的构造器

 

• 构造一个默认初始容量为10的空列表
• 构造一个指定初始容量的空列表
• 构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。

 

public ArrayList() {  
    this(10);  
}  
  
public ArrayList(int initialCapacity) {  
    super();  
    if (initialCapacity < 0)  
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);  
    this.elementData = new Object[initialCapacity];  
}  
  
public ArrayList(Collection<? extends E> c) {  
    elementData = c.toArray();  
    size = elementData.length;  
    // c.toArray might (incorrectly) not return Object[] (see 6260652)  
    if (elementData.getClass() != Object[].class)  
        elementData = Arrays.copyOf(elementData, size, Object[].class);  
}

 

 

 

 

插入、修改、存储数据

 

• 查找数据和修改指定数据get(index)/set(index,e)，性能很高
• 添加add(e)操作性能也很好（直接在数组末尾添加元素)
• 按照下标来插入元素或者删除操作，add(index,e)/remove(index)/remove(e),性能会低，需要使用 system.arraycopy()来移动受影响的元素

 

 

 

调整容量

 

      每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。

 

扩容规则

 

1. 将老数组中的元素重新拷贝一份到新的数组中
2. 每次数组容量的增长大约是其原容量的1.5倍

 

   可以知道，这样扩容的代价太高了，所以应该作适当的处理。

 

 

解决方法

 

1. 当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。
2. 根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

 

 

 

并发处理

 

      ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。