ArrayList源码解析(基于Java8)扩容删除

首先:执行List<Person> list1 = new ArrayList<>(); 在堆内存开辟了一块空间,既然是new出来的,那我们直接从构造函数入手

很简单一行代码,继续看一下

this.elementData

DEFAULTCAPACITY_EMPTY_ELEMENTDATA

分别是什么

Object[]数组,也就是说该数组可以放任何对象(所有对象都继承自父类Object)

static修饰的变量,常驻于方法区,我们不需要new,JVM会提前给我们初始化好,这个特性在实际开发过程中,经常拿来做缓存 fianl修饰的变量,JVM也会提前给我们初始化好

继续,执行list1.add(person1)看怎么处理add的

先看ensureCapacityInternal方法,有个参数size,看一下这个size从哪来的

size是int基本数据类型,成员变量初始化的为0

继续往下看

ensureCapacityInternal是在add里面调用的

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //如果底层数组就是默认的缓存数组,取两个参数的大的一个值继续往下调用,很明显这个大值为10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
 }

 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//记录修改次数

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

扩容

    private void grow(int minCapacity) {
        // 取到旧数组的长度
        int oldCapacity = elementData.length;
        //计算新数组的长度
        //>>是移位运算符,相当于int newCapacity = oldCapacity + (oldCapacity/2),但性能会好一些
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //保证长度在正常范围内
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 用计算出来的数组长度,往下传继续处理
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

这就是数组的扩容,一般是oldCapacity + (oldCapacity >> 1),相当于扩容1.5倍

跟进到Arrays这个工具类,很简单

再看copyOf()方法

System.arraycopy()方法用了一个native来修饰。 native的方法,是由其它语言来实现的,一般是(C或C++),所以这儿没有实现代码。 这是一个数组拷贝方法,大家还在写for循环拷贝数组吗?以后多用这个方法吧,简单又方便还能获得得更好的性能。

顺便看一看size()方法的源码

很简单,就是返回size值,而不是底层数组的长度,就是为何String里叫length()而List里叫size()的原因

有人说,诶,就一个元素,在堆内存中占了10个位置,好浪费啊,没办法,你要享受ArrayList的便利与丰富的API,就得牺牲一下空间作为代价

ArrayList还提供了其它构造方法,我们顺便来看一下

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
}

当我们在写代码过程中,如果我们大概知道元素的个数,比如一个班级大概有40-50人,我们优先考虑List<Person> list2 = new ArrayList<>(50)以指定个数的方式去构造,这样可以避免底层数组的多次拷贝,进而提高程序性能。

在长度为n数组中: 直接通过下标去访问元素,时间复杂度为O(1) 需要循环查找元素的时候,时间复杂度为O(n)

删除

删除指定位置的元素

public E remove(int index) {
        rangeCheck(index);

        //维护的一个变量,记录修改次数
        modCount++;
        //根据数组下标拿到底层数组里的元素
        E oldValue = elementData(index);

        //计算数组需要拷贝的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //拷贝删除位置(index)+1后面的numMoved个元素并从删除位置(index)开始复制
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //相当于:size = size - 1; elementData[size] == null
        //size减1,数组最后一个位置赋值为null
        elementData[--size] = null; // clear to let GC do its work

        //返回事先拿到的删除元素
        return oldValue;
}

这段代码里还调了一个方法rangeCheck()方法,我们看一下

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

好简单对不对,就是检查底层数组下标是否越界。我们再看另外一种删除方式

删除指定对象元素

public boolean remove(Object o) {
        //如果要删除的元素为null
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    //循环查找null,找到后执行fastRemove()方法
                    fastRemove(index);
                    //删除成功,返回true
                    return true;
                }
        } else {
            //要删除元素非空
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    //equals循环对比,对比成功则执行fastRemove()方法
                    fastRemove(index);
                    //删除成功,返回true
                    return true;
                }
        }
        //其他情况,返回 false
        return false;
}

再看一下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
}

和上面用下标删除方式一致,就是少了某些代码,就不细说了

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

661
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

3109
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1785
来自专栏闻道于事

Java常用工具类之时间转换

import java.text.DecimalFormat; import java.text.ParseException; import java...

3396
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2277
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3223
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

951
来自专栏武培轩的专栏

剑指Offer-求1+2+3+...+n

package Other; /** * 求1+2+3+...+n * 求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、...

3144
来自专栏书山有路勤为径

排序数组转换为二叉查找树

已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

863
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1092

扫码关注云+社区

领取腾讯云代金券