深入挖掘 ArrayList工作原理及其实现

深入挖掘 ArrayList工作原理及其实现,第1张

深入挖掘 ArrayList工作原理及其实现

文章目录

ArrayList工作原理及其实现

1.ArrayList集合使用2.通过JDK源码来研究ArrayList的实现

2.1 继承关系2.2 属性和默认值2.3 构造函数2.4 常见方法原码解析

2.4.1 add:添加元素2.4.2 remove:删除元素2.4.3 get:获取元素

ArrayList工作原理及其实现

特点、需要通过源码底层实现查看实现逻辑。

1.ArrayList集合使用

特点:

1、ArrayList可以存放重复数据
2、ArrayList中元素存放和插入顺序一致。
3、ArrayList中存放的数据可以为null
4、ArrayList集合底层采用的是数组来存储数据

构造函数:

//无参构造
ArrayList  list = new ArrayList <>();
//通过指定集合容量大小来实例化
ArrayList  list1 = new ArrayList <>(100);
//通过Collection集合实例来实例化一个新集合
ArrayList  list2 = new ArrayList <>(list);
2.通过JDK源码来研究ArrayList的实现

1、关注继承关系
2、属性和默认值
3、构造函数
4、扩容机制、扩容时机
5、底层数据结构(数组、链表、队列、栈、哈希表…)
6、常见方法实现原理(add、get、remove)

2.1 继承关系
public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

类结构图

①ArrayList继承自AbstractList,AbstractList是抽象类,实现了List接口,它是一个数组队列,提供了相关的添加、修改、删除、遍历等基本功能实现,方法子类对方法复用,如果子类有特有功能可以重写父类的方法。
②ArrayList实现了List接口,List接口继承自Collection接口,在Collection接口提供的方法基础上,有一些新的方法提供,比如get、set、add等特有方法。
③ArrayList实现了RandomAccess接口,即提供了随机访问功能。
④ArrayList实现了Cloneable接口,即包含了函数clone(),能被克隆。
⑤ArrayList实现了Serializable接口,意味着ArrayList支持序列化,能通过序列化去传输(IO)。

2.2 属性和默认值
//默认的初始容量10
private static final int DEFAULT_CAPACITY = 10;
//空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//存储数据:使用的是数组,数组存储的数据类型是Object
private transient Object[] elementData;
//用来记录存放数据的个数
private int size;

ArrayList底层存储元素是使用数组,类型为Object类型。数组中:elementData.length:表示的是当前数组容量,最大存储的数据个数; size:实际存放的数据个数,即数组中有效数据个数。

2.3 构造函数
        //有参构造函数:通过指定初始容量initialCapacity来实例化ArrayList
	public ArrayList(int initialCapacity) {
        super();
        //参数合法性校验
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        //实例化一个大小为initialCapacity数组并将数组赋值给elementData
        this.elementData = new Object[initialCapacity];
    }

    //无参构造函数  elementData赋值为空数组
    public ArrayList() {
       // ArrayList(DEFAULT_CAPACITY);
        super();
        this.elementData = EMPTY_ELEMENTDATA;
        //将默认值的赋值在add中完成
    }

    //通过集合来实例化ArrayList
    public ArrayList(Collection c) {
        //将集合转化为数组,直接赋值给elementData
        elementData = c.toArray();
        //将集合中已有元素的大小赋值给size(有效数据个数)
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //如果elementData类型不是Object类型,将其强转为Object类型
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
2.4 常见方法原码解析 2.4.1 add:添加元素
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

1、 ensureCapacityInternal(size + 1); 检查数组容量是否够

 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

2 、 如果当前数组是空数组,那么就会初始化数组容量大小为 10 (添加第一个元素,集合是通过无参构造实例的时候)

3、 如果当前数组不是空数组,那么执行ensureExplicitCapacity(minCapacity);

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

1)modcount++: modCount属性是版本控制器,和业务无关,仅仅是做版本控制,在集合进行变更时(修改、删除、添加)会自增1

    如果size+1 大于 数组的长度 那么进行 扩容 *** 作 grow(minCapacity);
private void grow(int minCapacity) {
        // 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.5 倍,得到新的数组长度newCapacity

oldCapcity >> 1 效率 比 oldCapcity / 2 高

②如果新的数组长度小于size+1的长度 大于 新的数组长度,更新新的数组长度为size + 1,如果新的数组长度比最大值MAX_ARRAY_SIZE还要大,进入hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,如果minCapacity大于最大容量,则新容量则为Integer.MAX_VALUE,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8

③调用Arrays.copyOf()函数将原有的集合数据拷贝到新容量为newCapacity的数组中

2.4.2 remove:删除元素
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

1、 如果删除对象是null ,遍历数组,找到null的元素,调用**fastRemove()**方法

2、 如果删除对象不是null,遍历数组,找到对应的元素,调用**fastRemove()**方法

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

3、fastRemove方法

删除对应的元素后,需要将后面的元素一一往前移动一位。先统计需要移动的元素个数(删除元素后的元素个数),调用System.arraycopy()方法进行元素拷贝移动,最后将数组中最后一个元素置为null,有效元素个数-1。

2.4.3 get:获取元素
    public E get(int index) {
        //检查查询位置的合法性 index = size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

	 E elementData(int index) {
        return (E) elementData[index];
    }

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710198.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存