本文出自：https://blog.csdn.net/DT235201314/article/details/79867960
一丶概述
面试：说说HashMap的底层实现原理？
小明：Android开发平时用ArrayList就够了，很少用HashMap。
面试：那你说说ArrayList
小明：。。。。
面试都喜欢问HashMap底层原理，而ArrayList是最长用到的，先说说ArrayList
二丶源码与原理
1.初始化
/**
* ArrayList初始化默认容量大小为10，见无参构造函数。
*/
private static final int DEFAULT_CAPACITY =
10;
/**
* 空实例共享的空数组实例。
*/
private static final Object[]
EMPTY_ELEMENTDATA = {}
;
/**
* ArrayList成员存储在这个数组缓冲区中。
* 容量大小是这个缓冲区的长度
* 在添加第一个成员时都会扩充到DEFAULT_CAPACITY大小，即容量为10。
* transient这个关键字告诉我们该对象在序列化的时候请忽略这个元素
*/
transient Object[]
elementData;
/**
* 逻辑长度
*/
private int size;
/**
* 传入长度
*/
public ArrayList(
int initialCapacity) {
super()
;
if (initialCapacity <
0)
throw new IllegalArgumentException(
"Illegal Capacity: "+
initialCapacity)
;
this.
elementData =
new Object[initialCapacity]
;
}
/**
* 初始化长度为10的数组
*/
public ArrayList() {
super()
;
this.
elementData =
EMPTY_ELEMENTDATA;
}
/**
*创建一个包含collection的ArrayList
*/
public ArrayList(Collection<?
extends E> c) {
elementData = c.toArray()
;
size =
elementData.
length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (
elementData.getClass() != Object[].
class)
elementData = Arrays.
copyOf(
elementData, size, Object[].
class)
;
}
说名：1：ArrayList底层是Object[]数组；2.空ArrayList指向同一个空数组,3.默认长度为10;
2.add方法：当ArrayList加入对象呢？
/**返回永远为true 无限扩容*/
public boolean add(
E e) {
// 确定ArrayList的容量大小
ensureCapacityInternal(
size +
1)
; // Increments modCount!!
//添加e到ArrayList中
elementData[
size++] = e
;
return true;
}
/**指定位置添加元素*/
public void add(
int index
, E element) {
if (index >
size || index <
0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index))
;
ensureCapacityInternal(
size +
1)
; // Increments modCount!!
System.
arraycopy(
elementData, index
, elementData, index +
1,
size - index)
;
elementData[index] = element
;
size++
;
}
/**添加一个元素*/
public void add(
E e) {
if (
modCount !=
expectedModCount)
throw new ConcurrentModificationException()
;
try {
int i =
cursor;
ArrayList.
this.add(i
, e)
;
cursor = i +
1;
lastRet = -
1;
expectedModCount =
modCount;
limit++
;
}
catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException()
;
}
}
/**确定ArrarList的容量*/
private void ensureCapacityInternal(
int minCapacity) {
if (
elementData ==
EMPTY_ELEMENTDATA) {
minCapacity = Math.
max(
DEFAULT_CAPACITY, minCapacity)
;
}
ensureExplicitCapacity(minCapacity)
;
}
/**判断是否需要扩容*/
private void ensureExplicitCapacity(
int minCapacity) {
modCount++
;
// overflow-conscious code
if (minCapacity -
elementData.
length >
0)
grow(minCapacity)
;
}
3.ArrayList扩容原理
/**扩容1.5倍，并重新copy值*/
private void grow(
int minCapacity) {
// overflow-conscious code
int oldCapacity =
elementData.
length;
// 若ArrayList的容量不足以容纳当前的全部元素则*1.5，设置 新的容量=“oldCapacity + (oldCapacity >> 1)
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)
;
}
人工数组扩容方法图解(换成ArrayList的话这里大小控制为1.5倍，就对啦)：
4.Arrays.copyof()和System.arraycopy()方法
Arrays.copyof()
public static <
T>
T[]
copyOf(
T[] original
, int newLength) {
return (
T[])
copyOf(original
, newLength
, original.getClass())
;
}
public static <
T,U>
T[]
copyOf(
U[] original
, int newLength
, Class<?
extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].
class)
? (
T[])
new Object[newLength]
: (
T[]) Array.
newInstance(newType.getComponentType()
, newLength)
;
System.
arraycopy(original
, 0, copy
, 0,
Math.
min(original.
length, newLength))
;
return copy
;
}
System.arraycopy()
/**
*native修饰为用其它语言（C/C++）实现方法
* @param src 要拷贝的数组
* @param srcPos 要拷贝数组起始位置
* @param dest 目标数组
* @param destPos 目标数组要拷贝的起始位置
* @param length 要拷贝长度
*/
public static native void arraycopy(Object src
, int srcPos
,
Object dest
, int destPos
,
int length)
;
5.其他方法（略）
fill ：填充元素
remove：删除元素，后面元素会前移
fastremove：截取后部分
......
6.特点
7.时间复杂度
底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)。
三丶推荐文章：
ArrayList初始化 - Java那些事儿
ArrayList底层数组扩容原理 - Java那些事儿专栏
时间复杂度 - Java那些事儿专栏
三顾ArrayList
ArrayList的时间复杂度 - Java那些事儿专栏
迄今为止看过最好的系列文章，可惜更新速度不快
