likes
comments
collection
share

ArrayList动态数组,是怎么实现动态的?

作者站长头像
站长
· 阅读数 11

简介

ArrayList是一个动态数组,可以通过泛型来决定数据中存放的元素类型

怎么实现的动态

之所以是动态数组,是因为在使用无参构造函数创建ArrayList之后,默认为空数组

public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
}

在你每次去add一个元素的时候,通过ensureCapacityInternal方法去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求

public boolean add(E e) {
	// size为当前数据存放元素的数量
    ensureCapacityInternal(size + 1);
    // elementData为ArrayList内部存放数据的数组
    elementData[size++] = e;  
    return true;
}

private void ensureCapacityInternal(int minCapacity) { 
	// 判断数组是否为空,为空则将最小容量设置为默认值10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  
    }  
	// 判断当前容量是否满足最小容量
    ensureExplicitCapacity(minCapacity);  
}

private void ensureExplicitCapacity(int minCapacity) {
	// modCount用于记录修改次数,作用于fast-fail机制
	// 如果在迭代的时候发现modCount被修改了,则会抛出异常来避免可能会出现的不确定行为
    modCount++;  
  
    // 如果当前容量小于最小容量,则进行扩容
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}

private void grow(int minCapacity) {  
    int oldCapacity = elementData.length;  
    // 计算新的容量,扩大为原容量的1.5倍, oldCapacity >> 1 运算表示右移一位,也就是相当于除以二并取整
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)  
        newCapacity = minCapacity; 
    // 如果新容量超过了数组的最大容量,调用hugeCapacity方法来获取一个更大的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)  
        newCapacity = hugeCapacity(minCapacity);  
    // 拷贝原数组,将原数组的元素复制到新数组中 
    elementData = Arrays.copyOf(elementData, newCapacity);  
}

private static int hugeCapacity(int minCapacity) {  
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
	// 如果最小容量大于最大容量,则将容量设置为Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?  
        Integer.MAX_VALUE :  
        MAX_ARRAY_SIZE;  
}

从上面的源码解释可以看到,如果新建数据没有给定初始值,ArrayList是每次在进行add操作的时候去进行扩容的,扩容则会涉及到Arrays.copyOf深拷贝,会造成内存和性能的消耗,所以在生产项目中,推荐大家尽量在创建ArrayList对象的时候就指定其容量。

Fast-Fail机制

大家肯定注意到了上面提到的通过modCount实现的Fast-Fail机制

Fast-Fail是一种机制,用于检测在迭代过程中是否有其他线程对集合进行了修改。当一个线程在迭代 ArrayList 时,如果其他线程对 ArrayList 进行了结构性修改(如添加、删除元素),那么迭代器会立即抛出 ConcurrentModificationException 异常,以避免出现不确定的行为。 例子:

public class Example1 {  
    public static void main(String[] args) {  
        ArrayList<String> list = new ArrayList<>(3);  
        list.add("qwe");  
        list.add("asd");  
        list.add("zxc");  
  
        Iterator<String> iterator = list.iterator();  
        while (iterator.hasNext()){  
            String next = iterator.next();  
            System.out.println(next);  
            list.remove(next);  
        }  
    }  
}

输出:
qwe
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at com.example.lepractice.collection.Example1.main(Example1.java:21)

造成快速失败的常见操作包括:

  1. 在迭代过程中,使用 ArrayList 的 add、remove、clear 等方法修改集合的结构。
  2. 多个线程同时对 ArrayList 进行修改操作。

为了避免快速失败,可以采取以下措施:

  1. 在迭代过程中,不要修改集合的结构。如果需要修改,可以使用迭代器的 remove 方法,对应上面的例子也就是iterator.remove()。
  2. 在多线程环境下,对于需要并发修改的情况,可以使用线程安全的集合类,如 CopyOnWriteArrayList。

如果使用语法糖 for (String next : list) { System.out.println(next); list.remove(next); } 这样的遍历方式,其实内部也是使用的迭代器,所以会存在同样的问题

转载自:https://juejin.cn/post/7265149630925045800
评论
请登录