精华内容
下载资源
问答
  • ArrayList源码

    2020-12-15 11:32:12
    ArrayList源码 一:ArrayList底层结构 ArrayList底层结构是基于数组实现的。 二:ArrayList源码 2.1:默认构造方法是一个空数组 private static final int DEFAULT_CAPACITY = 10; private static final Object[] ...

    ArrayList源码

    一:ArrayList底层结构

    ArrayList底层结构是基于数组实现的。

    二:ArrayList源码

    2.1:默认构造方法是一个空数组

     private static final int DEFAULT_CAPACITY = 10;
     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
       public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    2.2:add()方法,往数组添加数据的时候会对size+1,判断是否需要扩容,默认是空数组,所以第一次添加元素的时候肯定会进行扩容为大小是10的数组,然后进行元素的拷贝。

      public boolean add(E e) {
       //确保数组容量足够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //空数组的话,设置容量大小为10,见构造方法代码块
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
      private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //判断是否需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //通过位运算,右移一位进行1.5倍扩容
        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);
    }
    

    2.3:remove()
    判断是否越界,越界则抛异常,然后进行数据的拷贝。

    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;
    }
    
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    

    2.4:get()

      public E get(int index) {
          //检查是否越界
        rangeCheck(index);
          //fail-fast 防止用户多线程操作
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }
    private void checkForComodification() {
        //相当于一个版本号,判断版本号是否是预期的值
        if (ArrayList.this.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }
    E elementData(int index) {
        return (E) elementData[index];
    }
    

    三:总结

    优点:ArrayList进行读操作,通过下标进行随机访问,时间复杂度logO(1),性能高。
    缺点:频繁进行插入操作,需要考虑扩容和拷贝操作,性能较差。

    展开全文
  • ArrayList 源码

    千次阅读 2020-06-27 20:24:15
    ArrayList 源码 ArrayList概览 基本概念 ArrayList 的结构较为简单,就是一个数组。结构如下图所示。ArrayList中有一些重要概念、属性: index:当前下标 elementData:数组,该数组的大小,经常与 ArrayList 的...

    ArrayList 源码

    ArrayList概览

    基本概念

    ArrayList 的结构较为简单,就是一个数组。结构如下图所示。
    image.png
    ArrayList中有一些重要概念、属性:

    1. index:当前下标
    2. elementData:数组,该数组的大小,经常与 ArrayList 的size 混淆,需要注意。
    3. DEFAULT_CAPACITY:数组的初始大小,默认是 10
    4. size 表示当前ArrayList实际有多少个数据,没有使用 volatile 修饰;
    5. modCount :当前数组的版本号,数组结构有变动,就会 +1。

    类介绍(注释)

    类注释大致内容如下:

    • 允许 null 值,会自动扩容,实现了List接口的所有方法;
    • size、isEmpty、get、set、add 等方法时间复杂度都是 O (1);
    • 是非线程安全的,多线程情况下,推荐使用线程安全类:Collections#synchronizedList;
    • 增强 for 循环,或者使用迭代器迭代过程中,如果数组大小被改变,会快速失败,抛出ConcurrentModificationException异常。

    源码解析

    构造方法

    ArrayList提供了三种构造方法。

    1. 无参构造方法
    2. 指定大小
    3. 指定初始数据
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    //无参数直接初始化,数组大小为空
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // 指定大小,主要是判断指定大小的合理性(>=0)
    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(Collection<? extends E> c) {
        elementData = c.toArray();
        // c 有内容
        if ((size = elementData.length) != 0) {
            // 如果集合元素类型不是 Object 类型,我们会转成 Object
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // c 没有内容,则为空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

    构造方法补充

    1. ArrayList 无参构造器初始化时,默认大小是空数组,并不是大家常说的 10,10 是在第一次 add 的时候扩容的数组值。
    2. 指定初始数据初始化时,我们发现一个这样子的注释 c.toArray might (incorrectly) not return Object[] see 6260652,这是 Java8 的一个 bug,意思是当给定集合内的元素不是 Object 类型时,我们会转化成 Object 的类型。一般情况下都不会触发此 bug,只有在下列场景下才会触发:ArrayList 初始化之后(ArrayList 元素非 Object 类型),再次调用 toArray 方法,得到 Object 数组,并且往 Object 数组赋值时,才会触发此 bug。官方查看文档地址:https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 ,问题在 Java 9 中被解决。

    添加元素、扩容

    ArrayList 提供了两种方式添加元素。我们选取较简单的一种,即在末尾添加。
    添加元素分为两步:

    1. 确认容量是否足够,不足则扩容
    2. 在末尾赋值
    public boolean add(E e) {
        // 判断容量是否足够(当前大小+1)
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        
        // 直接赋值,非线程安全操作
        elementData[size++] = e;
        return true;
    }
    
    

    接下来追溯到ensureCapacityInternal方法的源码,为了便于理解,以下是简单整理所得,并非原版。

    private void ensureCapacityInternal(int minCapacity) {
        // 如果初始化数组大小时,没有给定初始值,才会走if分支
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity();
    }
    
    
    private void ensureExplicitCapacity(int minCapacity) {
        // 版本号+1
        modCount++;
    
        // 如果我们期望的容量,(即add操作时,传入的size+1) 超过 目前数组的长度,那么就扩容
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    

    最后是扩容-grow方法源码

    // 允许JVM分配的最大数组空间
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // oldCapacity >> 1 相当于 oldCapacity / 2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        // 如果扩容后的容量 < 我们的期望值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        
        // 如果扩容后的容量 > 允许JVM分配的最大数组空间,则使用 Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        
        // minCapacity is usually close to size, so this is a win:
        // 通过Arrays.copyOf方法进行扩容,同时复制了数据
        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;
    }
    

    在添加元素、扩容的源码中,我们应该注意:

    1. 扩容是原来容量大小 + 容量大小的一半,直白来说,扩容后的大小是原来容量的 1.5 倍;
    2. ArrayList 中的数组的最大值是 Integer.MAX_VALUE,超过这个值,在hugeCapacity方法中,也只会给Integer.MAX_VALUE。
    3. 新增时,并没有对值进行严格的校验,所以 ArrayList 是允许 null 值的。
    4. 源码在扩容的时候,有数组大小溢出意识,就是说扩容后数组的大小下界不能小于 0,上界不能大于 Integer 的最大值

    扩容的核心实现

    从以上源码,我们发现grow方法的核心实现,在于以下一句。

    elementData = Arrays.copyOf(elementData, newCapacity);
    

    该方法最终调用的,是System.arraycopy。
    image.png

    删除元素

    ArrayList提供了多个重载的remove方法,其中的实现大同小异,下面以remove``(``**Object **``o``),即删除指定对象的方式为例。

    public boolean remove(Object o) {
        // 需要删除的对象为 null
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    // 删除第一个找到的null值后,直接结束方法
                    fastRemove(index);
                    return true;
                }
        } else {
            // 需要删除的对象不为 null
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    // 通过equals方法,删除第一个找到的指定元素后,直接结束方法
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    

    以上源码中,可以发现,最终都是调用了fastRemove(index);通过索引来快速删除元素,除此之外需要额外注意:

    • 新增的时候是没有对 null 进行校验的,所以删除的时候也是允许删除 null 值的;
    • 需要删除的对象不为 null时,找到值在数组中的索引位置,是通过 equals 来判断的,如果数组元素不是基本类型,我们需要关注 equals 的具体实现。

    下面来看看fastRemove的实现:
    那为什么叫快速删除呢?通过注释可以看出,此方法跳过了下标范围检测、未返回任何值。

    	/*
         * Private remove method that skips bounds checking and does not
         * return the value removed.
         */
    private void fastRemove(int index) {
        // 更新版本号
        modCount++;
        
        // 计算需要移动的元素个数(从中间删除后,保证数组连续,会将后方元素前移)
        // 减 1 的原因,是因为 size 从 1 开始算起,index 从 0开始算起
        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
    }
    

    迭代(Iterator)

    ArrayList通过实现 java.util.Iterator接口,达到迭代器的效果。以下是几个重要参数:

    1. int cursor;// 迭代过程中,下一个元素的位置,默认从 0 开始。
    2. int lastRet = -1; // 新增场景:表示上一次迭代过程中,索引的位置;删除场景:为 -1。
    3. int expectedModCount = modCount;// expectedModCount 表示迭代过程中,期望的版本号;

    迭代器的实现,通常有hasNext、next、remove 三个方法。以下为ArrayList中方法的实现:

    public boolean hasNext() {
      // cursor 表示下一个元素的位置,size 表示实际元素个数
      // 如果两者相等,说明已经没有元素可以迭代了;如果不相等,说明还可以迭代
      return cursor != size;
    }
    
    public E next() {
      // 迭代过程中,判断版本号是否被修改。如被修改,抛出 ConcurrentModificationException
      checkForComodification();
      // 本次迭代过程中,元素的索引位置
      int i = cursor;
      if (i >= size)
        throw new NoSuchElementException();
        
      Object[] elementData = ArrayList.this.elementData;
      if (i >= elementData.length)
        throw new ConcurrentModificationException();
        
      // 下一次迭代时,元素的位置
      cursor = i + 1;
      // 返回元素值
      return (E) elementData[lastRet = i];
    }
    
    // 判断版本号是否被修改。如被修改,抛出 ConcurrentModificationException
    final void checkForComodification() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
    

    从源码中可以看到,next 方法就干了两件事情,第一是检验能不能继续迭代,第二是找到迭代的值,并为下一次迭代做准备( cursor = i + 1)。再看remove方法,我们需要注意其中两点:

    1. lastRet = -1 的操作目的,是防止重复删除操作
    2. 删除元素成功,数组当前 modCount 就会发生变化,这里会把 expectedModCount 重新赋值,下次迭代时两者的值就会一致了
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        // 判断版本号是否被修改
        checkForComodification();
    
        try {
            // 这里调用的是 ArrayList的remove方法
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            
            // -1 表示元素已经被删除,这里也防止重复删除
            lastRet = -1;
            
            // 删除元素时 modCount 的值已经发生变化,在此赋值给 expectedModCount
        	// 这样下次迭代时,两者的值是一致的了
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    

    缩容

    ArrayList并未提供自动缩容的机制,但可以通过手动调用trimToSize方法,来使其空间利用率达到100%。
    如以下场景:系统启动,初始化一些数据到ArrayList中缓存起来,这些数据比较多(几千个元素)但是根据业务场景是不会变的。源码较为简单:

    public void trimToSize() {
        // 增加版本号
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
        }
    }
    

    ArrayList的线程安全

    只有当 ArrayList 作为共享变量时,才会有线程安全问题,当 ArrayList 是方法内的局部变量时,是没有线程安全的问题的。
    ArrayList 有线程安全问题的本质,是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时,都没有加锁,而且这些变量的类型并非是可见(volatile)的,所以如果多个线程对这些变量进行操作时,可能会有值被覆盖的情况。
    类的注释中推荐我们使用 Collections#synchronizedList 来保证线程安全,SynchronizedList 是通过在每个方法上面加上锁来实现,虽然实现了线程安全,但是性能大大降低,如add操作:

    public void add(int index, E element) {
        // synchronized 是一种轻量锁,mutex 表示一个当前 SynchronizedList
        synchronized (mutex) {list.add(index, element);}
    }
    

    时间复杂度

    从我们上面新增或删除方法的源码解析,根据数组索引对数组元素的操作,复杂度是 O (1)。而遇到扩容时,复杂度为O(n)。

    展开全文
  • ArrayList源码.zip

    2021-03-13 23:53:25
    ArrayList源码.zip
  • ArrayList源码分析

    2019-03-30 11:33:41
    根据arraylist源码分析,自己编写了一个类似于arraylist集合的代码
  • ArrayLIst源码探究

    2017-04-12 20:28:03
    ArrayList源码

    一直知道ArrayList内部是使用数组实现的,但之前也只是大致扫过部分方法的源码,趁着刷剑指offer第二遍的空隙看一下源码,源码问题多次面试也都问到了。
    ArrayList内部维持一个数组:

    transient Object[] elementData;
    private int size;

    size保存ArrayList中的实际元素数量,size不一定等于elementData的长度,一般小于它,这个数组的初始容量为10。
    那么ArrayList是如何保证实现动态改变数组容量的呢?在每次执行添加操作时,会先判断此时elementData数组是否有足够的的容量,若没有则扩展数组为原来的1.5倍,如下:

    // 在指定位置插入元素
    public void add(int index, E element) {
            rangeCheckForAdd(index);// 先检查索引是否有效
    
            ensureCapacityInternal(size + 1); // 保证数组大小
            System.arraycopy(elementData, index, elementData, index + 1, size - index);// 将数组指定索引后边元素向前移动
            elementData[index] = element;
            size++;
    }
    private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
        }
        // Explicit:明确的
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
            // conscious:自觉地
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
    
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        /**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified(指定) by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        // 增长1.5倍
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);// 1.5倍
            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);
        }

    我感觉在源码里边这个地方设计的特别好(难理解),removeAll和retainAll调用了同一个方法batchRemove:

    // 这是删除集合c存在ArrayList中的元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
    // retain:保留;保留集合c中的元素,其余删除
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    private boolean batchRemove(Collection<?> c, boolean complement) {
            final Object[] elementData = this.elementData;
            int r = 0, w = 0;
            boolean modified = false;
            try {
                //精髓
                /*
                    complement:true时保留集合c中的值,false时删除c中的值remove。
                    当for循环结束时,符合要求的值被依次写入数组
                */
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally {
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) {
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                // 数组有变化
                if (w != size) {
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;
                    modified = true;
                }
            }
            return modified;
    }
    展开全文
  • 阅读ArrayList源码个人理解 近期阅读了java.util.ArrayList.java的源代码 ArrayList介绍 从贴出代码不难看出,ArrayList是继承了AbstractList,并且实现了List,RandomAccess,Cloneable,java.io.Serializable。...

    阅读ArrayList源码个人理解

    近期阅读了java.util.ArrayList.java的源代码

    ArrayList介绍

    从贴出代码不难看出,ArrayList是继承了AbstractList,并且实现了List,RandomAccess,Cloneable,java.io.Serializable。

    ArrayList可以无限延展下去的特点。

    ArrayList实现了Serializable接口,使它可以序列化之后持久的“存在”。

    注释:序列化,我很困惑,然后就啪啪去查阅。最终自己的大致理解就是,一个java对象可以通过序列化,转化成一个序列,字节序列,包括这个对象的数据、属性、对象的类型等信息,然后这个序列化之后的对象可以被持久的保存在文件中,可以存储以及传输,之后再对文件通过反序列化之后实例成对象。

     ArrayList属性分析

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        private static final long serialVersionUID = 8683452581122892189L;
    
        /**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        transient Object[] elementData;
    
        private int size;
        
        ...
        ...
    }

    serialVersionUID:这个是序列化的标识,序列化和反序列化会通过这个标识进行校验。

    DEFAULT_CAPACITY:这个是初始化的数组大小。

    EMPTY_ELEMENTDATA:初始化空的示例数组。

    DEFAULTCAPACITY_EMPTY_ELEMENTDATA:初始化的时候利用DEFAULT_CAPACITY来限定实例数组的长度大小。

    elementData:使用transient关键字修饰的elementData。它是存储数组的变量,对于ArrayList非常重要。

    注释:transient,java关键字,其修饰的对象不会进行序列化。

    size:记录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);
            }
        }
    
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

    ArrayList构造参数:为带长度大小的,不带参数的。

        /**
         * Trims the capacity of this <tt>ArrayList</tt> instance to be the
         * list's current size.  An application can use this operation to minimize
         * the storage of an <tt>ArrayList</tt> instance.
         */
        public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }
    

    trimToSize:这个方法是为了,节省空间的,每次ArrayList扩容的时候到会多出一点点,然后可以使用这方法删除多余的空间,这样就可以节约空间。

        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 void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

    ensureCapacity:对ArrayList进行扩容。简而言之,通过定量的扩充ArrayList的长度,避免在add()的时候,多次扩容,减少扩容的时间。

    参考:https://blog.csdn.net/nzh1234/article/details/22752095

    ensureExplicitCapacity:进行扩容的操作。

        /**
         * The maximum size of array to allocate.
         * Some VMs reserve some header words in an array.
         * Attempts to allocate larger arrays may result in
         * OutOfMemoryError: Requested array size exceeds VM limit
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        /**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        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;
        }

    grow:扩容的方法。对elementData进行操作。

        public int indexOf(Object o) {
            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;
        }

    indexOf:用来判断是否包含相应的对象,如果没有就返回-1。

        /**
         * Checks if the given index is in range.  If not, throws an appropriate
         * runtime exception.  This method does *not* check if the index is
         * negative: It is always used immediately prior to an array access,
         * which throws an ArrayIndexOutOfBoundsException if index is negative.
         */
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        /**
         * A version of rangeCheck used by add and addAll.
         */
        private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private String outOfBoundsMsg(int index) {
            return "Index: "+index+", Size: "+size;
        }

    这里是几个异常的输出,基本就是判断是否越界。

    rangeCheck:主要是对于获取指定位置的对象,移除指定位置的对象,已经更新指定位置的对象这些操作的检查。

    rangeCheckForAdd:对新增对象,超过ArrayList的容量。

    outOfBoundsMsg:我们经常看见的越界的错误信息就是这个地方定义抛出的错误。

    整个ArrayList的源码实现,实际上还是有很多内容的,我只是浅显理解,然后把自己的理解转化成可以便于理解的文字,ArrayList在实际的开发中利用是极其广泛的,深入理解ArrayList的源码还是对日常的开发工作是有很多很大好处。

    这里只是介绍了一部分内容,在迭代器这块没有任何涉及,如有错误请指正,谢谢!我将积极更正。

    最后附上ArrayList的源码,源码来自于开源平台,这里只提供下载,不做其他用途。

    https://download.csdn.net/download/la859962513/10681442,好像不可以设置免费。

     

     

    展开全文
  • ArrayList源码阅读笔记

    2020-07-15 16:51:46
    ArrayList源码阅读笔记 -- 介绍了ArrayList 普通增删改查的过程,从构造空参构造方法,然后添加元素,修改元素,删除元素,获取元素.
  • ArrayList 源码分析

    2019-01-09 22:49:32
    公众号原文:ArrayList 源码分析 博客原文:ArrayList 源码分析 以下源码分析使用的 Java 版本为 1.8 1. 概览 ArrayList 是基于数组实现的,继承 AbstractList, 实现了 List、RandomAccess、Cloneable、...
  • 学习笔记ArrayList源码学习

    万次阅读 2019-08-06 18:17:23
    ArrayList源码学习 继承自AbstractList,实现了List接口 private static final int DEFAULT_CAPACITY = 10 默认容量为10 transient Object[] elementData 底层使用Object数组来存储数据 ArrayList(int ...
  • ArrayList 源码深度解析

    2021-01-20 03:27:29
    ArrayList 源码深度解析 一、重新认识ArrayList 什么是ArrayListArrayList是基于数组实现的List类,封装了一个动态再分配的Object数组,以达到可以动态增长和缩减的索引序列。 长啥样? 如图,是一个长度为6,...
  • ArrayList源码阅读

    千次阅读 2018-09-21 20:07:31
    ArrayList源码阅读

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,002
精华内容 7,200
关键字:

arraylist源码