ArrayList/Vector/Stack底层分析

迈不过友情╰ 2022-05-09 10:00 68阅读 0赞

## ArrayList ##

`ArrayList` 实现于 `List`、`RandomAccess` 接口。可以插入空数据`null`，也支持随机访问。

`List`接口中的特有的增删改查：  
增：`add( int index , Object element )`  
删：`remove( int index )` //注意是下标而不是元素  
改：`set( int index , Object newElement )`  
查：`get(int index)`

--------------------

`ArrayList`相当于动态数据，其中最重要的两个属性分别是:  
`elementData` 数组，以及 `size` 大小。

### add ###

在调用 `add()` 方法的时候：

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

*  首先进行扩容校验。
 *  将插入的值放到尾部，并将 size + 1 。

如果是调用 `add(index,e)` 在指定位置添加的话：

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //复制，向后移动 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

*  也是首先扩容校验。
 *  接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。

其实扩容最终调用的代码:

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 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); }

也是一个数组复制的过程。

### remove ###

删除指定下标index的元素:

public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }

*  检验下标是否越界
 *  修改次数 modCount++, 保证线程安全
 *  需要移动的元素的个数,若大于0,移动元素`void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)`
 *  将最后一个元素(移动过后的)置空,交给GC

删除指定元素:可以删除null(因为可以存入null)

public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }

### modCount注释 ###

int java.util.AbstractList.modCount 来自AbstractList

> The number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.

> This field is used by the iterator and list iterator implementation returned by the iterator and listIterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations. `This provides fail-fast behavior`, rather than non-deterministic behavior in the face of concurrent modification during iteration.

> Use of this field by subclasses is `optional.` If a subclass wishes to provide fail-fast iterators (and list iterators), then it merely has to increment this field in its add(int, E) and remove(int) methods (and any other methods that it overrides that result in structural modifications to the list). A single call to add(int, E) or remove(int) must add no more than one to this field, or the iterators (and list iterators) will throw bogus ConcurrentModificationExceptions. If an implementation does not wish to provide fail-fast iterators, this field may be ignored.

[java中fail-fast 和 fail-safe的区别][java_fail-fast _ fail-safe]

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>Fail Fast Iterator</th> 
   <th>Fail Safe Iterator</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Throw ConcurrentModification Exception(抛异常?)</td> 
   <td>Yes</td> 
   <td>No</td> 
  </tr> 
  <tr> 
   <td>Clone object(克隆被操作对象?)</td> 
   <td>No</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>Memory Overhead(内存开销)</td> 
   <td>No</td> 
   <td>Yes</td> 
  </tr> 
  <tr> 
   <td>Examples(栗子)</td> 
   <td>HashMap,Vector,<br>ArrayList,HashSet</td> 
   <td>CopyOnWriteArrayList,<br>ConcurrentHashMap</td> 
  </tr> 
 </tbody> 
</table>

### get ###

查询方法源码: 可见底层是使用数组的访问方式

E elementData(int index) { return (E) elementData[index]; } public E get(int index) { rangeCheck(index); return elementData(index); }

### set ###

public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }

*  check Index
 *  替换元素,返回旧元素

由此可见 `ArrayList` 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。

### 序列化 ###

由于 ArrayList 是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 `transient` 修饰，可以防止被自动序列化。

transient Object[] elementData;

因此 ArrayList 自定义了序列化与反序列化：

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. //只序列化了被使用的数据 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } }

> 当对象中自定义了 writeObject 和 readObject 方法时，JVM 会调用这两个自定义方法来实现序列化与反序列化。

从实现中可以看出 ArrayList 只序列化了被使用的数据。

### RandomAccess ###

RandomAccess 是一个空接口,实现它有什么用处呢?

public interface RandomAccess { }

在接口的注释中指明:

*  它标志着接口支持快速访问(时间复杂度通常为常数n);但迭代的时候,如果对象实现了RandomAccess,那么就可以使用更高性能的迭代方式;
 *  **for循环比Iterator速度快**;

> Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

> The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

> It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:  
> for (int i=0, n=list.size(); i < n; i++)  
> list.get(i);  
> runs faster than this loop: for (Iterator i=list.iterator(); i.hasNext(); )  
> i.next();

## Vector ##

`Vector` 内部有两个重要的参数，一个是elementCount代表当前元素个数，一个是capacityIncrement，代表当列表元素满了之后增加的容量。**如果不设置capacityIncrement，那么Vector容量扩展时默认将扩展两倍**，在ArrayList源码分析中，我们知道ArrayList在扩容时默认将扩展1.5倍，所是ArrayList与Vector的一个区别。

`Vector` 也是实现于 `List` 接口，底层数据结构和 `ArrayList` 类似,也是一个动态数组存放数据。不过是在 `add()` 方法的时候使用 `synchronized` 进行同步写数据，但是开销较大，所以 `Vector` 是一个同步容器并不是一个并发容器。

### add(E e) ###

以下是 `add()` 方法：

public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }

private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

扩容算法:

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //如果没有设置capacityIncrement ,那么扩展为原来的两倍 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }

### add(int index, E element) ###

以及指定位置插入数据:

public void add(int index, E element) { insertElementAt(element, index); } public synchronized void insertElementAt(E obj, int index) { modCount++; if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = obj; elementCount++; }

## Stack ##

> Stack 是Vector的子类;class Stack extends Vector

Stack方法:

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>修饰符</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>push(E item)</td> 
   <td>无</td> 
   <td>使用Vector的addElement(item)方法<br>返回item</td> 
  </tr> 
  <tr> 
   <td>pop</td> 
   <td>synchronized</td> 
   <td>弹出栈顶元素(移除)</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>synchronized</td> 
   <td>返回栈顶元素(删除)</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>无</td> 
   <td>是否为空</td> 
  </tr> 
  <tr> 
   <td>search(Object o)</td> 
   <td>synchronized</td> 
   <td>查找是否有对象o</td> 
  </tr> 
 </tbody> 
</table>

Stack内部一共五个方法，其中三个方法都加了synchronized关键字，是线程安全的，而push和empty方法调用了Vector的方法，由于Vector中的addElement()和size()方法都是线程安全的，所以Stack的每个方法也都是线程安全的，所以它和Vector一样，都是线程安全的。

--------------------

参考:  
[https://github.com/crossoverJie/JCSprout/blob/master/MD/ArrayList.md][https_github.com_crossoverJie_JCSprout_blob_master_MD_ArrayList.md]

[java_fail-fast _ fail-safe]: https://blog.csdn.net/ch717828/article/details/46892051
[https_github.com_crossoverJie_JCSprout_blob_master_MD_ArrayList.md]: https://github.com/crossoverJie/JCSprout/blob/master/MD/ArrayList.md