JDK1.8 ArrayList 扩容详解

以你之姓@ 2022-05-22 02:40 266阅读 0赞

arraylist这个数据结构比较简单，总体来说，arraylist 底层结构是数组，他的很多方法都是从数组上面演变而来的，下面分析下arraylist的扩容机制，

每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。如果容量够，直接添加，否则需要进行扩容。在1.8 arraylist这个类中，扩容调用的是grow()方法，通过grow()方法中调用的Arrays.copyof()方法进行对原数组的复制，在通过调用System.arraycopy()方法进行复制，达到扩容的目的

几个重要的初始化值

[java] view plain copy

  1. 存储数组元素的缓冲区
  2. // non-private to simplify nested class access
  3. transient Object[] elementData;
  4. 默认空数组元素
  5. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  6. 默认初始化容量
  7. private static final int DEFAULT_CAPACITY = 10;
  8. 数组的大小
  9. private int size;
  10. 记录被修改的次数
  11. protected transient int modCount = 0;
  12. 数组的最大值
  13. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

几个重要的方法

一个空的构造方法

[java] view plain copy

  1. 默认数组的长度为10
  2. public ArrayList() {
  3. this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  4. }

添加元素的方法，

[java] view plain copy

  1. public boolean add(E e) {
  2. 扩充长度，在原来的大小上面加1
  3. // Increments modCount!!
  4. ensureCapacityInternal(size + 1);
  5. 添加元素
  6. elementData[size++] = e;
  7. return true;
  8. }

确认内部容量

[java] view plain copy

  1. private void ensureCapacityInternal(int minCapacity) {
  2. ensureExplicitCapacity(
  3. calculateCapacity(elementData, minCapacity));
  4. }

计算容量

[java] view plain copy

  1. private static int calculateCapacity (Object[] elementData, int minCapacity) {
  2. 如果这个数组等于空，返回最大的容量，否则，还是原来的容量
  3. if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  4. return Math.max(DEFAULT_CAPACITY, minCapacity);
  5. }
  6. return minCapacity;
  7. }

确认扩展容量

[java] view plain copy

  1. private void ensureExplicitCapacity(int minCapacity) {
  2. 修改次数加1
  3. modCount++;
  4. 如果容量不够，调用增加容量方法
  5. // overflow-conscious code
  6. if (minCapacity - elementData.length > 0)
  7. grow(minCapacity);
  8. }

扩展方法

[java] view plain copy

  1. private void grow(int minCapacity) {
  2. // overflow-conscious code
  3. 获取原来数组容量的长度
  4. int oldCapacity = elementData.length;
  5. 新增加的容量长度为原来容量的1.5倍
  6. int newCapacity = oldCapacity + (oldCapacity >> 1);
  7. 新容量比老容量小，那么新的容量就是老的容量
  8. if (newCapacity - minCapacity < 0)
  9. newCapacity = minCapacity;
  10. 新创建的容量超过数组的最大值。抛出异常
  11. if (newCapacity - MAX_ARRAY_SIZE > 0)
  12. newCapacity = hugeCapacity(minCapacity);
  13. // minCapacity is usually close to size, so this is a win:
  15. 调用复制方法，在原来元素上增加容量，这就是传说中的可变集合。用新长度复制原数组。
  16. elementData = Arrays.copyOf(elementData, newCapacity);
  17. }

数组工具类中的复制方法

[java] view plain copy

  1. public static T[] copyOf (T[] original, int newLength) {
  2. return (T[]) copyOf(original, newLength, original.getClass());
  3. }

具体的复制方法

[java] view plain copy

  1. public static T[] copyOf(U[] original, int newLength,
  2. Class<? extends T[]> newType) {
  3. @SuppressWarnings(“unchecked”)
  4. 获得者数组对象
  5. T[] copy = ((Object)newType == (Object)Object[].class)
  6. ? (T[]) new Object[newLength]
  7. : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  9. 调用系统的方法增加数组容量
  10. System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
  11. return copy;
  12. }

发表评论

表情：
评论列表 （有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读

    相关 ArrayList扩容处理

    ArrayList是基于动态数组实现的一个数据结构，如果添加元素时，元素个数超过list的容量大小时，会涉及到扩容。   ArrayList的扩容是如何做的，跟着代码走最容

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 321 阅读