【Java】20211016_Java集合_ArrayList

从简单数据结构谈起

数组

懂得都懂(doge)

ArrayList的底层结构

ArrayList的底层结构是数组（见代码块1-1），首先看ArrayList的初始化构造方法。

[^代码块1-1]

transient Object[] elementData;

ArrayList提供了三种构造方法（见代码块1-2）

[^代码块1-2]

private static final Object[] EMPTY_ELEMENTDATA = {};
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) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}    

1. ArrayList的无参构造，将其底层数组赋值为一个空数组。
2. ArrayList的int型参数构造，传入参数initialCapacity作为底层数组的初始化长度，判断初始化长度小于0则抛出异常，等于0则将底层数组赋值为一个空数组，大于0则以初始化长度动态初始化一个数组。
3. ArrayList的Collection型参数构造——略。

长度可变揭秘

无论使用哪种构造方式，一个确定的数组经过初始化后，其长度是不会发生改变的，所以我们需要看看ArrayList提供的add方法来探究ArrayList集合长度可变的秘密（见代码块1-3）

[^代码块1-3]

private int size;
public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private void grow(int minCapacity) {
   // overflow-conscious code
   int oldCapacity = elementData.length;
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   if (newCapacity - minCapacity < 0)
       newCapacity = minCapacity;
   if (newCapacity - MAX_ARRAY_SIZE > 0)
       newCapacity = hugeCapacity(minCapacity);
   // minCapacity is usually close to size, so this is a win:
   elementData = Arrays.copyOf(elementData, newCapacity);
}

以一个通过无参刚初始化的空集合为例：

1. ensureCapacityInternal方法——再次确定集合容量。由于刚初始化，此时size为0，ensureCapacityInternal方法实际接收的参数minCapacity为1，在ensureCapacityInternal方法内部调用了calculateCapacity方法。
2. calculateCapacity方法——计算集合容量。由于在使用无参构造初始化时
   elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，所以这个方法直接会返回minCapacity（1）和DEFAULT_CAPACITY（10）中的最大值即10。
3. ensureExplicitCapacity方法——明确添加元素后的集合容量。在ensureExplicitCapacity方法中，传入的minCapacity是上一步的返回结果10，modCount++后modCount为1，接着在判断条件中，显然(10-0)>0为true，所以下一步要走grow方法。
4. grow方法——扩容方法。
   // 获取旧容量值
   int oldCapacity = elementData.length;
   // 计算新容量值，oldCapacity >> 1 <==> oldCapacity / 2，所以新容量为旧容量的1.5倍大
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   紧接着是对新容量值做最终判断，如果newCapacity （这里为0）小于传入的minCapacity（这里是10），那么新容量值就取传入的minCapacity，否则就和MAX_ARRAY_SIZE比较，这里的MAX_ARRAY_SIZE非常大，一般不会为true（如果实际工作中你能让扩容走到这一步，联系我我给你发五毛钱安家费），接着就会通过Arrays工具类的copy方法将原来elementData数组中的数据拷贝到一个新的数组中并将新数组地址赋值给elementData完成集合扩容。
5. 走完上述方法后，执行elementData[size++] = e;才正式将想要添加的元素e添加到集合中。

走完整个扩容方法，可以知道：

1. 集合扩容的时机——如果一个集合原有长度是10，直到放置第11个元素才会扩容，即在添加超过集合容量的第一个元素时在add方法内部扩容。
2. 扩容后的容量——原容量的1.5倍。

面试题

（其实14号美团面试没有问ArrayList扩容，我也没答，但还是写了这个md文档，主要是ArrayList的扩容机制和HashMap存在不一样的地方，所以要做个记录，以防下次被问到）

正题：List.contains(Object obe)方法是怎么实现的?

内心os：这还要想？你要确定一个集合里有没有这个元素，直接遍历然后去做比较呗？

想是这么想，答也是这么答的，ArrayList在实现上也确实是这么个思路。看看码（见代码块2-1）：

[^代码块2-1]

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

直接看indexOf方法，indexOf方法分别谈论了o是否为null的两种情况，因为o为null在调用o.equals()时会报空指针异常。

1. 如果o是null，就遍历集合通过==来判断集合中是否有null这个特殊元素。
2. 如果o不是null，就遍历集合通过equals来判断集合中是否存在和o相同的元素。

null在Java中是特殊的，地址值固定的，所以可以通过==来判断，但是对于其他对象，应该调用可以被重写的对象o的equals方法来判断。（其实contains方法我还是回答对了的）

说到equals方法，上一篇写了下面的代码（见代码块2-2）：

[^代码块2-2]

Integer a = 1000;
Integer b = 1000;
System.out.println(a == b);

上面的代码最终输出结果为false，实际上在对两个包装类进行比较时应该用equals方法，阿里巴巴代码规约里已经告诉我们了。

努力让自己不那么菜

欲速则不达，每天进步一点点。

(有没有成都的大佬内推我一波)