关于arraylist:3秒搞定ArrayList

45次阅读

共计 4580 个字符，预计需要花费 12 分钟才能阅读完成。

Jdk8

总结

  1. 扩容和删除
 ArrayList 就是一个实现了 List 接口的可主动扩容的数组，当增加元素的时候它会尝试扩容, 扩容的规范是变为原来的 1.5 倍 **，当删除元素的时候，它会左移元素，防止数组呈现 "空位"
  1. 容量
 new ArrayList<>() 初始化容量为 0，等到第一次 add 的时候再初始化为 10
  1. 有序汇合

  2. 能够存储反复值和 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
  1. ArrayList 是 疾速失败 的，在遍历的同时当汇合被批改后会抛出 ConcurrentModificationException，能够应用 Iterator 的删除办法来防止这个问题
  2. 非线程平安 的，如果你想在多线程环境中应用，能够应用 Vector 或者它的线程平安包装类
  3. 扩大
  操作系统的局部性原理，数组的间断存储空间的个性充沛应用了局部性原理，也就是说硬件的高速缓存减速了数组的拜访

性能

  1. Adding an element– 如果你应用的是  add(E e) 办法增加一个元素到 ArrayList 开端，它的工夫复杂度 O(1)；然而当空间有余引发扩容的时候，会导致新建数组而后拷贝数据，这个时候它的工夫复杂度 O(n) ; 当你应用 add(int index, E element)的时候它的算法复杂度是 O(n – index) 也就是 O(n)
  2. Retrieving an element– 当你应用get(int index) 的时候，它的工夫复杂度是 O(1)，因为数组能够间接依据下标进行定位
  3. Removing an element– 当你应用 remove(int index) 它的工夫复杂度是 O(n – index) ，因为它波及到挪动元素
  4. Traverse – 遍历的工夫工夫复杂度是O(n), 也就是依赖于 Capacity 的大小，如果你比拟器重遍历的性能，就请不要不要给它设置一个很大的初始容量

UML


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

  1. 当调用 new ArrayList<>()时，将一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA  赋值给了 elementData，这个时候汇合的长度 size 为默认长度 0
  1. 例如当调用 new ArrayList<>(100)时，依据传入的长度，new 一个 Object[100]赋值给 elementData，当然如果玩儿的话，传了一个 0，那么将一个空数组 EMPTY_ELEMENTDATA 赋值给了 elementData
  1. 例如当调用 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[] (see 6260652)，即调用 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/yingwen…

正文完
arraylist
发表至： arraylist
2021-06-15
 0
关于arraylist:源码分析ArrayList和LinkedList如何实现的我看你还有机会
关于arraylist:ArrayList-的工作原理
关于arraylist:8-arraylist
关于arraylist:ArrayList源码