WaleGarrett

List

3/22/2022 List

# ArrayList

img

# Arrays.asList用法问题

# 不能将Arrays.asList的结果赋值给ArrayList

那这到底为什么呢，因为Arrays.asList构建出来的List与new ArrayList得到的List，压根就不是一个List！类关系图如下；

img

# 不能直接使用 Arrays.asList 来转换基本类型数组

int[] arr = { 1, 2, 3 };
List list = Arrays.asList(arr);
log.info("list:{} size:{} class:{}", list, list.size(), list.get(0).getClass());

其原因是：Arrays.asList 方法传入的是一个泛型 T 类型可变参数，最终 int 数组整体作为了一个对象成为了泛型类型 T。

正确的转换方法：

int[] arr1 = { 1, 2, 3 };
List list1 = Arrays.stream(arr1).boxed().collect(Collectors.toList());
log.info("list:{} size:{} class:{}", list1, list1.size(), list1.get(0).getClass());

// 另一种转换方法，这里还需要注意的一个问题就是Arrays.asList返回的List与原来的数组是同一个数组，引用相同。
Integer[] arr2 = { 1, 2, 3 };
List list2 = Arrays.asList(arr2);
log.info("list:{} size:{} class:{}", list2, list2.size(), list2.get(0).getClass());

# Arrays.asList 返回的 List 不支持增删操作

String[] arr = { "1", "2", "3" };
List list = Arrays.asList(arr);
arr[1] = "4";
try {
    list.add("5");
} catch (Exception ex) {
    ex.printStackTrace();
}
log.info("arr:{} list:{}", Arrays.toString(arr), list);

  1. 抛出异常的原因在于 Arrays.asList 第二个问题点：Arrays.asList 返回的 List 不支持增删操作。Arrays.asList 返回的 List 并不是我们期望的 java.util.ArrayList，而是 Arrays 的内部类 ArrayList。

  2. 查看源码，我们可以发现 Arrays.asList 返回的 ArrayList 继承了 AbstractList，但是并没有覆写 add 和 remove 方法。

# 对原始数组的修改会影响到我们获得的那个 List

  1. Arrays.asList 第三个问题点：对原始数组的修改会影响到我们获得的那个 List。ArrayList 其实是直接使用了原始的数组。

  2. 解决方法很简单，重新 new 一个 ArrayList 初始化 Arrays.asList 返回的 List 即可：

String[] arr = { "1", "2", "3" };
List list = new ArrayList(Arrays.asList(arr));
arr[1] = "4";
try {
    list.add("5");
} catch (Exception ex) {
    ex.printStackTrace();
}
log.info("arr:{} list:{}", Arrays.toString(arr), list);

# ArrayList扩容机制

  1. 判断长度充足； ensureCapacityInternal(size + 1);

  2. 当判断长度不足时，则通过扩大函数，进行扩容； grow(int minCapacity)

  3. 扩容的长度计算； int newCapacity = oldCapacity + (oldCapacity >> 1);，旧容量 + 旧容量右移 1 位，这相当于扩容了原来容 量的 (int)3/2 。 4. 10 ，扩容时 1010 + 1010 >> 1 = 1010 + 0101 = 10 + 5 = 15 2. 7 ，扩容时 0111 + 0111 >> 1 = 0111 + 0011 = 7 + 3 = 10

  4. 当扩容完以后，就需要进行把数组中的数据拷贝到新数组中，这个过程会用到 Arrays.copyOf(elementData, newCapacity); newCapacity);，但他的底层用到的 是； System. arraycopy

# 先从 ArrayList 的构造函数说起

（JDK8）ArrayList 有三种方式来初始化，构造方法源码如下：

    private static final int DEFAULT_CAPACITY = 10;


    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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


   
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

细心的同学一定会发现 ：以无参数构造方法创建 **ArrayList** 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10**。** 下面在我们分析 ArrayList 扩容时会讲到这一点内容！

补充：JDK6 new 无参构造的 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组 elementData 。

# 一步一步分析 ArrayList 扩容机制

这里以无参构造函数创建的 ArrayList 为例分析

# 先来看 add 方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

注意 ：JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

# ensureCapacityInternal() 方法

（JDK7）可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

当 要 add 进第 1 个元素时，minCapacity 为 1，在 Math.max()方法比较后，minCapacity 为 10。

此处和后续 JDK8 代码格式化略有不同，核心代码基本一样。

# ensureExplicitCapacity() 方法

如果调用 ensureCapacityInternal() 方法就一定会进入（执行）这个方法，下面我们来研究一下这个方法的源码！

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            
            grow(minCapacity);
    }

我们来仔细分析一下：

  • 当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。

  • 当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。

  • 添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。

直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。

# grow() 方法
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

">>"（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源

我们再来通过例子探究一下**grow()** 方法 ：

  • 当 add 第 1 个元素时，oldCapacity 为 0，经比较后第一个 if 判断成立，newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true,size 增为 1。

  • 当 add 第 11 个元素进入 grow 方法时，newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。

  • 以此类推······

这里补充一点比较重要，但是容易被忽视掉的知识点：

  • java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.

  • java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.

  • java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

# hugeCapacity() 方法。

从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) 
            throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

# System.arraycopy() 和 Arrays.copyOf()方法

阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！

# System.arraycopy()方法

源码：

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

场景：

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  
        
        
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }
# Arrays.copyOf()方法

源码：

    public static int[] copyOf(int[] original, int newLength) {
        
        int[] copy = new int[newLength];
    
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

场景：

    public Object[] toArray() {
    
        return Arrays.copyOf(elementData, size);
    }

个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容。

# 两者联系和区别

联系：

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

区别：

arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

# ArrayList的指定位置插入

首先来看一段代码：

public static void main(String[] args) { 
    List<String> list = new ArrayList<String>(10); 
    list.add(2, "1"); 
    System.out.println(list.get(0)); 
}

这段代码会报错：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 0 
    at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:665) 
    at java.util.ArrayList.add(ArrayList.java:477) 
    at org.itstack.interview.test.ApiTest.main(ApiTest.java:13)

# 源码分析

# 容量验证
public void add(int index, E element) { 
    rangeCheckForAdd(index); 
    ... 
}
private void rangeCheckForAdd(int index) { 
    if (index > size || index < 0) 
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
}

对于在指定位置插入的方法，在插入之前会进行容量验证，就是说将index和size进行判断，如果超出size将报出界异常

通过前面的源码我们知道了之前代码报错的源头了，即只有在每插入一个元素， size 才自增一次 size++ 。而代码中我们只是制定了初始的容量，并没有改变size的值，即size此时还是0，所以报异常了。

# 元素迁移

img

  1. 判断 size ，是否可以插入。

  2. 判断插入后是否需要扩容； ensureCapacityInternal(size + 1); 。

  3. 数据元素迁移，把从待插入位置后的元素，顺序往后迁移。

  4. 给数组的指定位置赋值，也就是把待插入元素插入进来。

# LinkedList

img

# Vector & Stack

  1. Vector 和 Stack 的设计目标是作为线程安全的 List 实现，替代 ArrayList。

    • Vector - Vector 和 ArrayList 类似，也实现了 List 接口。但是， Vector 中的主要方法都是 synchronized 方法，即通过互斥同步方式保证操作的线程安全。

  3. Stack - Stack 也是一个同步容器，它的方法也用 synchronized 进行了同步，它实际上是继承于 Vector 类。

Last Updated: 4/5/2022, 11:45:16 AM

Map