java arraylist6_【数据结构】6.java源码ArrayList

逃离我推掉我的手 2022-11-08 14:11 143阅读 0赞

关于ArrayList的源码关注点

1.从底层数据结构，扩容策略

2.ArrayList的增删改查

3.特殊处理重点关注

4.遍历的速度，随机访问和iterator访问效率对比

1.从底层数据结构，扩容策略

对于第一个问题，底层即时一个object的数组，用来存放动态数据：

transient Object\[\] elementData;

默认初始容量大小是10个，注意这里有个坑不是一开始就是10个，而是当进行add操作的时候，会默认修改为10个：private static final int DEFAULT\_CAPACITY = 10;

源码中进行初始化的时候：

![95dfeed34352cb6c90c3d6c39b89085e.png][]

而我们的DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA这个数据是,也就是说只进行new操作的时候，我们是给了一个空的数组大小是0长度是0，大小是0

Private static final Object\[\] DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA = \{\};

这里源码中有一段代码：

![c757a94a9de2d3d61ad9df61aec55d23.png][]

collection.toArray()應該等同於collection.toArray(new Object\[0\])，返回的是Object\[\]類型。然而，Arrays.asList卻不是這樣，如果它的類型是一個Object\[\]子類(比如String\[\])，那麼toArray()就會返回這個子類而不是Object\[\]，因為它調用的是clone())

EnsureCapacityInternal 扩容策略最终调用======》grow方法进行大小增长

只有在容量不够了的时候才会采取扩容措施

private void grow(intminCapacity) \{//overflow-conscious code

int oldCapacity =elementData.length;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);

1.而且扩容也很简单粗暴，直接扩大1.5倍，采用右移的方式进行扩容，然后加上原始容量

2.如果括了1.5倍，还是比需要获取的大小要小，那么就直接把大小扩为想要获取的大小

3.如果扩容之后的大小，超出限制(Integer.MAX\_VALUE - 8;)，那么就扩到最大Integer.MAX\_VALUE，如果期望的大小还没超过这个Integer.MAX\_VALUE - 8;那么就扩围Integer.MAX\_VALUE - 8;

最后吧新的数据拷贝过来取代旧数据

![8eda7db0086122e7ed3f6f7696f46251.png][]

2.ArrayList的增删改查

2.1 add操作

进行add操作的时候支持2种添加方式

![ac18d54ea0c79eea7f95d824bbb5f0e5.png][]

![0922e9ccd3cdbffd6b9c85526183f7a3.png][]

添加的时候size+1，作为新的size，然后调用扩容策略

最后吧新数据放到最后一个位置，返回true

其次添加到指定位置

做了2次拷贝操作

1.先创建新的容纳大小的空间

2.然后把需要添加进去的数据的index位置，往后推移拷贝一遍，然后再指定位置写入

System.arraycopy(elementData, index, elementData, index + 1,

size - index);

![3b7b314461107272c061826ac974c2d1.png][]

2.2 删除remove(obj),remove(int),fastRemove

Remove(obj)删除操作底层调用的还是fastremove

根据要删除的位置计算需要移动的元素个数

![8dbd78118c5c4a725184443589fad162.png][]

比如2个元素，现在要删除第一个元素，那么index=0，那么就是2-0-1 = 1；需要移动一个

Index就是对应的元素的下标,numMoved就是需要移动的元素的个数

![da875d12145a589c577d957978a1ab73.png][]

直接删除索引

Remove(int)

删除这个索引之前，会先判断是否越界

![191dfb04323199d6dd1fc9e903db29fd.png][]

和之前的删除大同小异

修改，查询就不说了，就是set和get操作，分别是elementData\[index\] = ele,和return elemenetData\[index\]

3.特殊处理重点关注，iterator

1.这里注意ArrayList有一个modCount属性，这个属性用来标识这个list被修改了多少次

2.注意使用迭代器的时候，对元素的增加或者删除，请用迭代器的删除，而不能用list的remove，而且遍历的时候只能删除，不能做新增

![d2aed88a1fff2d1113ab02bf17d2ecfc.png][]

这个方法会校验

![434bae8e7a3abb727860e2aa774a82f8.png][]

ExpectedModCount 而这个参数在创建iterator的时候，就进行了赋值 int expectedModCount = modCount;

4.遍历的速度，随机访问和iterator访问效率对比

并没有差别，其实iterator也就是对数组访问，所以不存在效率问题，只是我们一般的情况可以进行随机访问，而iterator只能进行遍历

5.是否支持多线程

这个就否了，不用管

借鉴：

[95dfeed34352cb6c90c3d6c39b89085e.png]: /images/20221023/bbe28e81b3184593b99aa11c9a1048c8.png
[c757a94a9de2d3d61ad9df61aec55d23.png]: /images/20221023/a731dc6f46124671ab810ae2c42f7c8c.png
[8eda7db0086122e7ed3f6f7696f46251.png]: /images/20221023/d44b6fb4a14c412997d28a001f2347cc.png
[ac18d54ea0c79eea7f95d824bbb5f0e5.png]: /images/20221023/ee9e598c7649418d8ae56252b9465e18.png
[0922e9ccd3cdbffd6b9c85526183f7a3.png]: /images/20221023/ae9a0f10380d4f80b87065caa81e51ac.png
[3b7b314461107272c061826ac974c2d1.png]: /images/20221023/3d897ede834c4aba90f48759737e6e19.png
[8dbd78118c5c4a725184443589fad162.png]: /images/20221023/0679a70f10fb4f1485b215467774e0cb.png
[da875d12145a589c577d957978a1ab73.png]: /images/20221023/c4871cdf5f80413680c46316ea2aa262.png
[191dfb04323199d6dd1fc9e903db29fd.png]: /images/20221023/77c5af0ec6fc4026ada0557ccebb0fdc.png
[d2aed88a1fff2d1113ab02bf17d2ecfc.png]: /images/20221023/969bce08c4b141ed94717d4729a7f95e.png
[434bae8e7a3abb727860e2aa774a82f8.png]: /images/20221023/018fbfb7ddb347d5a4a33be17ef7bed9.png