arrayList 的底层实现疑问解析

ゝ一世哀愁。 2023-05-28 11:24 11阅读 0赞

参考代码位置：[https://blog.csdn.net/leinminna/article/details/105110253][https_blog.csdn.net_leinminna_article_details_105110253]

### 1.arrayList类的结构和设计理念 ###

一段连续内存的数组，是arrayList的底层；  
底层数组扩容：  
数组容量，每次指定位置扩容后变为之前的1.5倍，arrayList的size不一定等于底层数组的容量，而是实际存储的元素的个数；

/** * 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;
    
        /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
        private void grow(int minCapacity) { 
            // overflow-conscious code
            // 底层数组原始容量
            int oldCapacity = elementData.length;
            // 容量变为之前的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 扩容1.5被之后还不满足当前所需的最小容量，直接采用实际所需长度；
            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;
        }

### 2.modCount 数结构操作次数 ###

用于记录数组结构的变化次数，如新增或删除元素，用于防止数组使用iteraor遍历时同时被修改；

// 设置数组真实容量
        private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        // 获取数组最小容量
        private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
        
        // 设置数组最小容量
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++; // 数组长度修改次数
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

### 3.实际使用的list和他的底层数组 ###

arrayList的底层数组是elementData，arrayList的允许的存储元素所占的内存位置是elementData\[0\]到ementData\[size-1\]。  
底层数组的长度是elementData.length,通常是arrayList.size()的1.5倍。

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
        public boolean add(E e) { 
        	// 设置底层数组真实容量
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            // 设置数组长度属性，加1； 数组最后一个元素赋值；
            // 等于将之前的arrayList扩容1；
            elementData[size++] = e;
            return true;
        }

4.arrayList类中继承的类有哪些？各有哪些实现和功能？  
5.arrayList类中实现的接口有哪些？各有哪些实现和功能？

持续更新中。。。

[https_blog.csdn.net_leinminna_article_details_105110253]: https://blog.csdn.net/leinminna/article/details/105110253