基于JDK1.8源码讲解ArrayList扩容机制
2022/1/1 17:09:47
本文主要是介绍基于JDK1.8源码讲解ArrayList扩容机制,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
现在有两组ArrayList,分别是list1和list2
List list1 = new ArrayList(); list1.add(1); list1.add(14); List list2 = new ArrayList(list1);
先说list1的情况,我们点进ArrayList查看ArrayList构造器(无参),如下会构造一个默认容量为10的ArrayList[],即Object[],此时的size为0
(如果我们分析list2的话,如果我们传进来的数组不是空数组,则他的容量大小以及size为传进来数组的长度;如果是空数组,则初始化一个空数组(EMPTY_ELEMENTDATA),这句话好像是废话.... )
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ 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; } }
我们重点看不传数组的现象
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
当我们去执行list.add的时候
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
elementData[size++]=e;这一行代码好理解,添加元素进数组,
我们重点看ensureCapacityInternal(size+1);这一行扩容代码.我们点进去查看
为了方便展示,我们在代码行里进行注释
private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }//如果我们使用的是无参构造器产生的ArrayList //则DEFAULT_CAPACITY为10(之前代码定义过),minCapacity的大小为size+1,则取最大的容量capacity,以免数组容量不够 ensureExplicitCapacity(minCapacity);//调用下一个函数 }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) //如果我们上述取得的minCapacity大于数组原有长度,调用下一个函数 grow(minCapacity); }
这里我们特别注意MAX_ARRAY_SIZE的大小为Integer最大值-8,他对数组长度溢出的约束有着大作用.
特别的,我们要知道:两个数字其中一个数字越界之后,A-B<0和A<B,会是两种不同的结果,A-B这个过程,我们可以自我忽略数组溢出的事情
System.out.println(Integer.MAX_VALUE + 1 - MAX_ARRAY_SIZE < 0);//false System.out.println(Integer.MAX_VALUE + 1 < MAX_ARRAY_SIZE);//true System.out.println(MAX_ARRAY_SIZE - (Integer.MAX_VALUE + 1) < 0);//true System.out.println(MAX_ARRAY_SIZE < Integer.MAX_VALUE + 1);//false System.out.println(Integer.MAX_VALUE + 1 - (Integer.MAX_VALUE + 2) < 0);//true System.out.println(Integer.MAX_VALUE + 1 < Integer.MAX_VALUE + 2);//true
接下来,我们看grow(minCapacity)方法
/** * 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; //原有数组长度增加3/2,>>即二进制右移1位,相当于原数字大小除以2 int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity和minCapacity,谁大取谁,不用管数字溢出的事,即使最大的数为负数 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果我们取得的最大的数比MAX_ARRAY_SIZE 还大,(通常不会有这种情况) if (newCapacity - MAX_ARRAY_SIZE > 0) //查看是否数组长度溢出的方法,这个方法有一个判断溢出的方法,溢出就抛出OutOfMemoryError newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: //溢出的话,在hugeCapacity()方法中就抛出异常了,到不了此方法,不溢出的话就copyOf(数组) elementData = Arrays.copyOf(elementData, newCapacity); }
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow //如果minCapacity为负数,则抛出内存超出错误 throw new OutOfMemoryError(); //返回最大的数组长度,到此结束 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
到此结束
这篇关于基于JDK1.8源码讲解ArrayList扩容机制的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南