Java ArrayList 实现实例讲解
这里有新鲜出炉的 Java 并发编程示例, 程序狗速度看过来!
Java 程序设计语言
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言, 是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台 (即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se)) 的总称
ArrayList 是基于数组实现的, 是一个动态数组, 其容量能自动增长, 类似于 C 语言中的动态申请内存, 动态增长内存这篇文章主要介绍了 java ArrayList 实现的相关资料, 需要的朋友可以参考下
ArrayList 概述:
ArrayList 是基于数组实现的, 是一个动态数组, 其容量能自动增长, 类似于 C 语言中的动态申请内存, 动态增长内存
ArrayList 不是线程安全的, 只能用在单线程环境下, 多线程环境下可以考虑用 Collections.synchronizedList(List l)函数返回一个线程安全的 ArrayList 类, 也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类
ArrayList 实现了 Serializable 接口, 因此它支持序列化, 能够通过序列化传输, 实现了 RandomAccess 接口, 支持快速随机访问, 实际上就是通过下标序号进行快速访问, 实现了 Cloneable 接口, 能被克隆
每个 ArrayList 实例都有一个容量, 该容量是指用来存储列表元素的数组的大小它总是至少等于列表的大小随着向 ArrayList 中不断添加元素, 其容量也自动增长自动增长会带来数据向新数组的重新拷贝, 因此, 如果可预知数据量的多少, 可在构造 ArrayList 时指定其容量在添加大量元素前, 应用程序也可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量, 这可以减少递增式再分配的数量
注意, 此实现不是同步的如果多个线程同时访问一个 ArrayList 实例, 而其中至少一个线程从结构上修改了列表, 那么它必须保持外部同步
下面对 java arraylist 做一个记录和总结吧
- public class arraylist < E > {
- /**
- * 存放集合的元素
- *
- */
- private transient Object[] elementData;
- /** 元素的大小 */
- private int size;
定义了一个泛型类, 一个 object 的数组和一个私有变量来记录该集合的元素数量, 原文多了一个私有变量, 我也不知道干嘛用的, 作者也没解释也没提及到, 我没使用也没事
- /**
- * 根据指定大小初始化
- * @param initialCapacity
- */
- public arraylist(int initialCapacity) {
- super();
- if (initialCapacity <= 0) {
- // 抛异常
- throw new IllegalArgumentException("初始化参数不能小于 0");
- } else {
- // 初始化数组
- this.elementData = new Object[initialCapacity];
- }
- }
- /**
- * 默认初始化
- */
- public arraylist() {
- this(10);
- }
- /**
- * 根据一个集合类初始化
- * @param c 一个必须继承了 Collection 接口的类
- */
- public arraylist(Collection < ?extends E > c) {
- // 初始化
- elementData = c.toArray();
- size = elementData.length;
- // 如果不是任意类型的数组就转换 Objec 类型
- if (elementData.getClass() != Object[].class) {
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- }
- }
3 个初始化方法, 根据默认大小进行数组的初始化, 给定大小初始化和传递一个继承了 Collection 集合接口的类进行转换赋值初始化
- /**
- * 扩容集合
- * @param minCapacity
- */
- public void ensureCapacity(int minCapacity) {
- /** 当前数组的大小 */
- int oldCapacity = elementData.length;
- if (minCapacity > oldCapacity) {
- /**
- * oldData 虽然没有被使用, 但是这是关于内存管理的原因和 Arrays.copyOf()方法不是线程安全
- * oldData 在 if 的生命周期内引用 elementData 这个变量, 所以不会被 GC 回收掉
- * 当 Arrays.copyOf()方法在把 elementData 复制到 newCapacity 时, 就可以防止新的内存或是其他线程分配内存是 elementData 内存被侵占修改
- * 当结束是离开 if,oldData 周期就结束被回收
- */
- Object oldData[] = elementData;
- int newCapacity = (oldCapacity * 3) / 2 + 1; // 增加 50% 1
- if (newCapacity < minCapacity) newCapacity = minCapacity;
- // 使用 Arrays.copyOf 把集合的元素复制并生成一个新的数组
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- }
这是一个核心的方法, 集合的扩容, 其实是对数组的扩容, minCapacity 集合的大小, 进行对比判断是否应该进行扩容, 使用了 Arrays.copyOf()方法进行扩容,
原文有进行详细的解释, 这个方法把第一个参数的内容复制到一个新的数组中, 数组的大小是第二个参数, 并返回一个新的数组, 关于 oldData 的变量上文有详细的注释
- /**
- * 检查索引是否出界
- * @param index
- */
- private void RangeCheck(int index) {
- if (index > size || index < 0) {
- throw new IndexOutOfBoundsException("下标超出, Index:" + index + ", Size:" + size);
- }
- }
一个下标的检索是否出 1 /**
* 添加元素
* 将指定的元素添加到集合的末尾
* @param e 添加的元素
* @return
*/
- public boolean add(E e) {
- ensureCapacity(size + 1);
- elementData[size] = e;
- size++;
- return true;
- }
添加元素, 先进行扩容, 在赋值, 然后元素加一, 注意 size+1 字段 size 并没有加一, 这里进行的是算术的运算, 所以在后面才需要进行自增
- /**
- * 添加元素
- * 将元素添加到指定的位置
- * @param index 指定的索引下标
- * @param element 元素
- * @return
- */
- public boolean add(int index, E element) {
- RangeCheck(index);
- ensureCapacity(size + 1);
- // 将 elementData 中从 Index 位置开始长度为 size-index 的元素,
- // 拷贝到从下标为 index+1 位置开始的新的 elementData 数组中
- // 即将当前位于该位置的元素以及所有后续元素右移一个位置
- System.arraycopy(elementData, index, elementData, index + 1, size - index);
- elementData[index] = element;
- size++; // 元素加一
- return true;
- }
这里不同的是 System.arraycopy(elementData, index, elementData, index+1, size-index);
这是一个 c 的内部方法, 详细的原文有解释, 这里就不说了, 这个也是整个 ArrayList 的核心所在, 也 Arrays.copyOf()的内部实现原理
- /**
- * 添加全部元素
- * 按照指定 collection 的迭代器所返回的元素顺序, 将该 collection 中的所有元素添加到此列表的尾部
- * @param c
- * @return
- */
- public boolean addAll(Collection < ?extends E > c) {
- Object[] newElement = c.toArray();
- int elementLength = newElement.length;
- ensureCapacity(size + elementLength);
- // 从 newElement 0 的下标开始, elementLength 个元素, elementData size 的下标
- System.arraycopy(newElement, 0, elementData, size, elementLength);
- size += elementLength;
- return elementLength != 0;
- }
基本上其他方法都只是根据不同的情况进行不同的处理, 比如通过接口把数据对象传递进来然后获取长度进行扩容, 在把数据使用 System,arraycopy 复制到新的数组中
- /**
- * 指定位置, 添加全部元素
- * @param index 插入位置的下标
- * @param c 插入的元素集合
- * @return
- */
- public boolean addAll(int index, Collection < ?extends E > c) {
- if (index > size || index < 0) {
- throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
- }
- Object[] newElement = c.toArray();
- int elementLength = newElement.length;
- ensureCapacity(size + elementLength);
- int numMoved = size - index;
- // 判断插入的位置是否在数组中间
- if (numMoved > 0) {
- // 把 index 插入位置的后面的所有元素往后移
- //elementData index 下标开始的 numMoved 个元素插入到 elementData 的 index+elementLength 位置
- System.arraycopy(elementData, index, elementData, index + elementLength, numMoved);
- }
- // 把 newElement 里从 0 开始的 elementLength 个元素添加到 elementData index 开始的位置
- System.arraycopy(newElement, 0, elementData, index, elementLength);
- size += elementLength;
- return elementLength != 0;
- }
- /**
- * 指定下标赋值
- * @param index
- * @param element
- * @return
- */
- public E set(int index, E element) {
- RangeCheck(index);
- E oldElement = (E) elementData[index];
- elementData[index] = element;
- return oldElement;
- }
- /**
- * 根据下标取值
- * @param index
- * @return
- */
- public E get(int index) {
- RangeCheck(index);
- return (E) elementData[index];
- }
- /**
- * 根据下标移除元素
- * @param index
- */
- public E remove(int index) {
- RangeCheck(index);
- E oldElement = (E) elementData[index];
- /** 移除的下标后面的元素数量 */
- int numMoved = size - index - 1;
- // 如果在数组范围内就进行移动
- if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved);
- // 移除
- elementData[--size] = null;
- return oldElement;
- }
- /**
- * 根据元素移除
- * @param obj
- * @return
- */
- public boolean remove(Object obj) {
- //Arraylist 允许存放 null, 所以也要进行判断处理
- if (obj == null) {
- for (int index = 0; index < size; index++) {
- if (elementData[index] == null) {
- remove(index);
- return true;
- }
- }
- } else {
- for (int index = 0; index < size; index++) {
- if (obj.equals(elementData[index])) {
- remove(index);
- return true;
- }
- }
- }
- return false;
- }
- /**
- * 根据下标移除指定范围内的元素
- * @param fromIndex 开始
- * @param toIndex 结束
- */
- protected void removeRange(int fromIndex, int toIndex) {
- RangeCheck(fromIndex);
- RangeCheck(toIndex);
- // 要移动的元素数
- int numMoved = size - toIndex;
- // 把 toIndex 后面的元素移动到 fromIndex
- System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
- // 要移除的元素数量
- int newSize = size - (toIndex - fromIndex);
- while (size != newSize) {
- elementData[--size] = null;
- }
- }
- /**
- * 把数组容量调整到实际的容量
- */
- public void trimToSize() {
- int leng = elementData.length;
- if (size < leng) {
- Object[] old = elementData;
- elementData = Arrays.copyOf(elementData, size);
- }
- }
- /**
- * 把集合元素转换成数组
- * @return
- */
- public Object[] toArray() {
- return Arrays.copyOf(elementData, size);
- }
- public < T > T[] toArray(T[] a) {
- if (a.length < size) {
- return (T[]) Arrays.copyOf(elementData, size, a.getClass());
- }
- // 把集合元素复制到 a 数组中
- System.arraycopy(elementData, 0, a, 0, size);
- if (a.length > size) {
- for (int index = size; index < a.length; index++) {
- a[index] = null;
- }
- }
- return a;
- }
基本上都是对数组进行操作和使用 c 的方法进行赋值移动等, 详细的可以查看原文, 原文中除了那个私有变量外也没多少问题, 代码可以完美运行, 这李要注意的和难点就会是 System,arraycopy 和 Arrayist.copy()这 2 个方法
和在扩容方法里 oldData 这个变量的使用, 这个变量真的很好, 一开始我也不知道为什么要这么使用, 在原文的末尾会进行解释
来源: http://www.phperz.com/article/18/0210/359526.html