本文共 2583 字,大约阅读时间需要 8 分钟。
arraylist这个数据结构比较简单,总体来说,arraylist 底层结构是数组,他的很多方法都是从数组上面演变而来的,下面分析下arraylist的扩容机制, 每次在add()一个元素时,arraylist都需要对这个list的容量进行一个判断。如果容量够,直接添加,否则需要进行扩容。在1.8 arraylist这个类中,扩容调用的是grow()方法,通过grow()方法中调用的Arrays.copyof()方法进行对原数组的复制,在通过调用System.arraycopy()方法进行复制,达到扩容的目的 - 存储数组元素的缓冲区
-
- transient Object[] elementData;
- 默认空数组元素
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- 默认初始化容量
- private static final int DEFAULT_CAPACITY = 10;
- 数组的大小
- private int size;
- 记录被修改的次数
- protected transient int modCount = 0;
- 数组的最大值
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
几个重要的方法 - 默认数组的长度为10
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- public boolean add(E e) {
- 扩充长度,在原来的大小上面加1
-
- ensureCapacityInternal(size + 1);
- 添加元素
- elementData[size++] = e;
- return true;
- }
确认内部容量 - private void ensureCapacityInternal(int minCapacity) {
- ensureExplicitCapacity(
- calculateCapacity(elementData, minCapacity));
- }
- private static int calculateCapacity (Object[] elementData, int minCapacity) {
- 如果这个数组等于空,返回最大的容量,否则,还是原来的容量
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- return minCapacity;
- }
- private void ensureExplicitCapacity(int minCapacity) {
- 修改次数加1
- modCount++;
- 如果容量不够,调用增加容量方法
-
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
- private void grow(int minCapacity) {
-
- 获取原来数组容量的长度
- 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);
- }
- public static <T> T[] copyOf (T[] original, int newLength) {
- return (T[]) copyOf(original, newLength, original.getClass());
- }
- public static <T,U> T[] copyOf(U[] original, int newLength,
- Class<? extends T[]> newType) {
- @SuppressWarnings("unchecked")
- 获得者数组对象
- T[] copy = ((Object)newType == (Object)Object[].class)
- ? (T[]) new Object[newLength]
- : (T[]) Array.newInstance(newType.getComponentType(), newLength);
-
- 调用系统的方法增加数组容量
- System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
- return copy;
- }
转载地址:http://fhnmi.baihongyu.com/