ArrayList和Vector源码角度分析增删查

左手的ㄟ右手 2023-05-31 12:25 24阅读 0赞

### ArrayList和Vector源码角度分析增删查 ###

*  1.初始化的角度有啥区别
 *  2.新增操作 （add）
 *  3.获取操作 （get），删除操作（clear、remove）
 *  4.总结

# 1.初始化的角度有啥区别 #

01： arrayList：从下面两张图可以看出来，arraylist的初始化调用了DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA方法，而DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA默认是一个空的数组。**也就是说arrayList初始化默认为空。但是，详情请见下文。**  
![在这里插入图片描述][20191025095915129.png]

![在这里插入图片描述][2019102510044780.png]  
01： vector：从下图可以看出，vector默认是初始容量为10.  
![在这里插入图片描述][20191025100918537.png]

# 2.新增操作 （add） #

**01：arrayList.add()方法**： 在调用arrayList.add()方法的时候，我们首先调用了ensureCapacityInternal方法，来保证内部容量够。调用ensureCapacityInternal方法之后，会先进行计算，调用calculateCapacity方法，其中calculateCapacity方法中的elementData就是很神奇了。如下面图一展示，我们看上面注释说明，任何空的arraylist数组elementData=DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，当第一次添加的时候，添加一个DEFAULT\_CAPACITY，DEFAULT\_CAPACITY在源码中默认为10。**也就是说我们在初始化容量之后，容量的确是为空的，但是，当我们添加第一个元素的时候，会给池子默认是10 的容量。** 接下来我们看一下，什么情况下会进行扩容，为了说明的更加清楚，我贴出源码 写注释

//如果我们传入的最小容量minCapacity，如果我们最小的预期容量减去底层数组容量小于0的话，则调用grow()方法进行扩容
    private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
    
    //oldCapacity 将老数组的容量赋值给变量保存
    //newCapacity oldCapacity >> 1 移位运算符，相当于右移除以2的1次方 再加上oldCapacity ，新的容量就等于旧容量的1.5倍。（PS：如果是左移的话，乘以2的N次方）
    //如果新的容量还比minCapacity小的话，就把minCapacity的值赋值给newCapacity，这步也是为了 计算新的容量时候出错。
    //下面再判断一下如果newCapacity的大小超过了最大数组容量（MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8），MAX_ARRAY_SIZE代表了要分配数组的最大大小，如果想分配更大的话，超出了虚拟机的限制。会出现OutOfMemoryError。
    //接下来调用hugeCapacity进行扩容，调用Arrays.copyOf进行数组复制。
    
     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);
        }

![在这里插入图片描述][20191025103832115.png]  
**02：vector.add()方法**： 这个和上面的arraylist都差不多呀，不同点为vector在方法上面加了synchronized，同步锁。这可以保证线程安全。 然后我们从源码角度分析 扩容方式。

//oldCapacity 获取到原数组容量大小
    //newCapacity capacityIncrement大于0就使用用户自己设置的扩容大小 newCapacity = oldCapacity + capacityIncrement 否者 newCapacity = oldCapacity * 2
    //扩容后还是小于最小容量，赋值 newCapacity = 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);
        }
    
    
    /** * The amount by which the capacity of the vector is automatically * incremented when its size becomes greater than its capacity. If * the capacity increment is less than or equal to zero, the capacity * of the vector is doubled each time it needs to grow. *capacityIncrement大于0就使用用户自己设置的扩容大小,如果他的容量小于或者等于0的时候，向量的容量自动增加2倍 * @serial */
        protected int capacityIncrement;

# 3.获取操作 （get），删除操作（clear、remove） #

**01：arrayList.get() :** 这个很简单呀，直接看源码

/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} * 先对传入的下标进行判断有没有越界，越界的话直接抛出IndexOutOfBoundsException异常，没有的话，直接在数组中根据下标返回对应的值。 */
        public E get(int index) { 
            rangeCheck(index);
            return elementData(index);
        }
    
    
     /** * Removes all of the elements from this list. The list will * be empty after this call returns. * 这个很简单，通过for循环，清空数组，size=0。 */
        public void clear() { 
            modCount++;
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
            size = 0;
        }
    
      /** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} * 先判断index是否合法，用oldValue 来存储旧值，先获取到旧值，然后返回旧值。 * int numMoved = size - index - 1; 解释，size是总容量大小，index是数组下标，从0开始的，所以要删除某个元素要加1，这样计算出要移动元素的数量，这个元素后面的全部向前移动，采用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;
        }
    
     /** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element 下面也是如果参数为空直接删除所有，参数不为空，删除指定位置上的值。 注意看 下面用到了一个fastRemove方法，字面意思快速删除，点进去看，其实就是绕过了边界检查rangeCheck。 */
        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;
        }

**02：vector.get() :**  
大同小异呀，跟arrayList的区别是 加了synchronized同步锁。

public synchronized E get(int index) { 
            if (index >= elementCount)
                throw new ArrayIndexOutOfBoundsException(index);
    
            return elementData(index);
        }

remove方法我这里就不多说了，基本都差不多，先进行校验，然后根据下标删除，删除以后，获取到要移动元素的位置和数量，移动元素，返回获取到的值。

# 4.总结 #

上面其实还有很多方法，我这里没有进行说明，大家感兴趣的可以自己了解下，不同的场景适合不同的方法，也许有些不常用的，大家要会区别对待。下面，我们做下总结：

<table> 
 <thead> 
  <tr> 
   <th>arrayList</th> 
   <th>vector</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>初始化容量是一个空数组</td> 
   <td>初始化是一个默认容量为10的数组</td> 
  </tr> 
  <tr> 
   <td>第一次add操作的时候，扩展容量为10。之后扩展容量为：原来的数组大小+原来数组大小的一半，也就是1.5倍</td> 
   <td>当增量为0，扩展为原来大小的两倍。不为0的时候，扩展原来大小，加上增量</td> 
  </tr> 
  <tr> 
   <td>多线程执行不安全</td> 
   <td>多线程执行是安全的，但是效率比较低</td> 
  </tr> 
  <tr> 
   <td>如果可以判断容量较小的话，用arraylist，因为空间不浪费</td> 
   <td>容量较大的话，用vector，每次扩容两倍</td> 
  </tr> 
 </tbody> 
</table>

其实：由上面我们可以看出，我们在初始化的时候，最好指定初始化容量，避免了每次进行数组复制，增加服务器开销和程序运行时间。

[20191025095915129.png]: /images/20230531/b24d6eca017149e890e4e6d4227b73a7.png
[2019102510044780.png]: /images/20230531/8e70cb619d814e85bee3fd7497e137d2.png
[20191025100918537.png]: /images/20230531/41fec9f81eae4b3d9c3434dc1d77feef.png
[20191025103832115.png]: /images/20230531/5940d3ac3e8a4fd28509dcbc8102fab8.png