集合-ArrayList

ArrayList：

• 基于数组实现可自动扩容的集合列表
• 允许插入NULL元素。
• 非线程安全
• 基于位置查询速度快, O(1)
• 指定位置新增和删除慢,涉及元素拷贝移动

add(E e)

向集合中添加元素，需要注意的是，由于列表初始化默认返回空数组，在进行扩容计算时加了特殊判断

// 数组允许的最大长度，文档给的解释是有些虚拟机会在数组中保留一些头信息，即数组前几位可能存储的不是真正的数据
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 在数组元素末尾新增元素
public boolean add(E e) {
      // 计算添加元素数组所需最小值，如果数组长度小于最小值则以1.5倍容量扩容，如果这里size=Integer.MAX_VALUE，则size + 1会溢出成为一个小于0的数
      ensureCapacityInternal(size + 1);
      elementData[size++] = e;
      return true;
}
// 扩容处理
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);
}
// 扩容代码
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 以1.5倍扩容得到扩容长度，这个扩容长度值是存在溢出风险的，因为int的最大值是2147483647
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 这里主要是针对使用默认构造器初始化时，延迟初始化数组，直到第一个元素写入时创建数组。
        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) {
        // 溢出处理，当前数组长度已经是Integer.MAX_VALUE了，无法继续添加元素，抛出异常
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
        // 虽然有数组最大值的兼容处理，但是还是可以继续扩容至Integer.MAX_VALUE
	return (minCapacity > MAX_ARRAY_SIZE) ?
		Integer.MAX_VALUE :
		MAX_ARRAY_SIZE;
}

逻辑

扩容逻辑是添加元素的难点和重点，因为这里做了溢出的逻辑处理，贴个图好理解一些，1431655765是一个临界值，扩容后会得到Integer.MAX_VALUE
假设当前数组 length = size = 1431655765，继续添加元素

1. 取得新增元素数组下标，minCapacity = size + 1 = 1431655766
2. 进入ensureExplicitCapacity方法 --> minCapacity - elementData.length = 1 > 0 --> 进入grow(minCapacity)方法
3. oldCapacity = 1431655765，newCapacity = 2147483647 = Integer.MAX_VALUE，第一个if不满足[if (newCapacity - minCapacity < 0)]，newCapacity - MAX_ARRAY_SIZE = 8，满足第二个if，进入hugeCapacity(minCapacity)方法
4. minCapacity > 0，minCapacity > MAX_ARRAY_SIZE 为 true， 返回 Integer.MAX_VALUE。
5. 执行elementData = Arrays.copyOf(elementData, newCapacity)，将原数组扩容复制到新数组。新数组容量为Integer.MAX_VALUE
6. 在1431655766设置元素值
7. 返回true，新增结束
   接着继续新增一个元素
8. 取得新增元素数组下标，minCapacity = size + 1 = -2147483648，
9. 进入ensureExplicitCapacity方法 --> minCapacity - elementData.length = 1 > 0 --> 进入grow(minCapacity)方法
10. oldCapacity = 2147483647，newCapacity = -1073741826，newCapacity - minCapacity = 1073741822 > 0, 第一个if不满足，newCapacity - MAX_ARRAY_SIZE = 1073741831 > 0，满足第二个if，进入hugeCapacity(minCapacity)方法
11. minCapacity = -2147483648 < 0，抛出异常

E remove(int index)

删除集合中指定位置的元素, 位置右边的元素会左移一位, 并置空末位元素

public E remove(int index) {
        // 边界校验
	rangeCheck(index);

	modCount++;
        // 获取指定位置元素
	E oldValue = elementData(index);

	int numMoved = size - index - 1;
        // 移动元素, elementData中index+1位置开始往后numMoved个元素复制到elementData中index开始往后numMoved个位置的元素, 即删除元素位置后边的元素左移一位
	if (numMoved > 0)
		System.arraycopy(elementData, index+1, elementData, index,
						 numMoved);
	elementData[--size] = null; // clear to let GC do its work

	return oldValue;
}

E set(int index, E element)

修改指定位置元素

public E set(int index, E element) {
	rangeCheck(index);

	E oldValue = elementData(index);
	elementData[index] = element;
	return oldValue;
}

boolean contains(Object o)

查询元素信息

public boolean contains(Object o) {
	return indexOf(o) >= 0;
}
public int indexOf(Object o) {
	if (o == null) {
		for (int i = 0; i < size; i++)
			if (elementData[i]==null)
				return i;
	} else {
		for (int i = 0; i < size; i++)
			if (o.equals(elementData[i]))
				return i;
	}
	return -1;
}

循环数组,比较查询值,返回下标

集合-ArrayList

原文：https://www.cnblogs.com/simple-ly/p/13965167.html