Vector扩容机制源码分析

左手的ㄟ右手 2024-04-18 21:08 78阅读 0赞

再来稍微聊一下Vector的特点。

Vector继承树如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]

（1）允许null值

（2）底层使用动态对象数组Object\[\] elementData

（3）默认初始容量是10，也可通过构造函数指定初始容量（实际分配值）

（4）线程安全，通过synchronized锁得以保证

（5）fail-fast机制

（6）扩容与capacityIncrement参数相关，若此参数大于0，则按该值扩增容量，否则，成倍扩增

（7）如果需要扩容，则先扩容，再插入元素。

以addElement方法为例：

/** * Adds the specified component to the end of this vector, * increasing its size by one. The capacity of this vector is * increased if its size becomes greater than its capacity. * * <p>This method is identical in functionality to the * {@link #add(Object) add(E)} * method (which is part of the {@link List} interface). * * @param obj the component to be added */
        public synchronized void addElement(E obj) { 
            modCount++;
            ensureCapacityHelper(elementCount + 1);
            elementData[elementCount++] = obj;
        }
        
    	/** * This implements the unsynchronized semantics of ensureCapacity. * Synchronized methods in this class can internally call this * method for ensuring capacity without incurring the cost of an * extra synchronization. * * @see #ensureCapacity(int) */
        private void ensureCapacityHelper(int minCapacity) { 
        	//容量保证，数组容量满了之后才会触发扩容
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

再看扩容方法的核心：

/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        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);
        }
    
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

<table> 
 <tbody> 
  <tr> 
   <td align="left"><font><b>关于Stack<b></b></b></font></td> 
  </tr> 
 </tbody> 
</table>

Stack的继承树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70 1]  
Stack继承了Vector，也是线程安全的，方法上使用了synchronized锁。正如它的名字，它是一种先进后出的栈结构。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/dd207869422140c4a5daf1e3601179c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3ba0f93d10a84002b77e6533250b0749.png