| 手写ArrayList集合与源码分析 | 您所在的位置：网站首页 › arraylist源码分析 › 手写ArrayList集合与源码分析 |
手写ArrayList集合与源码分析
|
背景：首先集合大家是非常熟悉的，不管是个人日常编码还是公司项目，都是经常打交道的好朋友。但是我们要摸清楚她的底细，毕竟好朋友就是要知根知底~
那么来认识认识集合中的List集合，List集合中的ArrayList集合，四舍五入就是集合中的集合。 首先，简单陈述ArrayList集合特性，底层使用动态数组实现，随机查询效率非常快（元素下标），但插入和删除需要移动整个数组、效率低，ArrayList不是线程安全的、 Vector是线程安全的集合。ArrayList时间复杂度低,占用内存较多,顺序是连接的,空间复杂度高。 然后我们开始源码分析，以JDK1.8为演示，这里插一句，虽然JDK都是1.8版本的，但是如果后缀版本不一样，源码是会有大同小异的，我曾看过两个小版本不同的1.8集合源码中有一个是提取了公共方法，有一个是没有提取的，当然是不会有什么其他影响。 序：案例源码码云地址：地址：https://gitee.com/yiang-hz/gather PS：这里着重于实现思路与流程，建议对着源码看分析。 一、定义List集合接口这里定义常用的四个方法 增、删、查与大小。这里贴代码就不贴注释了，注释在源码中很详细。 public interface YiangList { int size(); E get(int index); boolean add(E e); E remove(int index); } 二、ArrayList属性变量解析我们来说说ArrayList实现类的一些变量以及它的作用。 1.（数据容器）elementData list是由数组实现的，那么需要有数组来存储数据值。故elementData为数据容器（数组容器）。默认为空。 2.（默认容量）DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组容器需要一个容量大小，那么该属性即为初始大小。数组容器默认为空，并且在构造函数中加载该变量。赋予容器初始默认大小。 3.（默认初始容量）DEFAULT_CAPACITY 由于ArrayList默认是在添加值的时候才会触发扩容机制，所以在扩容是需要有一个默认初始容量，那么该值就是在List添加值扩容时进行赋值给数组。 4.（默认最大值）MAX_ARRAY_SIZE 我们要知道不管什么容器，都有它最大的负载量，ArrayList也不例外。她的最大值为Integer的最大值 - 8。在Integer源码中有这么一句话 /** * A constant holding the maximum value an {@code int} can * have, 231-1. */ public static final int MAX_VALUE = 0x7fffffff;那么究竟是多少呢？答案为2的31次幂，也就是 2 147 483 648，是吗？不是，错了。 在这源码上有段注释，注释大致告诉你是 2^31 - 1 所以是 2 147 483 647。
5.（默认数据大小值）size 该值就比较明显了，是list.size()方法获取时返回的count数，count数的叠加是在add方法中进行累加的。也就是说每调用一次add()方法，就会进行一次 size++。为数组容器中数据量的总和 6.（线程安全控制）modcount 由于ArrayList是非线程安全的，所以在使用迭代器遍历的时候，用来检查列表中的元素是否发生结构性变化（列表元素数量发生改变）了，主要在多线程环境下需要使用，防止一个线程正在迭代遍历，另一个线程修改了这个列表的结构。 相关异常：ConcurrentModificationException。（并发修改异常） 通俗点说，就是迭代的时候，检查防止另外一个线程改变集合中元素。所以从这里就能体现为什么遍历很多人吹集合建议用迭代器的原因之一了。 实现代码块： public class YiangArrayList implements YiangList { /** * 默认初始容量 */ private static final int DEFAULT_CAPACITY = 10; /** 默认最大值 Integer最大值 -8 (HZ)*/ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 存放集合所有的数据，transient表示不能被序列化。 */ transient Object[] elementData; protected transient int modCount = 0; /** * 数组容量默认为空 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 数组大小默认为0 */ private int size; public YiangArrayList(){ this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** 返回集合当前大小 (HZ)*/ @Override public int size() { return size; } /** * 通过强制转换E，返回对应对象，使用@SuppressWarnings注解避免强转警告， * @param index 索引 * @return 元素 */ @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * 获取数组中元素 * @param index 索引 * @return 元素 */ @Override public E get(int index) { //调用返回方法 return elementData(index); } @Override public boolean add(E e) { //1.数组扩容 ensureCapacityInternal(size + 1); //2.数组变量赋值 elementData[size++] = e; return true; } /** * 删除方法 ** System.arrayCopy解析 * @see com.yiang.MyList#testArrayCopy() * * @param index 元素对象下标地址 * @return 被删除的对象 */ @Override public E remove(int index) { //监测下标是否越界 rangeCheck(index); modCount++; //此处获取被删除的数据返回出去 E oldValue = elementData(index); //计算移动位置 集合大小 - 移动的下标位置 - 1 int numMoved = size - index - 1; //如果移动的位置>0，也就是代表移除的不是最后一位的情况下，进行移动覆盖算法。 if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } //置空元素最后一位的同时将size减去1，这里真的很棒。 // 至于清除这里源码英文注释翻译是 “清除，让GC做它的工作” elementData[--size] = null; // clear to let GC do its work return oldValue; } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size; } /** * 判断数组是否为初始情况 * 如果数组扩容值小于默认值10则返回默认值，如果大于默认值，那则返回该值 * @param elementData 数组 * @param minCapacity 最小容量 = 数组大小 N + 扩容的值 1 * @return 10 > N ? 10 : N 初始返回为10 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果扩容时，数组为空那么 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //max为三元运算，如果初始容量大于当前容量，那么赋值为初始容量，如果小于则以当前容量计算 return Math.max(DEFAULT_CAPACITY, minCapacity); } //返回容量 return minCapacity; } /** * 对计算是否扩容方法进行调用，同时判断是否为初始情况 * {@code minCapacity} 初始值为1 * @param minCapacity 最小容量 = 数组大小 N + 扩容的值 1 */ private void ensureCapacityInternal(int minCapacity) { //调用计算是否扩容方法 ensureExplicitCapacity( //抽取出来的公共方法，源码有所变化。 calculateCapacity(elementData, minCapacity) ); } /** * 判断数组是否需要进行扩容 * @param minCapacity 容量值 */ private void ensureExplicitCapacity(int minCapacity) { //控制线程安全之类的。 modCount++; // overflow-conscious code //如果容量值大于数组长度，那么进行grow扩容方法。 此处初始默认情况为：10 - 0 > 0 if (minCapacity - elementData.length > 0) { grow(minCapacity); } } /** * 数组扩容方法 * @param minCapacity 容量值 初始为10 */ private void grow(int minCapacity) { // 当前数组长度，原来的容量 默认为0 int oldCapacity = elementData.length; //新的长度 = 旧的长度 + 二进制算法（旧长度除以2） 也就是原有长度 + 原有长度的二分之一 int newCapacity = oldCapacity + (oldCapacity >> 1); //初始情况为 0 + 0/2 - 10 所以 新长度会默认等于传递的长度10 if (newCapacity - minCapacity < 0) { //作用：第一次对数组初始化容量操作 newCapacity = minCapacity; } //判断最大值 MAX_ARRAY_SIZE = Integer最大值-8 //目的是为了做个限制，实际上是用不到的 if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } // minCapacity is usually close to size, so this is a win: //开始对我们的数组进行扩容 //复制当前数组，并将复制后的数组的长度设置为 newCapacity 第一次扩容 10 -> 15 elementData = Arrays.copyOf(elementData, newCapacity); } /** * 如果超过了默认设置的集合最大值，那么就使用Integer最大值 * @param minCapacity 最小值 * @return 集合最大值或者Integer最大值 */ private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) { // overflow throw new OutOfMemoryError(); } return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } } 三、ArrayList重点方法解析上面说完了变量值后，相信大家都饥渴难耐的想要了解类的方法实现原理了。马上来揭秘她！
3.1、获取集合大小 list.size() 返回当前集合的大小，也就是将属性值size返回。由于size在add方法中会进行size++操作，所以size与数组中实际元素的大小是一致的。注意size是数组容器内实际元素数量，而不是数组容器的大小。 3.2、获取集合元素 list.get(int index) 获取集合元素，实际上就是通过下标，在数组容器中找到对应的数据返回即可。 3.3、集合添加元素 list.add(Object o) 添加元素中涉及到的知识点就比较多了。先扩容、再赋值。 1.扩容：PS：扩容由于涉及内容太多，故将其作为第四大点放在下文。 2.赋值：代码： elementData[size++] = e;不得不说这里很巧妙。打个比方现在的容器大小为5，已有数据量size为3，那么在[]内计算size++就是 3+1 = 4。那么得到新添加的元素下标为4，同时size也进行了累加。在使用数组赋值，将该下标赋值为新添加的元素e。一句代码实现了，size累加。下标定位。数据赋值。
3.4、为什么ArrayList删除元素要慢？ list.remove(int index) 首先在删除下标时，会通过监测方法rangeCheck(int index)，监测下标是否越界，原理就是判断index是否大于等于size。 由于下标是 0开始，size是1开始，故判断是判断大于等于，而不仅仅是大于。 其次是删除时调用的方法，数组复制算法。（慢的主要原因） src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度。 System.arraycopy(elementData, index + 1, elementData, index, numMoved);这里画图说说它实现的原理 。复制时是将 1234 如果是删除 1 那么就是将 234往前复制，然后就变成了 2344。 其次源码里最后会将数组最后一位数赋值为NULL完成删除。 如果是删除2，复制数组结果就是 1344，然后把最后一位赋值为NULL。得出134。 如果是删除3，复制数组结果就是1244，然后把最后一位赋值为NULL。得出124。
综合以上，我们就能知道为什么ArrayList在删除时会要慢，因为每次删除都需要重新复制一遍数组容器的数据进行覆盖。 四、ArrayList扩容机制 4.1、扩容判断机制方法 ensureCapacityInternal扩容机制调用方法：ensureCapacityInternal。 /** * 对计算是否扩容方法进行调用，同时判断是否为初始情况 * {@code minCapacity} 初始值为1 * @param minCapacity 最小容量 = 数组大小 N + 扩容的值 1 */ private void ensureCapacityInternal(int minCapacity) { //调用计算是否扩容方法 ensureExplicitCapacity( //抽取出来的公共方法，源码有所变化。 calculateCapacity(elementData, minCapacity) ); }首先它会调用ensureExplicitCapacity方法来进行判断是否需要进行扩容。如果容量值大于数组长度，那么进行扩容。 参数组成为：当前数组大小 N + 扩容的值 X 这里填的1。 /** * 判断数组是否需要进行扩容 * @param minCapacity 容量值 */ private void ensureExplicitCapacity(int minCapacity) { //控制线程安全之类的。 modCount++; // overflow-conscious code //如果容量值大于数组长度，那么进行grow扩容方法。 此处初始默认情况为：10 - 0 > 0 if (minCapacity - elementData.length > 0) { grow(minCapacity); } }判断数组是否需要扩容方法的参数容量值为经过 calculateCapacity(elementData, minCapacity)方法判断数据后得出的值。 那么calculateCapacity方法实际上就是通过判断数组是否为空（是否第一次扩容），如果为空则判断扩容的值和默认容量10，扩容容量当前为1，那么返回的值就是10。如果不为空，那么就证明不是第一次扩容，直接返回数组当前容量。 /** * 判断数组是否为初始情况 * 如果数组扩容值小于默认值10则返回默认值，如果大于默认值，那则返回该值 * @param elementData 数组 * @param minCapacity 最小容量 = 数组大小 N + 扩容的值 1 * @return 10 > N ? 10 : N 初始返回为10 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果扩容时，数组为空那么 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //max为三元运算，如果初始容量大于当前容量，那么赋值为初始容量，如果小于则以当前容量计算 return Math.max(DEFAULT_CAPACITY, minCapacity); } //返回容量 return minCapacity; }故这里传递给判断扩容方法（ensureExplicitCapacity）的值。若是第一次扩容则为默认值10，若是第二次扩容则为数组当前容量也就是第一次扩容后的10。如果目前是无需扩容，那么直接返回。结束方法。如果是需要扩容，那么进入grow方法，开始扩容机制。 4.2、扩容方法grow这里传入的值有两种情况，第一种是第一次扩容，默认为初始值DEFAULT_CAPACITY也就是10。 第二次扩容则是数组当前的容量大小。也就是第一次扩容后的10 首先它会获取原来的长度oldCapacity，然后新的长度等于 原来长度的1.5倍，源码采用二进制计算，总所周知二进制运算是速度更快的。所以第二次扩容后数组大小为15。 然后判断数组大小是否超过设定最大值，如果超过了则默认为最大值。 最后通过Arrays提供的copyOf方法指定需要复制的数组与长度，再将原来的数组覆盖完成扩容。 /** * 数组扩容方法 * @param minCapacity 容量值 初始为10 */ private void grow(int minCapacity) { // 当前数组长度，原来的容量 默认为0 int oldCapacity = elementData.length; //新的长度 = 旧的长度 + 二进制算法（旧长度除以2） 也就是原有长度 + 原有长度的二分之一 int newCapacity = oldCapacity + (oldCapacity >> 1); //初始情况为 0 + 0/2 - 10 所以 新长度会默认等于传递的长度10 if (newCapacity - minCapacity < 0) { //作用：第一次对数组初始化容量操作 newCapacity = minCapacity; } //判断最大值 MAX_ARRAY_SIZE = Integer最大值-8 //目的是为了做个限制，实际上是用不到的 if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } // minCapacity is usually close to size, so this is a win: //开始对我们的数组进行扩容 //复制当前数组，并将复制后的数组的长度设置为 newCapacity 第一次扩容 10 -> 15 elementData = Arrays.copyOf(elementData, newCapacity); }以上即是扩容机制。 扩容机制总结：默认初始化容量为0，首次添加默认扩容为10，可设置值计算公式为三元 N > 10 ? N : 10。最大容量为 [2的32次幂-1] 2^32-1 扩容会进行细节判断，区分old与new两个大小。计算公式为 old + old/2。也就是常说的1.5倍 通过Arrays.copyOf来进行最后的数组扩张。 本文总结：回顾文章开篇说的List特性： 底层使用动态数组实现，随机查询效率非常快（元素下标），但插入和删除需要移动整个数组、效率低，ArrayList不是线程安全的、 Vector是线程安全的集合。ArrayList时间复杂度低,占用内存较多,顺序是连接的,空间复杂度高。 论证： 1.扩容机制？底层是包含数组，默认扩容大小为10，扩容倍数为 1.5倍，首次扩容大小与扩容倍数机制均可自定义。 2.为什么慢？由于增加需要扩容，删除需要复制数组，打乱数组原有顺序，所以导致整个数组出现复制操作，空间复杂度高，由此效率变低，故效率低。 3.为什么Vector就安全了？源码加了个锁 4.时间复杂度低是什么？为什么查询快？查询快是因为底层默认使用数组，查询元素只需要通过下标找到对应元素即可，但维持快速度查询的是需要保证顺序绝对性，故占用内存，所以空间复杂度高。 备注：拉取代码通过运行test方法即可调试扩容信息。 后记：目前也是在复习集合知识，通过博客来将知识梳理供大家学习，也提升自己的印象。 如有不足之处，欢迎指正，如有共同维护该集合项目或分享更多学习知识想法，可以加我好友联系。
|
【本文地址】