经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
学习一下Java的ArrayList和contains函数和扩容机制
来源:cnblogs  作者:芜光  时间:2023/10/25 19:46:59  对本文有异议

起因

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

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

contains(Object o)

直接翻(JDK8)源码:
image
nullobject区分开来还是因为equals有一方是null的话都会导致异常. 合并一起写的话可以用Objects.equals(obj1, obj2)的写法.
所以显然暴力解法用到的contains原理就是朴实无华的一遍遍搜索所以时间特别长.

ArrayList扩容机制

省流: 直接看最下面的grow函数.

如果是默认的ArrayList, 添加元素时会先计算数组长度, 如果元素个数+1大于当前数组长度+1大于elementData.length时进行扩容,扩容后的数组大小是: oldCapacity + (oldCapacity >> 1) 可以理解成1.5倍扩容。

涉及到的源码:

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

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

原文链接:https://www.cnblogs.com/joey-redfield/p/17787980.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号