写在前面
数据结构在面试中基本都是常问的，但是一般开发中基本上都是在使用没有去关心过怎么实现的。
在数据结构中，链表是一种线性存储结构，也就是常说的线性表。
概念：线性表，是数据结构中的一种数据存储结构，数据元素之间具有“一对一”的逻辑关系。可以理解为把所有数据用一根线串起来，在存储到物理空间中。
顺序表 ArrayList
概念：将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）。类似下图用一个线把他们连接起来，形成一条线性的结构。
ArrayList 就是属于这样的一种。
ArrayList 是基于数组实现的，数组是一种最简单的数据结构，在使用时必须要给它创建大小，在日常开发中，往往我们是不知道给数组分配多大空间的，如果数组空间分配多了，内存浪费，分配少了，装不下。而 ArrayList 在使用时可以添加多个元素切不需要指定大小，因为 ArrayList 是动态扩容的。
类的继承关系
源码分析
类的属性
/** * 默认初始容量 */private static final int DEFAULT_CAPACITY = 10;
/** *ArrayList 实际数据存储的一个数组 *存储ArrayList的元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。 *添加第一个元素时，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。 */transient Object[] elementData;
/** * 共享的空数组实例，用于默认大小的空实例 */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * elementData 的大小 */private int size;
复制代码
类的构造函数
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
复制代码
new ArrayList()做了什么
public class TestClient {
public static void main(String[] args) { List<String> list = new ArrayList<>(); Integer capacity = getCapacity(list); System.out.println("没添加元素时的容量：" + capacity); System.out.println("没添加元素时的大小：" + list.size()); list.add("添加元素"); capacity = getCapacity(list); System.out.println("添加1个元素时的容量：" + capacity); System.out.println("添加1个元素时的大小：" + list.size()); }
/** * 通过反射获取list的容量 * * @param list * @return */ public static Integer getCapacity(List<String> list) { Integer length = null; Class c = list.getClass(); Field f; try { f = c.getDeclaredField("elementData"); f.setAccessible(true); Object[] o = (Object[]) f.get(list); length = o.length; } catch (NoSuchFieldException e) { e.printStackTrace(); } catch (IllegalAccessException e) { e.printStackTrace(); } return length; }}
复制代码
打印结果
没添加元素时的容量：0没添加元素时的大小：0添加1个元素时的容量：10添加1个元素时的大小：1
复制代码
因此，当 new ArrayList()时，默认会有一个空的 Object 空数组，在没有添加有元素的时候，其初始化容量是 0，只有当添加第一个元素的时候，容量才会设置成 10。
基本方法
添加元素 add(E e)
/** * 将指定的元素追加到此列表的末尾 */ public boolean add(E e) { ensureCapacityInternal(size + 1); //直接赋值 elementData[size++] = e; return true;}
复制代码
add(int index, E element)
在指定索引位置添加元素
String[] elementData = {"1", "2", "3", "4", "5", "6", "7", "8"};int index = 4;//从下标为4的位置开始复制，复制的长度为8-4=4(复制"5", "6", "7", "8")，从下标为4+1=5的位置开始替换为"5", "6", "7", "8"System.arraycopy(elementData, index, elementData, index+1, elementData.length-index);
复制代码
ArrayList 扩容机制
ensureExplicitCapacity(int minCapacity)
private void ensureExplicitCapacity(int minCapacity) { modCount++;
//如果其元素数量大于其容量，则进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }
复制代码
grow(int minCapacity)
/** * 扩容 * @param minCapacity */ private void grow(int minCapacity) { //原来的容量 int oldCapacity = elementData.length; //新的容量 通过位运算右移一位 如，默认为10 10>>1=5 右移过程：10的二进制为 1010 右移1位->0101 转十进制->5 //可以理解为oldCapacity >> 1 == oldCapacity/2 再加上原来的长度就扩容1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果大于ArrayList 可以容许的最大容量，则设置为最大容量 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
复制代码
想了解位运算的可以看看这篇文章：Java中的位运算
ArrayList 的内部实现，其实是用一个对象数组进行存放具体的值，然后用一种扩容的机制，进行数组的动态增长。
其扩容机制可以理解为，如果元素的个数，大于其容量，则把其容量扩展为原来容量的 1.5 倍。
拓展延伸
文章首发：ArrayList源码分析及扩容机制
公众号：Javatv
评论