栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

ArrayList常用方法源码解析

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

ArrayList常用方法源码解析

文章目录
  • 一、概述
  • 二、源码解析


一、概述

ArrayList是实现了List接口的一个顺序存储的容器,允许存放null元素,底层通过数组实现,类内部没有实现同步,其余与vector大致相同,底层capacity表示数组实际的大小,当数组添加元素时,容量不足会触发自动扩容机制

二、源码解析
 
    private static final int DEFAULT_CAPACITY = 10;

    
    private static final Object[] EMPTY_ELEMENTDATA = {};

    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    
    transient Object[] elementData; // non-private to simplify nested class access

    
    private int size;

底层数据结构为数组结构,大部分情况下第一次扩容的默认容量为10,size用来记录底层数组中实际存放的元素的个数


构造函数

 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);
        }
    }

    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    
    public ArrayList(Collection c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

1.当构造函数参数为大于0整形参数时,会在底层创建一个整形参数长度大小的空数组并使elementData指向该引用,如果为0则指向已经在类中定义好的容量为0的空数组,如果小于0则会抛出异常
2.当构造函数为无参构造调用时,elementData指向已经在类中定义好的容量为10的数组引用
3.当构造函数参数为Collection接口下的容器时,会将该容器中的元素都存于数组之中,数组中元素个数不为0时,如果该容器为ArrayList容器,使elementData指向数组的引用,倘若为其他容器,进行数组复制的操作,如果容器元素为0,则使elementData指向一个容量为0的空数组

自动扩容

   public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    
    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);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。
数组进行扩容时会新建数组,并将旧数组中的元素通过Arrays.copyOf的方法拷贝到新数组中,数组每一次扩容大约为旧数组容量的1.5倍(数组扩容通过位运算,未必为1.5倍)

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

判断是否需要扩容,将元素放入数组末尾

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

如果index>size或index<0抛出异常,触发扩容机制, 创建一个新数组,索引之后元素全部后移,将元素复制到当前索引位置

set

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

索引检索并修改指定索引位置的值

get

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

        return elementData(index);
    }

索引检索并得到指定索引处的值

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

        modCount++;
        E oldValue = elementData(index);

        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

        return oldValue;
    }

通过数组复制将索引之后的元素向前移动一位,最后一位显式赋null使gc起作用

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/939641.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号