Java面试重点--ArrayList 底层结构和证明采用Arraylist无参构造器的扩容机制

浅浅的花香味﹌ 2024-04-03 09:25 42阅读 0赞

### 先说明ArrayList的底层结构和操作分析 ###

1、ArrayList的底层结构是一个Object\[\] elementData，即一个Object类型的数组。  
2、创建ArrayList对象时，如果采用的是无参构造器，则数组初始空间为0，第一次添加数组空间扩容至10，如需再次扩容，则扩容至原数组空间的1.5倍。  
3、如果采用的是有参构造器，则数组初始空间为传入的参数值，如需再次扩容，则扩容至原数组空间的1.5倍。  
4、添加元素的顺序与取出元素的顺序相同。  
5、每个元素都有对应的索引，即可以通过索引查找元素。  
6、ArrayList可以添加多个null，也可以添加相同元素。

### ArrayList 底层源码分析 ###

##### 证明ArrayList的底层结构是一个Object类型的数组 #####

1、Debug进入ArrayList arrayList = new ArrayList(），分析ArrayList的底层结构

public ArrayList() {
        
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

2、再进入elementData，我们可以看见ArrayList的底层结构是一个Object\[\] elementData，即一个Object类型的数组。

transient Object[] elementData;

3、因为采用的是无参构造器，所以数组初始空间为0，为了证实我们进入DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };

4、如果采用的是有参构造器，例如：ArrayList arrayList1 = new ArrayList(8);，Debug进入

public ArrayList(int initialCapacity) {
        
            if (initialCapacity > 0) {
        
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
        
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
        
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

此时initialCapacity = 8，满足第一个if条件，所以elementData的初始空间为8。

##### 证明采用Arraylist无参构造器的扩容机制 #####

在ArrayList中加入20个元素

import java.util.ArrayList;
    
    public class Arraylist_ {
        
        public static void main(String[] args) {
        
            ArrayList arrayList = new ArrayList();
            for (int i = 1; i <= 20; i++) {
        
                arrayList.add(i);
            }
            System.out.println(arrayList);
        }
    }

###### 添加第1个元素 ######

1、Debug进入arrayList.add(i);

public boolean add(E e) {
        
            modCount++;
            add(e, elementData, size);
            return true;
        }

i = 1，所以e = 1。modCount = 1，size = 0。  
2、Debug进入add(e, elementData, size);  
e = 1，s = 0，因为采用的是无参构造器，所以数组初始空间为0，所以elementData.length = 0。  
所以满足s == elementData.length。

private void add(E e, Object[] elementData, int s) {
        
            if (s == elementData.length)
                elementData = grow();
            elementData[s] = e;
            size = s + 1;
        }

3、Debug进入grow()  
size = 0

private Object[] grow() {
        
            return grow(size + 1);
        }

4、Debug再次进入grow()  
minCapacity = size + 1 = 1，elementData.length = 0，所以oldCapacity = 0，elementData目前为空，DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA也是空，所以进入else语句，DEFAULT\_CAPACITY = 10，minCapacity = 1，因为是Math.max，所以选择10，所以elementData扩容至10个空间。

private Object[] grow(int minCapacity) {
        
            int oldCapacity = elementData.length;
            if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
                int newCapacity = ArraysSupport.newLength(oldCapacity,
                        minCapacity - oldCapacity, /* minimum growth */
                        oldCapacity >> 1           /* preferred growth */);
                return elementData = Arrays.copyOf(elementData, newCapacity);
            } else {
        
                return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
            }
        }

所以证明了创建ArrayList对象时，如果采用的是无参构造器，第一次添加数组空间扩容至10。

###### 添加第11个元素 ######

1、Debug进入arrayList.add(i);  
e = 11，modCount = 11，size = 10。

public boolean add(E e) {
        
            modCount++;
            add(e, elementData, size);
            return true;
        }

2、Debug进入add(e, elementData, size);  
e = 11，s = 10，因为已经添加了10个元素，所以elementData.length = 10，所以满足s == elementData.length

3、Debug进入grow()  
size = 10

private Object[] grow() {
        
            return grow(size + 1);
        }

4、Debug再次进入grow()  
minCapacity = size + 1 = 11，elementData.length = 10，所以oldCapacity = 10，所以满足oldCapacity > 0，进入if语句。  
oldCapacity = 10，minCapacity - oldCapacity = 1，oldCapacity >> 1 = 5

5、Debug进入newLength方法  
oldLength = 10，minGrowth = 1，prefGrowth = 5，所以newLength = prefGrowth + oldLength = 15，满足if条件，返回15，所以newCapacity = 15。

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        
            // assert oldLength >= 0
            // assert minGrowth > 0
    
            int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
            if (newLength - MAX_ARRAY_LENGTH <= 0) {
        
                return newLength;
            }
            return hugeLength(oldLength, minGrowth);
        }

6、返回grow()方法，执行return elementData = Arrays.copyOf(elementData, newCapacity);，进行数组的拷贝，所以elementData数组扩容至15，所以证明了创建ArrayList对象时，如果采用的是无参构造器，如需再次扩容，则扩容至原数组空间的1.5倍。