起因
在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.5倍扩容。
涉及到的源码:
// 向指定索引位置插入元素public void add(int index, E element) { // 检查索引范围 rangeCheckForAdd(index); // 确保容量足够 ensureCapacityInternal(size + 1); // 增加 modCount(用于支持并发修改的计数器) // 使用 System.arraycopy 将元素后移,为新元素腾出位置, 这是跟另一个add的区别⭐⭐⭐⭐⭐ System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; // 在指定位置插入新元素 size++; // 更新列表大小}// 在列表末尾添加元素public boolean add(E e) { // 确保容量足够 ensureCapacityInternal(size + 1); // 增加 modCount 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) { modCount++; // 增加并发修改计数器 // 检查容量是否足够,如果不够则扩展 if (minCapacity - elementData.length > 0) grow(minCapacity);}// 内部方法:扩展容量private void grow(int minCapacity) { // 溢出安全的代码 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量通常为旧容量的1.5倍 if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); // 处理可能的巨大容量情况 // 使用 Arrays.copyOf 扩展数组容量 elementData = Arrays.copyOf(elementData, newCapacity);}
实际上Array.copyof
底层调用的还是System.arraycopy
.