ArrayList源码:add 方法 布满荆棘的人生 2023-01-23 01:05 120阅读 0赞 ## 1. add(E e): ## // 向列表中追加一个元素。 // size:当前列表中元素的数量。 public boolean add(E e) { // size+1 表示最小容量。最小容量 == 当前列表中元素个数+1。 ensureCapacityInternal(size + 1); // Increments modCount!! // 到这里已经扩容结束了。将新元素追加到数组。 elementData[size++] = e; // 添加成功,返回 true。 return true; } 看下扩容函数: `ensureCapacityInternal(size + 1)` private void ensureCapacityInternal(int minCapacity) { // 1.先计算出所需的最小容量。 // 2.确认最小容量,并执行扩容。 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } (1)计算所需的最小容量。如果是向空列表中 add 元素,最小容量取 `默认容量(10)` 和 `待添加的元素个数` 中较大的那个。如果是向非空列表中 add 元素,最小容量直接取:`当前列表中元素的个数 + 待添加的元素的个数`。 // 计算需要的最小容量。minCapacity == 当前数组元素个数 + 要添加的元素的个数。 // DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} // DEFAULT_CAPACITY = 10 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 向空数组中添加元素,比如第一次 add 元素时才会触发 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 返回 默认容量 和 minCapacity 中最大的。 return Math.max(DEFAULT_CAPACITY, minCapacity); } // 向非空数组 add 时,直接返回 minCapacity。 return minCapacity; } (2.1)确认是否扩容。只有当 计算所需要的最小容量 大于 当前数组的长度时,才扩容。 // minCapacity 是计算出来的最小容量。 private void ensureExplicitCapacity(int minCapacity) { // 这个是校验并发用的。 modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) // 当需要的最小容量 > 当前数组的长度时, 执行扩容。 grow(minCapacity); } (2.2) 执行扩容。 // minCapacity 是所需的细小容量。 private void grow(int minCapacity) { // 当前数组的长度。 int oldCapacity = elementData.length; // 扩容到当前数组长度的 1.5 倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果扩容后的容量还小于所需的最小容量,那就以计算需要的为准(再将容量扩大)。 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 再判断,如果新容量是个很大的数子,快逼近 int 的极限的了,但还没有溢出, // 那就直接将新容量扩大到 int 的极限。 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); } // 极大的扩容 private static int hugeCapacity(int minCapacity) { // 如果容量超 int 范围了,报异常。 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // 三段式,确定大容量的准确值。 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } ## 2. addAll(Collection<? extends E> c) ## // 向列表中追加一个list。 public boolean addAll(Collection<? extends E> c) { // 拿出 list 中元素保存到数组中。 Object[] a = c.toArray(); // 获取追加的元素个数。 int numNew = a.length; // 给原本的 elementData 扩容。 ensureCapacityInternal(size + numNew); // Increments modCount // 将 a 数组中的元素从 0 开始,依次复制到 elementData 的 size 位置开始,并往后推 // 总共复制 numNew 个。 System.arraycopy(a, 0, elementData, size, numNew); // 更新列表长度。 size += numNew; return numNew != 0; } ## 3. add(int index, E element) ## // 在指定索引出插入元素。 public void add(int index, E element) { // 检查是否越界。 rangeCheckForAdd(index); // 扩容。 ensureCapacityInternal(size + 1); // Increments modCount!! // 将 index 位置以及后面的元素,向后移动 1 为。 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 在指定位置插入元素。 elementData[index] = element; // 列表中元素个数 + 1。 size++; } ## 4. addAll(int index, Collection<? extends E> c) ## // 在指定索引出插入一个集合。 public boolean addAll(int index, Collection<? extends E> c) { // 检查索引是否越界。 rangeCheckForAdd(index); // 集合里的元素保存到数组中。 Object[] a = c.toArray(); // 数组长度。 int numNew = a.length; // 扩容。 ensureCapacityInternal(size + numNew); // Increments modCount // 原数组中要向后移动的元素的个数。 int numMoved = size - index; // 如果向后移动的元素的个数大于 0。 if (numMoved > 0) // index 位置开始向后,总共 numMoved 元素,均向后移动 numNew 的距离。 System.arraycopy(elementData, index, elementData, index + numNew, numMoved); // 将 a 中的元素从 elementData 的 index 位置开始,其次复制到 elementData 中。 System.arraycopy(a, 0, elementData, index, numNew); // 列表中总元素个数更新。 size += numNew; return numNew != 0; } ## 5. ArrayList() 无参构造函数。 ## private static final int DEFAULT_CAPACITY = 10; public ArrayList() { // 创建空数组,此时 ArrayList 对象默认的 capacity = 10。 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } ## 6. 小问题 ## public class MyArrayListAdd { public static void main(String[] args){ ArrayList<String> demo = new ArrayList<>(); demo.add("diego"); demo.add("amos"); } } 三行代码,每执行一行,列表容量和数组的数组的长度是分别是多少? ArrayList<String> demo = new ArrayList<>(); 默认容量:10 ,空数组长度是:0 demo.add("diego"); 向空列表中 add 元素,需求容量是 1,默认容量是 10 ,取较大的,所以计算的最小容量是 10。因为 最小容量大于当前数组长度,要扩容,最终确认的容量也是 10,因此创建长度为 10 的数组,最后向里面追加一个元素。 容量:10,数组长度:10,但里面只有一个元素。 demo.add("amos"); 向非空列表中 add 元素,需求容量是 2,所以计算出来的最小容量直接是 2。因为计算出来的最小容量小于当前数组的长度。不需要扩容。直接在向数组中追加新元素。 容量:2,数组长度 10,里面有两个元素。 # 7. Vector 和 ArrayList 的区别是什么? # > **Vector 是线程安全版的 ArrayList。** 对比一下 add 方法的源码就能看清楚了 // Vector.java // synchronized 加锁 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } // ArrayList.java public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }
还没有评论,来说两句吧...