1. 如何实现Arraylist的add方法,插入时数组满了怎么办,扩容的话新数组是多大?
作者:肥宝er
链接:https://www.nowcoder.com/discuss/80927
来源:牛客网
ArrayList是基于数组实现的,新增元素默认添加到数组的尾部,插入时数组满了会自动扩容,新数组是旧数组的1.5倍。 下面为addd()方法的源码,其中size指的是数组中存放元素的个数,elementData.length表示数组的长度,当new一个ArrayList系统默认产生一个长度为10的elementData数组,elementData.length=10,但是由于elementData中还未放任何元素所有size=0。如果加入元素后数组大小不够会先进行扩容,每次扩容都将数组大小增大一半,比如数组大小为10一次扩容后的大小为10+5=10;ArrayList的最大长度为 2^32 .
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 加入元素前检查数组的容量是否足够
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(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;//如果扩充一半后仍然不够,则 newCapacity = minCapacity;minCapacity实际元素的个数。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//数组最大位2^32
elementData = Arrays.copyOf(elementData, newCapacity);
}