精华内容
下载资源
问答
  • ArrayList底层原理

    2020-08-16 16:51:03
    ArrayList底层主体就是一个Object数组,对ArrayList的所有底层操作就是基于数组实现的 1.ArrayList的线程安全性 对ArrayList进行添加操作的时候是分两个步骤进行的,即第一步先在object[size]的位置上存放需要...

    ArrayList是抽象类AbstractList的子类,实现了List接口、RandomAccess(随机访问)等接口
    在这里插入图片描述
    ArrayList的底层主体就是一个Object数组,对ArrayList的所有底层操作就是基于数组实现的
    在这里插入图片描述

    1.ArrayList的线程安全性

    对ArrayList进行添加操作的时候是分两个步骤进行的,即第一步先在object[size]的位置上存放需要添加的元素,第二步就是将size的值增加1,由于这个过程在多线程的环境下是不能保证具有原子性的,因此ArrayList在多线程的环境下是线程不安全的

    2.ArrayList的主要成员变量

    • private final int DEFAULT_CAPACITY=10:当ArrayList的构造方法中没有显式指出ArraList的数组长度时,类内部使用默认的容量大小为10
    • private static final Object[] EMPTY_ELEMENTDATA={}:当ArrayList的构造方法中显式指出ArrayList的数组长度为0时,类内部将EMPTY_ELEMENTDATA这个空对象数组赋给elementData数组
    • private static final Object[] DEFAULT_EMPTY_ELEMENTDATA={}:当ArrayList的构造方法中没有显式指出ArraList的数组长度时,类内部使用默认缺省时对象数组
    • private int size:实际ArrayList中存放的元素的个数,默认时为0

    3.ArrayList的构造函数

    指定ArrayList数组容量大小:
    在这里插入图片描述
    当没有显式指定数组容量大小时,指定数组大小为10:
    在这里插入图片描述
    Collection<? extends E>类型构造方法:
    在这里插入图片描述

    4.ArrayList的add()方法

    在add()方法中主要完成了三件事:

    • 首先判断数组中元素个数是否已经等于数组长度,如果是,则进行扩容操作
    • 然后将元素添加到elementData数组的指定位置
    • 最后将集合中实际的元素个数加1
      在这里插入图片描述

    5.ArrayList的扩容机制grow()方法

    将可允许的数组的最小容量传过去(最小容量mincapacity=size+1是因为要添加一个元素,所以进行加一操作)
    在这里插入图片描述
    调用复制copyOf()方法,在原来元素基础上增加容量:
    在这里插入图片描述
    这里就涉及到扩容最重要的方法:newCapacity()

    • 首先获取数组长度
    • 将数组长度扩容为原数组长度的1.5倍
    • 将新容量和所需最小容量做对比,看到这可能会觉得感到疑惑:最小容量我们知道minCapacity=size+1(此时的size等于length,因为size==element.length才会进行扩容嘛),即数组中元素大小加1,而newCapacity=elementData.length*1.5,按道理来说一个是原来的1.5倍,一个只是+1操作,那肯定是1.5倍那个大,这个比较不就是多余的了吗?这里我们可能会忽略一种非常重要的情况:当数组为空时数组为空又分为两种情况:(1)指定了数组容量为0 (2)没有显式指定数组大小。当数组为空时我们进行插入操作,因为元素个数size为0,数组容量也为0,那么就会进行扩容操作,对于空数组,扩容1.5倍后你的容量还是为0,那么此时就会小于我所需的最小容量(也就是1),所以这里就是针对数组为空的情况,那么对于第一种指定了数组长度为0,它扩容后的容量就是1;对于第二种情况,扩容后的数组长度就是DEFAULT_CAPACITY,也就是10
    • 最后判断新容量大小是否大于默认数组的最大值(Integer.MAX_VALUE-8),则赋予它整型的最大值
      在这里插入图片描述

    补充

    1.ArrayList和Array的区别是什么

    1. 存储内容比较:Array可以包含基本类型和对象类型,ArrayList只能存储对象类型
    2. 空间大小比较:Array数组的空间大小是固定的,所以需要提前确定合适的空间大小,ArrayList的空间大小是动态增长的,而且存在扩容机制
    3. 方法上的比较:ArrayList比Array更多样化

    2.ArrayList和LinkedList的区别是什么

    1. 数据结构实现上:ArrayList的底层是数组,ArraList的底层是双向链表
    2. 随机访问效率上:ArrayList实现了RandomAccess接口,所以支持随机访问,LinkedList不支持随机访问
    3. 增加和删除效率上:在非首尾的增加 和删除操作,LinkedList要比ArrayList高
    4. LinkedList比ArrayList更占空间内存
    展开全文
  • // 指定大小的构造方法 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 按照参数初始化数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // ...

    初始化

    有两个构造方法,一个带参数的是自己指定大小,一个不带参数的则是默认大小为10,可以看到如果是使用默认构造方法的话,不会立刻初始化一个大小为10的数组,而是指向了一个空数组,这是为了避免初始化之后又没插入数据而带来的空间浪费。

    // 默认大小

    private static final int DEFAULT_CAPACITY = 10;

    // 空数组

    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 默认构造方法使用的空数组

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 真实存放数据的数组

    transient Object[] elementData;

    // 指定大小的构造方法

    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;

    }

    add()方法

    这个方法是直接往list里面添加元素,可以看到它会判断数组是否初始化了,如果没有这个时候才会真正的初始化数组,然后直接把元素放到数组中,时间复杂度是O(1)。

    // 在数组最后面添加一个元素

    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++;

    // 添加后的长度要比数组大,需要调用grow()方法扩容

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    grow(minCapacity);

    }

    set(int index, E element)方法

    这个方法是覆盖一索引上的旧值,然后返回这个旧值,可以看到就是判断下索引越界问题,然后获取数组中的值返回,再把新值放进去,时间复杂度是O(1)。

    public E set(int index, E element) {

    rangeCheck(index);

    E oldValue = elementData(index);

    elementData[index] = element;

    return oldValue;

    }

    private void rangeCheck(int index) {

    if (index >= size)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    add(int index, E element)方法

    这个方法和无参的add()方法的区别就是不是在数组后面顺序添加,而是指定位置的插入,可以看到检查是否扩容的逻辑没有变,主要是多了一步copy数组的操作,比如一个数组是[1,2,3,4,5],需要在索引1的位置插入一个10,会先从索引1的位置copy数组,把后面的数字都往后挪一位[1,2,2,3,4,5],然后再把索引1的2改为10,就成了[1,10,2,3,4,5],这个操作的时间复杂度就是O(n)了,因为最坏的情况就是插入到索引0,整个数组的值都要挪动一位。

    // 插入指定索引

    public void add(int index, E element) {

    // 检查索引越界

    rangeCheckForAdd(index);

    // 检查容量

    ensureCapacityInternal(size + 1); // Increments modCount!!

    // copy数组,在要插入的索引位置开始一直到最后一个值,整体往后挪一格,然后把新值填入要插入的索引中

    System.arraycopy(elementData, index, elementData, index + 1,

    size - index);

    elementData[index] = element;

    size++;

    }

    // 检查容量是否足够的方法

    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++;

    // 添加后的长度要比数组大,需要调用grow()方法扩容

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    grow(minCapacity);

    }

    addAll(Collection extends E> c)方法

    这个方法是直接把另一个集合里的值追加进来,判断一下容量,然后直接把要追加的里面的值copy过来,时间复杂度是O(n),n是追加集合的长度。

    public boolean addAll(Collection extends E> c) {

    Object[] a = c.toArray();

    int numNew = a.length;

    ensureCapacityInternal(size + numNew); // Increments modCount

    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

    }

    addAll(int index, Collection extends E> c)方法

    追加集合的方法也可以指定索引,就是addAll(Collection extends E> c)和add(int index, E element)的结合版,计算出索引后面的值要移动的位置进行移动,再把追加的集合的值copy到指定索引,时间复杂度也是O(n),但是n是追加集合的长度+数组移动元素的长度。

    public boolean addAll(int index, Collection extends E> c) {

    rangeCheckForAdd(index);

    Object[] a = c.toArray();

    int numNew = a.length;

    ensureCapacityInternal(size + numNew); // Increments modCount

    int numMoved = size - index;

    if (numMoved > 0)

    System.arraycopy(elementData, index, elementData, index + numNew,

    numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);

    size += numNew;

    return numNew != 0;

    }

    get()方法

    get()方法,没啥好说的了,直接就是在数组里取值,时间复杂度也是O(1)。

    public E get(int index) {

    rangeCheck(index);

    return elementData(index);

    }

    remove()方法

    remove()方法和插入方法很类似,但是更简单,直接把值取出来返回,然后把后面的值全部都往前挪一位,最后还把空出的那个索引位置置空让虚拟机GC清理,时间复杂度也是O(n)。

    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;

    }

    size()方法

    获取大小也是时间复杂度为O(1),直接读取变量值。

    private int size;

    public int size() {

    return size;

    }

    indexOf()/contains()方法

    这两个方法是用来获取指定目标索引和判断是否包含指定目标,contains()方法是调用indexOf()方法,而indexOf()方法是遍历判断,所以时间复杂度是O(n)。

    public boolean contains(Object o) {

    return indexOf(o) >= 0;

    }

    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;

    }

    扩容

    上面看到很多方法都会调用到grow()方法,也就是核心的扩容方法,可以看到本质上就是先使用位运算符来扩容1.5倍,再copy到一个新的数组,替代原来那个旧的数组。

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private void grow(int minCapacity) {

    // oldCapacity是存放数据数组的长度,也就是当前集合的长度

    // overflow-conscious code

    int oldCapacity = elementData.length;

    // newCapacity是计算出来的新长度,>>运算符是右移一位,相当于除以2,所以扩容是原来大小的1.5倍

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 扩容完之后还是不够用就直接拿所需要的最小容量作为容量值

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    // 新容量大于MAX_ARRAY_SIZE,直接使用Integer.MAX_VALUE作为新容量

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    // 把原来数组中的值copy到一个新的数组中

    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;

    }

    内部类ListItr

    这个类实现了ListIterator接口,而ListIterator又继承了Iterator接口,是一个功能更加强大的迭代器。

    // 将指定的元素插入列表,插入位置为迭代器当前位置之前

    add(E e);

    // 以正向遍历列表时,如果列表迭代器后面还有元素,则返回 true,否则返回false

    hasNext();

    // 如果以逆向遍历列表,列表迭代器前面还有元素,则返回 true,否则返回false

    hasPrevious();

    // 返回列表中ListIterator指向位置后面的元素

    next();

    // 返回列表中ListIterator所需位置后面元素的索引

    nextIndex();

    // 返回列表中ListIterator指向位置前面的元素

    previous();

    // 返回列表中ListIterator所需位置前面元素的索引

    previousIndex();

    // 从列表中删除next()或previous()返回的最后一个元素

    remove();

    // 从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e

    set(E e);

    展开全文
  • 理解ArrayList底层原理

    2019-07-03 19:11:41
    * 手写ArrayList 体会底层原理 * @author sofency * */ public class SofencyArrayList03<E> {//与泛型结合一起 private Object[] elementData; private int size; private static final int...

    实现ArrayList泛型的底层算法

    1. size() 返回数组列表的大小
    2. isEmpty() 返回数组列表是否为空
    3. remove(int index) 通过下标删除对象
    4. remove (E element) 删除对象
    5. add(E elment) 添加对象
    6. get(int index) 获取特定下标的对象
    7. set(E element,int index) 修改特定下标的对象
    package 容器myself;
    
    import java.io.ObjectInputStream.GetField;
    
    import javax.management.RuntimeErrorException;
    
    /**
     * 手写ArrayList 体会底层原理  实现remove
     * @author sofency
     *
     */
    public class SofencyArrayList05<E> {
    	private Object[] elementData;
    	private int size;
    	private static final int DEFAULT_CAPACITY=10;
    	public SofencyArrayList05(){
    		elementData=new Object[DEFAULT_CAPACITY];//默认的容量是10
    	}
    	public SofencyArrayList05(int capacity) {
    		if(capacity<0) {
    			throw new RuntimeException("容器的容量不能为零");
    		}else if(capacity==0) {
    			elementData=new Object[DEFAULT_CAPACITY];
    		}else {
    			 elementData=new Object[capacity];//传进数组列表的容量
    		}
    	}
    	public void add(E e) {//添加对象	
    		if(size==elementData.length) {//什么时候扩容
    			Object[] newArray=new Object[elementData.length+(elementData.length>>1)];//新创建数组 10->10+10/2 加号的优先级大于右移
    			System.arraycopy(elementData, 0, newArray, 0, elementData.length);
    			
    			elementData=newArray;//扩容
    		}
    		elementData[size++]=e;//将对象加到默认的数组列表中
    	}
    	public E get(int index) {	
    		checkRange(index);
    		return (E)elementData[index];//强转为E类型
    	}
    	public void set(E element,int index) {//修改下标index的值
    		checkRange(index);
    		elementData[index]=element;	
    	}
    	//移除元素
    	public void  remove(E element) {
    		for(int i=0;i<size;i++) {
    			if(element.equals(get(i))) {
    				remove(i);
    			}	
    		}
    	}
    	public void remove(int index) {	
    		int numMoved=elementData.length-index-1;
    		if(numMoved>0) {
    			System.arraycopy(elementData, index+1, elementData, index, numMoved);//复制后面的元素并且向前移动
    		}
    		elementData[--size]=null;
    	}
    	public int size() {
    		return size;//返回数组的大小
    	}
    	public boolean isEmpty() {
    		return size==0?true:false;
    	}
    	//检查下标的范围
    	public void checkRange(int index) {
    		if(index<0||index>size-1) {
    			//不合法
    			throw new RuntimeException("索引不合法");
    		}
    	}
    	//重写toString方法
    	@Override
    	public String toString() {
    		// TODO Auto-generated method stub
    		StringBuilder sb=new StringBuilder();
    		sb.append("[");
    		for (int i = 0; i < size; i++) {
    			sb.append(elementData[i]+",");
    		}
    		sb.setCharAt(sb.length()-1, ']');
    		return sb.toString();
    	}
    	public static void main(String[] args) {
    		SofencyArrayList05<String> sofency=new SofencyArrayList05<>(20);//默认为20个对象
    		sofency.add("aa");
    		sofency.add("bb");
    		
    		for(int i=0;i<40;i++) {
    			sofency.add("sofency"+i);
    		}
    		System.out.println(sofency.toString());	
    		//System.out.println(sofency.get(10));
    		sofency.remove(0);//根据下标删除
    		System.out.println(sofency.toString());
    		sofency.remove("bb");//根据元素删除
    		System.out.println(sofency.toString());
    		
    		System.out.println(sofency.size());
    		System.out.println(sofency.isEmpty());
    		
    		sofency.remove(1);
    		System.out.println(sofency.size());
    	}
    }
    

    类型擦除问题
    泛型的引入主要为了解决某些容器,算法等代码的通用性而引入的,并且能在编译期间作类型检查。但是我们在使用泛型进行类型判断是往往会出错。因为泛型在运行期间进行类型擦除,也就是ArrayList在运行的过程中实际上是ArrayList类型的,
    下面那样写时非法的。
    在这里插入图片描述

    展开全文
  • ArrayList底层原理浅析

    2020-12-05 02:50:13
    一. ArrayList和LinkedList异同 1. 相同点:  ...ArrayList底层仍然是使用数组(Object[] elementData)实现的,通过对数组操作的封装,简化了程序员编程中对集合的使用过程。ArrayList是List

    一. ArrayList和LinkedList异同

    1. 相同点:

         ArrayList 和LinkedList 都是List 接口下的实现类,相同于List接口,这两个实现类也同样是有序且不唯一(可重复)的集合类。

    2. 不同点:

          ArrayList 的底层仍然是使用数组(Object[] elementData)实现的,通过对数组操作的封装,简化了程序员编程中对集合的使用过程。ArrayList是List接口的主要实现类,也就是使用得最多的,因为其效率高,但是线程不安全。
       LinkedList 不同于ArrayList,其底层使用了双向链表存储数据,实现集合功能。由于其是双向链表实现,对于集合插入、删除需求高的情况,建议使用LinkedList。

    二. ArrayList的底层实现原理浅析

    1. 部分成员变量及常量的作用

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData;
    private int size;
    // 常量MAX_ARRAY_SIZE表示整型的最大值-8,文末会用到并解释作用
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    

          这是在ArrayList 源码中的部分成员变量及常量,先对这几个解释以便后续理解。
         Object[] elementData:前面提到ArrayList 其实就是以数组存储数据的,elementData就是该存储数据的数组,后续对数组的数据操作就是对该数组的操作。

         private int size:size指的是该elementData的容量大小。

          final int DEFAULT_CAPACITY = 10:当使用ArrayList 的无带参构造方法初始化时,即无指定数组容量,会有一个默认的数组容量,就是DEFAULT_CAPACITY ,即数组容量默认是10。

       final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}:该常量是一个空数组,当ArrayList 初始化时,若没有指定容量大小,即调用无带参构造函数,在底层会先将elementData初始化为空数组。

    2. ArrayList的构造方法

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
        
    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);
        }
    }
    
    • 调用ArrayList 的无参构造函数时,会先将elementData 初始化为空数组,即赋值为常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
            值得注意的是,当ArrayList 初始化时,若没有指定容量大小,即调用无参构造方法,在底层会先将elementData初始化为空数组,而不是直接将elementData初始化为默认容量(10)。当开始对elementData进行存储数据的操作时,才会将其容量拓展为默认容量(10)。为什么要提这一点呢,因为该情况是JDK1.8对ArrayList进行优化后才出现的,最初在JDK1.7及之前版本,对ArrayList 的初始化后,若无指定容量则直接将elementData初始化为默认容量(10)。
            相比于JDK1.7,JDK1.8的做法不会在初始化ArrayList 后就创建空间,而是等到真正需要将数据存入数组时才拓展容量,对内存占用有所优化。

    • 调用带参构造方法时,根据传入的int类型变量initialCapacity,initialCapacity即为指定的容量大小,将数组初始化为指定容量大小的数组。
      若传参initialCapacity为0,则进行相同于无参构造方法的操作,即elementData为空数组,当开始对elementData进行存储数据的操作时,将其容量拓展为默认容量(10)。
      若initialCapacity < 0,则抛出异常。

    • 除此之外ArrayList还有一个带参构造方法传入的参数是Collection<? extends E> c。该构造方法按照它们由集合的迭代器返回的顺序构造一个包含指定集合的元素的列表。
      源码如下:

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

    3. ArrayList的add方法及容量拓展

          我们知道ArrayList 的底层数组elementData的容量要么是默认值(10),要么是指定容量。但是当我们对其进行添加数据超过了elementData的容量大小会怎么样呢?这时候就需要进行容量拓展的处理,前面说到的elementData初始化为空数组,等到对数据进行存储时才进行的容量拓展是也是类似的处理方式,只不过根据具体情况的不同会有些许步骤有所差别。
          注意:虽说是数组的容量拓展,但其实并不是扩大原有数组的大小,因为数组一旦定义大小是不可改变。所谓的容量拓展是以原有的数组容量为基础,根据具体情况新建一个符合条件容量的数组,并将原数组数据复制到该新数组,以此实现容量拓展。这在后面会提到。
          接下来看看其处理过程。

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        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);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    

          容量拓展处理过程:此时先假设elementData容量大小n=10。当elementData的10个容量都已经存储了数据后,又有新的数据需要add()进来,此时调用ensureCapacityInternal(size + 1)方法,因为是要add()一个数据进来,所以传参是原本的数组大小+1,。在该方法中有一个if 语句

    private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
    }
    
    // 别忘了前面提到DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    

          这个if 语句存在的意义就是当elementData如果是初始化后的空数组时,就需要进行容量拓展,其拓展的容量就是默认容量10。这对应着上文提到的JDK1.8对ArrayList优化后的特点:若没有指定容量大小,即调用无参构造函数,在底层会先将elementData初始化为空数组,当开始对elementData进行add操作时,才会将其容量拓展为默认容量(10)。 将变量minCapacity设置为10后,调用ensureExplicitCapacity(minCapacity)。
          若elementData是非空数组,那么直接调用ensureExplicitCapacity(minCapacity)函数

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

          这个方法也有一条if 语句,表示的意思是当minCapacity 大于数组的长度时,则表明需要的数组容量已经比当前的数组容量大,因此需要进行容量拓展,而grow(minCapacity)方法就是对容量拓展的方法,将其调用。

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        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 + (oldCapacity >> 1)表示将当前容量大小拓展为1.5倍大小,即若原本容量大小n=10的话,拓展完后的容量n=15。由此可看出ArrayList正常情况下的容量拓展都是拓展为原来的1.5倍。拓展完的容量大小赋值给变量newCapacity后,接着进行判断,此时有两条if 语句:
          先看第一条if 语句:

     if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    

          第一个条if 语句表示当拓展后的容量比原来的容量还小时的情况。可是为什么n拓展为原来1.5倍却比原来小呢?这时候就回到之前说的若没有指定容量大小,即调用无参构造函数,在底层会先将elementData初始化为空数组,当开始对elementData进行存储数据的操作时,才会将其容量拓展为默认容量(10)。 也就是说当elementData为空数组时,长度为0,0的1.5倍仍然为0,所以要将容量直接拓展为minCapacity,而minCapacity的值在此情况下就是默认容量10。这条if 语句处理了调用无参构造函数,将elementData初始化为空数组的容量拓展问题。
          接着看第二条if 语句:

    if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
    
    // 常量MAX_ARRAY_SIZE表示整型的最大值-8
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    

          当拓展后的容量大于MAX_ARRAY_SIZE而又小于整型数的最大值时,那么将容量设置为整型数的最大值Integer.MAX_VALUE。这个处理在 hugeCapacity(minCapacity)方法内进行。源码如下:

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

          当确定拓展容量的具体数值后,接着grow方法下面的内容:

    elementData = Arrays.copyOf(elementData, newCapacity);
    

          这条语句调用了copyOf(elementData, newCapacity)方法,这就是之前提到的容量拓展不是扩大原有数组的大小,而是新建一个符合条件容量的新数组。
          在这些方法处理完后完成了容量拓展,就又回到了add()方法,此时接着执行add()的添加数据的操作,因为已经完成了容量拓展,对于新数据有了多余的容量存放。

          ArrayList 源码中还封装了对数组的各种操作的方法,建议可以去看看。本篇文章仅作为辅助理解ArrayList 部分源码。有错欢迎评论指出。

    展开全文
  • ArrayList底层原理学习

    2020-03-14 19:20:32
    一直以来,ArrayList都是一个熟悉的陌生人一样的存在,用都会用,也知道底层是数组,再深入问细节就懵逼。 1.构造方法 public ArrayList() public ArrayList(int initialCapacity) public ArrayList(Collection<?...
  • 原文地址:用大白话告诉你ArrayList底层原理 目录 一、数据结构 二、线程安全性 三、继承关系 四、构造方法 五、add()方法 六、扩容机制 七、set(int index,E element)方法 八、indexOf(Object o)方法 ...
  • ArrayList底层原理详解

    2020-02-28 12:56:45
    在讲ArrayList之前,先讲简单讲下List List集合代表一个有序集合,集合中每个元素都有其对应的顺序索引,它继承Collection接口,可以定义一个允许重复的有序集合 List接口的特点: 1、有下标 2、有顺序 3、能...
  • ArrayList底层原理及源码分析

    千次阅读 2019-09-24 16:01:41
    ArrayList底层数据结构核心其实是一个Object数组,对于ArrayList的操作都是基于这个Object进行操作而实现的。 二:内存模型/内存分配 这里我贴上一张我自己画的图,因为我在网上看到一些关于Ar...
  • ArrayList底层原理分析

    2019-10-15 19:37:45
    1 先看构造器 按照指定容量初始化一个elementData数组,就是个object数组 ...ArrayList中elementData为什么被transient修饰  https://blog.csdn.net/lishuoboy/article/details/102574176
  • 自定义实现一个AraayList,体会底层原理 增加泛型 数组扩容 增加set get方法和判读数组边界 增加remove 删除 @author fantaisheng */ public class FanArrayList5 { private Object[] elme...
  • 首先无论是ArrayList还是LinkedList这两个集合类,都是用于存储一系列的对象引用的。 1、ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构;2、对于随机访问get和set,ArrayList要优于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,492
精华内容 596
关键字:

arraylist底层原理