学习一下Java的ArrayList和contains函数和扩容机制

起因

在Leetcode上做题写了两种暴力解法，但是执行效率上不太一样。

时间上差很远，内存虽然差不多但是前者击败30%，后者击败94%。这两种解法区别是用一条ArrayList还是两条来存数据，所以contains虽然执行次数一样但是检测的长度上不一样，而且ArrayList的扩容次数也不一样，所以学习一下。
contains(Object o)

直接翻(JDK8)源码:

null和object区分开来还是因为equals有一方是null的话都会导致异常. 合并一起写的话可以用Objects.equals(obj1, obj2)的写法.
所以显然暴力解法用到的contains的原理就是朴实无华的一遍遍搜索所以时间特别长.
ArrayList扩容机制

省流: 直接看最下面的grow函数.
如果是默认的ArrayList, 添加元素时会先计算数组长度, 如果元素个数+1大于当前数组长度+1大于elementData.length时进行扩容，扩容后的数组大小是: oldCapacity + (oldCapacity >> 1) ，位运算右移1位表示除以2, 所以可以理解成1.5倍扩容。
涉及到的源码:

1. // 向指定索引位置插入元素
2. public void add(int index, E element) {
3.     // 检查索引范围
4.     rangeCheckForAdd(index);
6.     // 确保容量足够
7.     ensureCapacityInternal(size + 1);  // 增加 modCount（用于支持并发修改的计数器）
8.     // 使用 System.arraycopy 将元素后移，为新元素腾出位置, 这是跟另一个add的区别⭐⭐⭐⭐⭐
9.     System.arraycopy(elementData, index, elementData, index + 1, size - index);
10.     elementData[index] = element; // 在指定位置插入新元素
11.     size++; // 更新列表大小
12. }
14. // 在列表末尾添加元素
15. public boolean add(E e) {
16.     // 确保容量足够
17.     ensureCapacityInternal(size + 1);  // 增加 modCount
18.     elementData[size++] = e; // 在列表末尾添加新元素
19.     return true;
20. }
22. // 内部方法：确保容量足够
23. private void ensureCapacityInternal(int minCapacity) {
24.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
25. }
27. // 内部方法：计算容量
28. private static int calculateCapacity(Object[] elementData, int minCapacity) {
29.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
30.         // 如果内部数组为空，返回默认容量或所需容量中的较大者
31.         return Math.max(DEFAULT_CAPACITY, minCapacity);
32.     }
33.     return minCapacity; // 否则返回所需容量
34. }
36. // 内部方法：确保容量足够
37. private void ensureExplicitCapacity(int minCapacity) {
38.     modCount++; // 增加并发修改计数器
40.     // 检查容量是否足够，如果不够则扩展
41.     if (minCapacity - elementData.length > 0)
42.         grow(minCapacity);
43. }
45. // 内部方法：扩展容量
46. private void grow(int minCapacity) {
47.     // 溢出安全的代码
48.     int oldCapacity = elementData.length;
49.     int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量通常为旧容量的1.5倍
50.     if (newCapacity - minCapacity < 0)
51.         newCapacity = minCapacity; // 如果新容量小于所需容量，使用所需容量
52.     if (newCapacity - MAX_ARRAY_SIZE > 0)
53.         newCapacity = hugeCapacity(minCapacity); // 处理可能的巨大容量情况
54.     // 使用 Arrays.copyOf 扩展数组容量
55.     elementData = Arrays.copyOf(elementData, newCapacity);
56. }

复制代码

实际上Array.copyof底层调用的还是System.arraycopy.

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！