3秒搞定ArrayList

原创

老兵程序员

修改于 2021-06-16 10:28:16

4560

修改于 2021-06-16 10:28:16

文章被收录于专栏：Hello知识库-JAVA基础Hello知识库-JAVA基础

jdk8

总结

扩容和删除

ArrayList 就是一个实现了List接口的可自动扩容的数组，**当添加元素的时候它会尝试扩容,扩容的标准是变为原来的1.5倍**，当删除元素的时候，它会左移元素，避免数组出现"空位"

容量

new ArrayList<>() 初始化容量为0，等到第一次add的时候再初始化为10

有序集合
可以存储重复值和null值

示例：

    public static void main(String[] args) {
        List<String> a=new ArrayList<>();
        a.add(null);
        a.add(null);
        a.add(null);
        System.out.println(a.size());
    }
    输出：
    3

ArrayList 是快速失败的，在遍历的同时当集合被修改后会抛出ConcurrentModificationException，可以使用Iterator 的删除方法来避免这个问题
非线程安全的，如果你想在多线程环境中使用，可以使用Vector 或者它的线程安全包装类
扩展

操作系统的局部性原理，数组的连续存储空间的特性充分使用了局部性原理，也就是说硬件的高速缓存加速了数组的访问

性能

Adding an element- 如果你使用的是 add(E e) 方法添加一个元素到ArrayList末尾，它的时间复杂度 O(1)；但是当空间不足引发扩容的时候，会导致新建数组然后拷贝数据，这个时候它的时间复杂度 O(n) ;当你使用 add(int index, E element)的时候它的算法复杂度是 O(n - index) 也就是 O(n)
Retrieving an element- 当你使用get(int index) 的时候，它的时间复杂度是 O(1)，因为数组可以直接根据下标进行定位
Removing an element- 当你使用 remove(int index) 它的时间复杂度是 O(n - index) ，因为它涉及到移动元素
Traverse - 遍历的时间时间复杂度是O(n),也就是依赖于Capacity 的大小，如果你比较重视遍历的性能，就请不要不要给它设置一个很大的初始容量

UML

底层是一个Object[]，添加到ArrayList中的数据保存在了elementData属性中。

当调用new ArrayList<>()时，将一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给了elementData，这个时候集合的长度size为默认长度0
例如当调用new ArrayList<>(100)时，根据传入的长度，new一个Object100赋值给elementData，当然如果玩儿的话，传了一个0，那么将一个空数组 EMPTY_ELEMENTDATA 赋值给了elementData
例如当调用new ArrayList<>(new HashSet())时，根据源码，我们可知，可以传递任何实现了Collection接口的类，将传递的集合调用toArray()方法转为数组内赋值给elementData

构造方法

无参构造

创建一个空的使用默认容量的list(默认是0，第一次add会初始化为10)

//默认创建一个ArrayList集合
List<String> list = new ArrayList<>();
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

指定初始容量

创建一个空的指定容量的list

//创建一个初始化长度为100的ArrayList集合
List<String> initlist = new ArrayList<>(100);

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

其他集合作为参数

//将其他类型的集合转为ArrayList
List<String> setList = new ArrayList<>(new HashSet());

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

构造一个包含指定集合元素的列表，其顺序由集合的迭代器返回。当传入的集合参数为空的话，抛出NullPointerException，因为它会调用该集合的toArray 方法，和HashTable 里面调用key 的hashcode 方法的原理一样

当集合是一个空的集合的话，elementData = EMPTY_ELEMENTDATA和指定0是initialCapacity的效果一样

注意:在传入集合的ArrayList的构造方法中，有这样一个判断

if (elementData.getClass() != Object[].class)，给出的注释是：c.toArray might (incorrectly) not return Object，即调用toArray方法返回的不一定是Object[]类型，查看Collection接口的定义

Object[] toArray();

我们发现返回的确实是Object[]，那么为什么还会有这样的判断呢？如果有一个类CustomList继承了ArrayList，然后重写了toArray()方法呢。。

public class CustomList<E> extends ArrayList {
    @Override
    public Integer [] toArray() {
        return new Integer[]{1,2};
    };
    
    public static void main(String[] args) {
        Object[] elementData = new CustomList<Integer>().toArray();
        System.out.println(elementData.getClass());
        System.out.println(Object[].class);
        System.out.println(elementData.getClass() == Object[].class);
    }
}

执行结果：

class [Ljava.lang.Integer;
class [Ljava.lang.Object;
false

接着说，如果传入的集合类型和我们定义用来保存添加到集合中值的Object[]类型不一致时，ArrayList做了什么处理？读源码看到，调用了 Arrays.copyOf(elementData, size, Object[].class);

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {    
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength); 
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

我们发现定义了一个新的数组，将原数组的数据拷贝到了新的数组中去。

思考

    我们在查看 ArrayList 的实现类源码时，你会发现对象数组 elementData 使用了 transient 修饰，我们知道 transient 关键字修饰该属性，则表示该属性不会被序列化，然而我们并没有看到文档中说明 ArrayList 不能被序列化，这是为什么？<br />

ArrayList 属性主要由数组长度 size、对象数组 elementData、初始化容量 default_capacity 等组成，其中初始化容量默认大小为 10。

// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 对象数组
transient Object[] elementData; 
// 数组长度
private int size;

从 ArrayList 属性来看，它没有被任何的多线程关键字修饰，但 elementData 被关键字 transient 修饰了。这就是我在上面提到的第一道测试题：transient 关键字修饰该字段则表示该属性不会被序列化，但 ArrayList 其实是实现了序列化接口，这到底是怎么回事呢？这还得从"ArrayList 是基于数组实现"开始说起，由于 ArrayList 的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据。如果采用外部序列化法实现数组的序列化，会序列化整个数组。ArrayList 为了避免这些没有存储数据的内存空间被序列化，内部提供了两个私有方法 writeObject 以及 readObject 来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间。因此使用 transient 修饰数组，是防止对象数组被其他外部方法序列化。

看到这里就点个赞吧👇分享更多技术文章,去帮助更多的人,这里有我所有知识库哟~ 🐌

https://www.yuque.com/yingwenerjie

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度