Java基础汇总（十三）——ArrayList，Vector和stack

Myth丶恋晨 2024-04-06 13:43 76阅读 0赞

**一、ArrayList**

**1.定义**

**ArrayList：实现List接口的动态数组**

*  **动态：Arraylist的大小是可变的**
 *  **实现了所有可选列表操作**
 *  **允许包括 null 在内的所有元素**
 *  **提供一些方法来操作内部用来存储列表的数组的大小**
 *  **ArrayList实现不是同步的（即它不是线程安全）**

**ArrayList容量：**每个ArrayList实例都有一个容量，该容量是指**用来存储列表元素的数组的大小**

*  **ArrayList的默认初始容量为10**
 *  ArrayList中元素的增加，它的容量也会不断的自动增长
 *  在每次添加新的元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作带来数据向新数组的重新拷贝。所以如果我们**知道具体业务数据量，在构造ArrayList时可以给ArrayList指定一个初始容量**，这样就会减少扩容时数据的拷贝问题。**当然在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量**，这可以减少递增式再分配的数量

**2. ArrayList的继承关系**

*  **继承AbstractList抽象父类**
 *  **实现了List接口（规定了List的操作规范）**
 *  **实现了RandomAccess（可随机访问）**
 *  **实现了Cloneable（可拷贝）**
 *  **实现了Serializable（可序列化）**

**3.底层数据结构**

*  **ArrayList的底层是一个object数组，并且由trasient修饰**
 *  **ArrayList底层数组不会参与序列化，而是使用重写writeobject方法进行序列化**
 *  **使用重写writeobject方法进行序列化的原因：节省空间（只复制数组中有值的位置，其他未赋值的位置不进行序列化）**

**4.增删改查**

**在指定位置增加元素（本质为数组元素的复制）**

*  **添加元素时，首先判断索引是否合法**
 *  **其次检测是否需要扩容**
 *  **最后使用System.arraycopy方法来完成数组的复制**

//System.arraycopy()方法的原型
    public static void arraycopy
    (Object src, int srcPos, Object dest, int destPos, int length)

**arraycopy方法是将源数组src从srcPos位置开始复制到dest数组中，复制长度为length，数据从dest的destPos位置开始粘贴**

//在指定位置增加元素
    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++;
    }

**删除指定位置元素（本质为元素复制）**

*  **判断索引是否和法**
 *  **删除的方式是把被删除元素右边的元素左移，方法同样是使用System.arraycopy进行拷贝**

//删除指定位置元素
    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;
    }

**清空数组（将所有元素置为null，这样就可以让GC自动回收掉没有被引用的元素）**

//        /**
    //         * Removes all of the elements from this list.  The list will
    //         * be empty after this call returns.
    //         */
    public void clear() {
        modCount++;
    
    //clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

**修改指定位置元素**

*  **判断索引是否和法**
 *  **进行修改操作**

//修改指定位置元素
    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

**rangecheck方法()**

*  **检查下标是否越界**

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

**modcount**

由对ArrayList增删改查操作可知，**在一个迭代器初始的时候，会赋予它调用这个迭代器的对象的modCount，即在迭代器初始化过程中会将modCount值赋给迭代器的 expectedModCount，在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 ArrayLis**t

所以在遍历那些非线程安全的数据结构时，建议尽量使用迭代器

*  **Fail-Fast 机制（如果ArrayList不是线程安全的，抛出ConcurrentModificationException异常）**
 *   **modcount为对ArrayList内容的修改次数（只要修改ArrayList内容，modcount值增加）**

final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

**5.初始容量和扩容方式**

**ArrayList初始容量为10**

例1（扩容方法）：

//        private static final int DEFAULT_CAPACITY = 10;
    
    //扩容发生在add元素时，传入当前元素容量加一
       public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    
    //这里给出初始化时的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    //这说明：如果数组还是初始数组，那么最小的扩容大小就是size+1和初始容量中较大的一个，
    //初始容量为10。
    //因为addall方法也会调用该函数，所以此时需要做判断。
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }
    
    //开始精确地扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
         //如果此时扩容容量大于数组长度，执行grow，否则不执行。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

*  由上述代码可知，**ArrayList真正执行扩容的方法为grow()方法**
 *  **扩容方式是让新容量等于旧容量的1.5倍**（1.5倍的扩容是最好的倍数。因为**一次性扩容太大**(如2.5倍)**可能会浪费更多的内存**(1.5倍最多浪费33%，2.5倍最多会浪费60%，3.5倍则会浪费71%……)。但**一次性扩容太小，需要多次对数组重新分配内存，对性能消耗比较严**重。所以**1.5倍刚刚好，既能满足性能需求，也不会造成很大的内存消耗**。）

**？？？未懂：当新容量大于最大数组容量时，执行大数扩容**

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

**当新容量大于最大数组长度，两种情况**

*  **溢出，抛异常**
 *  **没溢出，返回整数的最大值**

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

**trimToSize()方法**

*  **最小化ArrayList实例的存储量**

除ensureCapacity()这个扩容数组外，ArrayList还提供了将**底层数组的容量调整为当前列表保存的实际元素的大小的功能**

public void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

**二、Vector**

**1.定义**

**Vector：可以实现可增长的对象数组**（与数组一样，它包含可以使用整数索引进行访问的组件）

*  **vector大部分方法都使用了synchronized修饰符，所以是线层安全的集合类**
 *  **Vector实现List接口，继承AbstractList类，所以我们可以将其看做队列，支持相关的添加、删除、修改、遍历等功能**
 *  **Vector实现RandmoAccess接口，即提供了随机访问功能，提供提供快速访问功能（在Vector中可以直接访问元素）**
 *  **Vector 实现了Cloneable接口，支持clone()方法，可以被克隆**
 *  **vector底层数组不加transient，序列化时会全部复制**

protected Object[] elementData;
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            final java.io.ObjectOutputStream.PutField fields = s.putFields();
            final Object[] data;
            synchronized (this) {
                fields.put("capacityIncrement", capacityIncrement);
                fields.put("elementCount", elementCount);
                data = elementData.clone();
            }
            fields.put("elementData", data);
            s.writeFields();
        }

Vector除了iterator外还提供Enumeration枚举方法（较为过时）

public Enumeration<E> elements() {
        return new Enumeration<E>() {
            int count = 0;
    
            public boolean hasMoreElements() {
                return count < elementCount;
            }
            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }

**2.Vector中的增删改查**

**vector的增删改查既提供了自己的实现，也继承了abstractList抽象类的部分方法**

//查找指定位置元素
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        return elementData(index);
    }
    
    //修改指定位置元素
    public synchronized void setElementAt(E obj, int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                    elementCount);
        }
        elementData[index] = obj;
    }
    
    //删除指定位置元素
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                    elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }
    
    //在指定位置插入指定元素
    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++;
    }
    
    //在列表末尾加入指定元素
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

**3.Vector初始容量和扩容**

**扩容方式与ArrayList基本一样，但扩容时不是1.5倍扩容，而是有一个扩容增量capacityIncrement**

protected int elementCount;
    
    protected int capacityIncrement;
    }
    public Vector() {
        this(10);
    }

*  **如果在创建Vector时，指定了capacityIncrement的大小，则：**
    
     *  **每次当Vector中动态数组容量增加时，增加的大小都是capacityIncrement**
     *  **如果容量的增量小于等于零，则每次需要增大容量时，向量的容量将增大一倍**

public synchronized void ensureCapacity(int minCapacity) {
        if (minCapacity > 0) {
            modCount++;
            ensureCapacityHelper(minCapacity);
        }
    }
    
    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;
        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);
    }

**三、Stack**

**1.Stack类：后进先出（LIFO）的对象堆栈（采用典型的先进后出的操作方式完成的）**

*  **Stack类继承Vector类**
 *  **Stack通过五个操作对Vector进行扩展（Stack类在Vector基础上仅有一个构造方法，五个实现方法（从Vector继承而来的方法不算与其中）），允许将Vector视为堆栈**
    
     *  **empty()：测试堆栈是否为空**
     *  **peek()：查看堆栈顶部的对象，但不从堆栈中移除它**
     *  **pop()：移除堆栈顶部的对象，并作为此函数的值返回该对象**
     *  **push(E item)：把项压入堆栈顶部**
     *  **search(Object o)：返回对象在堆栈中的位置，以 1 为基数**

/**
     * 构造函数
     */
    public Stack() {
    }
    
    /**
     *  push函数：将元素存入栈顶
     */
    public E push(E item) {
        // 将元素存入栈顶。
        // addElement()的实现在Vector.java中
        addElement(item);
    
        return item;
    }
    
    /**
     * pop函数：返回栈顶元素，并将其从栈中删除
     */
    public synchronized E pop() {
        E    obj;
        int    len = size();
    
        obj = peek();
        // 删除栈顶元素，removeElementAt()的实现在Vector.java中
        removeElementAt(len - 1);
    
        return obj;
    }
    
    /**
     * peek函数：返回栈顶元素，不执行删除操作
     */
    public synchronized E peek() {
        int    len = size();
    
        if (len == 0)
            throw new EmptyStackException();
        // 返回栈顶元素，elementAt()具体实现在Vector.java中
        return elementAt(len - 1);
    }
    
    /**
     * 栈是否为空
     */
    public boolean empty() {
        return size() == 0;
    }
    
    /**
     *  查找“元素o”在栈中的位置：由栈底向栈顶方向数
     */
    public synchronized int search(Object o) {
        // 获取元素索引，elementAt()具体实现在Vector.java中
        int i = lastIndexOf(o);
    
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

**四、总结**

**1.ArrayList的优缺点**

*  **ArrayList的优点：**
    
     *  **ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快**
     *  **ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已**
 *  **ArrayList的缺点：**
    
     *  **删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能**
     *  **插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能**

**因此，ArrayList比较适合顺序添加、随机访问的场景**

**2.ArrayList和Vector的区别**

*  **ArrayList是线程非安全的，Vector（实现90%和ArrayList都完全一样）因有synchronized修饰，所以其为线程安全的**

**保证ArrayList线程安全：**

**使用Collections.synchronizedList方法把你的ArrayList变成一个线程安全的List**

List<String> synchronizedList = Collections.synchronizedList(list);
    synchronizedList.add("aaa");
    synchronizedList.add("bbb");
    for (int i = 0; i < synchronizedList.size(); i++)
    {
        System.out.println(synchronizedList.get(i));
    }

*  **Vector可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小\*2**

int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);

参考文章：

[Java-Tutorial/Java集合详解1：一文读懂ArrayList,Vector与Stack使用方法和实现原理.md at master · h2pl/Java-Tutorial · GitHub][Java-Tutorial_Java_1_ArrayList_Vector_Stack_.md at master _ h2pl_Java-Tutorial _ GitHub]

[Java-Tutorial_Java_1_ArrayList_Vector_Stack_.md at master _ h2pl_Java-Tutorial _ GitHub]: https://github.com/h2pl/Java-Tutorial/blob/master/docs/java/collection/Java%E9%9B%86%E5%90%88%E8%AF%A6%E8%A7%A31%EF%BC%9A%E4%B8%80%E6%96%87%E8%AF%BB%E6%87%82ArrayList,Vector%E4%B8%8EStack%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95%E5%92%8C%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86.md