我要评论
arraylist扩容原理
arraylist底层数据结构是数组！！！
数组的特点：固定长度，顺序存储，有下标，可重复。
代码
源码
追进arraylist源码
得到：
追入：defaultcapacity_empty_elementdata
得到：-- 意思是：创建一个final修饰的object类型的空的常量数组。
总结：
将空数组赋值给elementdata这个属性。此时elementdata数组是空的。defaultcapacity_empty_elementdata数组也是空的。
第一次追进add源码
得到：
- (e e)：就是你传入的 "aa" 。
- size：现在等于0。
追入：ensurecapacityinternal
得到：
mincapacity：就等于 （size + 1）。--现在等于1。
然后利用 if判断，前面提到过，elementdata是defaultcapacity_empty_elementdata赋值得到的，所以现在它们两个相等。
条件成立，就进入，math.max(default_capacity, mincapacity)意思是取括号里的较大的值，咱们现在知道mincapacity的值是1，所以现在追进default_capacity的源码去看看：
default_capacity的值是10。
所以这行代码的意思是：
mincapacity = math.max(default_capacity, mincapacity);
将10重新赋值给mincapacity。
此时 mincapacity：等于10。
继续执行下一条语句：
追入：ensureexplicitcapacity
此时 mincapacity =10。
第一条语句：modcount++；追进去看看：
发现 modcount =0。
然后判断mincapacity - elementdata.length是否大于 0 。因为前面说过elementdata数组是空的，所以 10 - 0是大于 0的。
条件成立，执行grow(mincapacity);
追入：grow
注意：重点来了
此时 mincapacity = 10。
语句：int oldcapacity = elementdata.length;
此时 oldcapacity = 0。
语句：int newcapacity = oldcapacity + (oldcapacity >> 1);
位运算符：>>意思是 / 2。 <<的意思是 * 2。
此时newcapacity = 0。
语句：if (newcapacity - mincapacity < 0)
newcapacity = mincapacity;
判断 0 - 10是否小于 0 。
条件成立，执行：newcapacity = mincapacity;
此时newcapacity = 10。
语句：if (newcapacity - max_array_size > 0)
newcapacity = hugecapacity(mincapacity);
判断 10 -max_array_size是否大于 0。
max_array_size = 2147483639。
条件不成立，不执行：newcapacity = hugecapacity(mincapacity);
继续往下走。
语句：elementdata = arrays.copyof(elementdata, newcapacity);
新数组 = arrays.copyof（旧的数组，新数组的长度）：意思是复制数组，将旧数组复制到新的数组。
此时elementdata数组长度为 10。
然后返回到二、第一次追进add源码执行下一条语句
elementdata[size++] = e;
- 前面说过size = 0；e = "aa"；
- 所以：elementdata[0] = "aa";
- 然后size++
- 此时 size = 1。
第一遍追进之后数据的改变
- size = 1。
- elementdata数组长度为 10。
- newcapacity = 10。
- modcount = 1。
第二次追进add源码
得到：
此时size = 1。
追入：ensurecapacityinternal
此时mincapacity =size + 1。
mincapacity = 2。
判断 elementdata 和defaultcapacity_empty_elementdata是否相等，因为经过第一次赋值导致 elementdata已经是 10了。所以条件不成立，不执行里面的语句。
继续执行下一条语句。
追入：ensureexplicitcapacity
得到：
此时modcount = 1。
判断 mincapacity -elementdata.length是否大于 0 。
因为此时elementdata数组长度为 10。所以条件不成立，不执行里面语句。
所以此时返回到三、第二次追进add源码执行下一条语句。
elementdata[size++] = e;
前面说过size = 1；e = "bb"；
- 所以：elementdata[1] = "bb";
- 然后size++
- 此时 size = 2。
第二遍追进之后数据的改变
- size = 2。
- elementdata数组长度为 10。
- newcapacity = 10。
- modcount = 2。
第十遍追进之后数据的改变
size = 10。
elementdata数组长度为 10。
newcapacity = 10。
modcount = 10。
第十一次追进add源码
得到：
此时size = 10 。
追入：ensurecapacityinternal
- 此时mincapacity =size + 1 。
- mincapacity = 11 。
- 判断 elementdata 和defaultcapacity_empty_elementdata是否相等，因为经过前面赋值导致 elementdata已经是 10了。所以条件不成立，不执行里面的语句。
- 继续执行下一条语句。
追入：ensureexplicitcapacity
- 此时modcount = 10。
- 判断 mincapacity -elementdata.length是否大于 0 。
- 因为 mincapacity = 11 。elementdata数组长度为 10 。所以条件成立，执行里面的语句。
追入：grow
重点：
此时mincapacity = 11 。elementdata.length = 10 。
语句：int oldcapacity = elementdata.length;
此时oldcapacity = 10 。
语句：int newcapacity = oldcapacity + (oldcapacity >> 1);
意思是：newcapacity = 10 + （10除以 2）
此时newcapacity = 15 。
语句：if (newcapacity - mincapacity < 0)
newcapacity = mincapacity;
判断 15 - 11是否小于 0 。
不小于，所以不执行里面的语句：newcapacity = mincapacity;
语句：if (newcapacity - max_array_size > 0)
newcapacity = hugecapacity(mincapacity);
判断 15-max_array_size是否大于 0。
max_array_size = 2147483639。
条件不成立，不执行：newcapacity = hugecapacity(mincapacity);
继续往下走。
语句：elementdata = arrays.copyof(elementdata, newcapacity);
意思是：新数组 =arrays.copyof（老数组，新数组长度）;
elementdata = arrays.copyof(elementdata,15);
所以这是后 elementdata 数组长度为 15 。
然后返回到四、第十一次追进add源码执行下一条语句
elementdata[size++] = e;
所以：elementdata[10] = "第十一次";
然后size++
此时 size = 11。
总结
1、底层创建了一个 object[]的数组。数组名：elementdata。此数组中没有元素。
2、通过list.add 调用 grow()扩容方法，数组长度变为10。
3、在数组存满之前 list.add中不会再调用grow()扩容方法了。
4、当第十一次存入时，list.add再次调用grow()扩容方法。
数组长度会变为原数组长度的1.5倍。
5、扩容不是在老数组基础上拼接的，而是创建了一个1.5倍长度的新数组。
并把老数组的元素复制到新数组。
面试时参考话术
arraylist底层数据结构是数组，当创建arraylist对象时，底层初始化了一个空数组，数组是object类型，数组名是elementdata。
当第一次添加元素时，数组长度扩容为10。
……
当第11次添加时，会触发扩容机制，其实就是调用 grow方法，扩容为原数组长度的1.5倍。
每次扩容时，都是创建一个新数组，将老数组的元素通过 arrays工具类复制到新数组中。elementdata 指向了新数组。
arraylist和 linkedlist 区别？
arraylist 底层数据结构 数组。
linkedlist 底层数据结构 链表。
功能上区别：
arraylist 查询快，增删慢。
原因：顺序存储，有索引，可以根据索引，直接定位到元素，所以查询快；由于是顺序存储，新增或者删除，都会对后续的元素有影响。
linkedlist 查询慢，增删快。
原因：不是顺序存储，每个结点相连，一个结点中可以存储下一个和上一个结点，这样的话，增删元素，只对相邻的结点有影响，其他结点不受影响；由于没有下标，所以，查询元素时，需要（从头结点或尾结点）遍历。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论