ArrayList底层结构和源码分析

ArrayList源码分析

1）允许添加任意的元素 包括null 多个

2） ArrayList是由数组来实现数据存储的

3）Array在多线程中是不安全的 建议使用vector

前言

数组是数据结构基本的数据结构 java封装了一系列数组的方法

数组中存储的内存是连续的 插入和删除困难 查询方便

• ArrayList中维护了一个Object类型的数组elementData
• 无参构造器：自动扩容机制 ele->0（default）->10（First add）->15(second add)->15x1.5->15x1.5x1.5
• 有参构造器：指定大小（size）->size*1.5(First add) -> sizex1.5X1.5(second add)

源码

• Tip：英语对于看源码和理解有一定的帮助

构造方法

     public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];//创建指定长度的object数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;  //空数组
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
        public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }


 public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray(); //将集合转换成数组
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) { //如果不是object数组类型
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);//拷贝一下
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }
    

add方法

/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {      
   //改进后的直接自增
    modCount++;
    add(e, elementData, size);
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */

//指定位置添加
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    //将index之后的所有元素移动一位
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
    
}

//扩容的入口方法 DEFAULTCAPACITY_EMPTY_ELEMENTDATA  默认为10
//判断是你的值大还是它的值大 就返回你的值
public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }


//数组扩容方法
   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)];
        }
    }

    private Object[] grow() {
        return grow(size + 1);
    }
//第一次其实是  0*any=0    
//用0.5倍来扩容

modCount++;用来记录修改的记录

return elementData = Arrays.copyOf(elementData, newCapacity);

进行扩容

使用扩容机制来确定扩容到多大