源码分析之ArrayList容器-蒲公英云

源码分析之ArrayList容器

- 1、ArrayList容器概述
- 2、ArrayList类主要属性
- 3、ArrayList类构造器
- 4、查找相关方法
- 5、插入相关方法
- 6、删除相关方法
- 7、其它方法
- 8、总结
- 9、往期佳文
- - 9.1、面试系列
  - 9.2、技术系列
  - 9.3、源码系列

1、ArrayList容器概述

   Java中的ArrayList类声明如下：
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

在这里插入图片描述
Java中的ArrayList容器是一个可动态调整大小的数组，每当我们往容器中插入元素都不必考虑容器是否装的下，其内部可以自动扩展大小。ArrayList容器的实现原理是封装了一个数组，每当插入元素就判断当前数组是否还有空位置存放，如果没有空位置，则新建一个更长的数组，并且把之前的元素复制到新数组中。

2、ArrayList类主要属性

   ArrayList类中的主要属性如下：
/** * 默认数组初始化的大小 */
private static final int DEFAULT_CAPACITY = 10;
/** * 空数组实例（当初始化容量=0时） */
private static final Object[] EMPTY_ELEMENTDATA = { };
/** * 调用默认构造器时，初始化的空数组实例 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
/** * ArrayList底层存放元素使用的数组 */
transient Object[] elementData;
/** * 数组中存放的元素个数（注意与数组长度的区分） */
private int size;

3、ArrayList类构造器

   ArrayList类中共有3个构造器：
/** * 指定数组的初始化长度 */
public ArrayList(int initialCapacity) { 
    // 主要是初始化elementData数组
    if (initialCapacity > 0) { 
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { 
        // EMPTY_ELEMENTDATA默认的空数组实现（前面介绍了这个静态属性）
        this.elementData = EMPTY_ELEMENTDATA;
    } else { 
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/** * 默认构造器 */
public ArrayList() { 
    // 表示数组未初始化（DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组空实现，前面介绍过这个静态属性）
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/** * 复制构造器 */
public ArrayList(Collection<? extends E> c) { 
    // 调用容器c中的toArray方法，获取数组形式的数据
    elementData = c.toArray();
    if ((size = elementData.length) != 0) { 
        // c.toArray可能返回的不是Object[].class，所以进行类型转换
        if (elementData.getClass() != Object[].class)
            // 调用Arrays.copyOf方法，copy出一个Object[].class形式的副本
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else { 
        // 如果容器c为空，则初始化elementData为空数组示例
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

4、查找相关方法

   1、get方法
/** * 通过index获取elementData中的元素（此方法未使用任何权限修饰符，所以默认是default，在当前包下可使用） */
@SuppressWarnings("unchecked")
E elementData(int index) { 
    return (E) elementData[index];
}
/** * 通过index获取elementData中的元素（public修饰，对外展示接口） */
public E get(int index) { 
    // 查找前先判断index是否超过了size（数组中元素的个数）
    rangeCheck(index);
    return elementData(index);
}
   2、contains方法
/** * 判断Object是否存在于容器中 */
public boolean contains(Object o) { 
    // 如果能查找到该元素的下标，则说明是存在的
    return indexOf(o) >= 0;
}
   3、indexOf、lastIndexOf方法
/** * 查找Object在容器数组中的第一个下标（未查找到返回-1） */
public int indexOf(Object o) { 
    // 如果o为null，则o需要==判断，否则调用equals方法判断是否相等
    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;
}
/** * 查找Object在容器数组中的最后一个下标（未查找到返回-1） */
public int lastIndexOf(Object o) { 
    // 与indexOf的区别就是从后往前查找，找的的就是最后一个下标
    if (o == null) { 
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else { 
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

5、插入相关方法

   1、add方法
/** * 往容器尾端增加一个元素 */
public boolean add(E e) { 
    // 增加元素前需要判断是否有空位置（没有就需要扩容
    ensureCapacityInternal(size + 1);
    // 直接放入elementData数组中的下一个空位置
    elementData[size++] = e;
    return true;
}
/** * 往容器指定下标插入一个元素 */
public void add(int index, E element) { 
    // 插入前需要判断插入的下标是否在[0, size]中，也就是不能插入到非连续的其它位置
    rangeCheckForAdd(index);
    // 当然还需要判断容器是否有空间供插入
    ensureCapacityInternal(size + 1);
    // arraycopy的五个参数分别是，数组src，起始下标，数组des，起始下标，复制的个数
    // 此时我们需要把elementData[index]这个位置空出来，也就是[index, size)区间的元素全部往后移动一个位置，index移动到index+1，index+1移动到index+2
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 现在就可以放入插入的元素了
    elementData[index] = element;
    // 容器中的元素数量自增1
    size++;
}
       2、set方法
/** * 此方法是修改指定下标的元素值 */
public E set(int index, E element) { 
    // 如果这个下标超出[0, size)都算错误！（注意与[0, elementData.length)的区别）
    // 因为这是修改方法，如果这个index对应没有值，则不能修改
    rangeCheck(index);
    // 修改前记录旧值，在替换心值
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

6、删除相关方法

   1、remove方法
/** * 移除容器中指定下标的元素 */
public E remove(int index) { 
    // 检查下标是否在[0, size)区间中
    rangeCheck(index);
    // 父类AbstractList中的一个变量，用于记录结构性调整（插入、删除、修改等）的次数
    modCount++;
    E oldValue = elementData(index);
    // [index + 1, size)区间的中的元素全部前一个位置
    int numMoved = size - index - 1;
    // arraycopy的五个参数分别是，数组src，起始下标，数组des，起始下标，复制的个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将size - 1的元素移除
    elementData[--size] = null;
    return oldValue;
}
/** * 移除容器中的o对象（第一个） */
public boolean remove(Object o) { 
    // 遍历一遍容器，把值为对象o的元素全部移除
    if (o == null) { 
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) { 
                // 此方法移除时不判断index的合法性，直接移除（因为传入的下标就是合法的）
                fastRemove(index);
                return true;
            }
    } else { 
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) { 
                fastRemove(index);
                return true;
            }
    }
    return false;
}
/* * 移除index下标对应的元素（不进行index判断，默认index是合法的） */
private void fastRemove(int index) { 
    // 与public E remove(int index)方法是一样的，只是没了index判断
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
}

7、其它方法

   1、trimToSize方法
/** * 此方法的作用是将elementData数组中的空余位置剔除（有点像瘦身） */
public void trimToSize() { 
    // 次方法也属于结构性调整
    modCount++;
    if (size < elementData.length) { 
        // 如果elementData数组存在元素，则调用Arrays.copyOf方法，复制到一个长度为size的数组中
        elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }
}
   2、grow扩容方法
/** * 增加elementData数组的长度 */
private void grow(int minCapacity) { 
    // 新长度为原长度的1.5倍
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新长度 比 最小的长度小，则修改为最小的长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新长度比MAX_ARRAY_SIZE还大，修改为默认的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用Arrays.copyOf方法，复制到一个长度为newCapacity的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

8、总结

   经过上面的分析不难看出，ArrayList容器的底层实现特别简单，就是封装了一个数组，每当插入元素就判断一下是否容的下，容不下就扩容。ArrayList容器支持尾端插入、根据下标插入（随机插入）；支持按下标查找（随机查找）、按值查找。

9、往期佳文

9.1、面试系列

1、吊打面试官之一面自我介绍
2、吊打面试官之一面项目介绍
3、吊打面试官之一面系统架构设计
4、吊打面试官之一面你负责哪一块
5、吊打面试官之一面试官提问

······持续更新中······

9.2、技术系列

1、吊打面试官之分布式会话
2、吊打面试官之分布式锁
3、吊打面试官之乐观锁
4、吊打面试官之幂等性问题
5、吊打面试关之分布式事务
6、吊打面试官之项目线上问题排查

······持续更新中······

9.3、源码系列

1、源码分析之SpringBoot启动流程原理
2、源码分析之SpringBoot自动装配原理

······持续更新中······

转载：Java容器之ArrayList源码分析

源码分析之ArrayList容器

1、ArrayList容器概述

2、ArrayList类主要属性

3、ArrayList类构造器

4、查找相关方法

5、插入相关方法

6、删除相关方法

7、其它方法

8、总结

9、往期佳文

9.1、面试系列

9.2、技术系列

9.3、源码系列

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

随便看看

教程文章

热评文章

1江湖小白之一起学Python （二）爬取数据的保存

2Java Shiro：简化身份验证和授权的安全框架

3Java中try()catch{}的使用方法

4Swagger注解-@ApiModel 和 @ApiModelProperty

5windows下强制杀死tomcat进程

6uni-app 条形码(一维码)/二维码生成实现

标签列表