面试宝典:数据结构-ArrayList(下)

简介: 面试宝典:数据结构-ArrayList(下)

image.png


当 要 add 进第1个元素时,minCapacity为(size+1=0+1=)1


在Math.max()方法比较后,minCapacity 为10


然后紧接着调用ensureExplicitCapacity更新modCount的值


并判断是否需要扩容


image.png


oldCapacity为旧数组的容量


newCapacity为新数组的容量(oldCap+oldCap/2:即更新为旧容量的1.5倍)


检查新容量的大小是否小于最小需要容量,如果小于那就将最小容量置为数组的新容量


如果新容量大于MAX_ARRAY_SIZE,使用hugeCapacity比较二者


hugeCapacity逻辑:


对minCapacity和MAX_ARRAY_SIZE进行比较


若minCapacity大,将Integer.MAX_VALUE作为新数组的大小


若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小


MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8


add方法执行流程总结


image.png


  • 这是第一次调用add方法的过程,当扩容值capacity为10之后,


  • 继续添加第2个元素(先注意调用ensureCapacityInternal方法传递的参数为size+1=1+1=2)



  • 在ensureCapacityInternal方法中,elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA不成立,所以直接执行ensureExplicitCapacity方法


  • ensureExplicitCapacity方法中minCapacity为刚刚传递的2,所以第二个if判断(2-10=-8)不会成立,即newCapacity 不比 MAX_ARRAY_SIZE大,则不会进入 grow 方法。数组容量为10,add方法中 return true,size增为1。


  • 假设又添加3、4......10个元素(其中过程类似,但是不会执行grow扩容方法)


  • 当add第11个元素时候,会进入grow方法时,计算newCapacity为15,比minCapacity(为10+1=11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中return true,size增为11


add(int index,E element)方法


image.png


add(int index, E element)方法(在元素序列指定位置(假设该位置合理)插入)的过程大概是下面这些


  • 检测数组是否有足够的空间(这里的实现和上面的)
  • 将 index 及其之后的所有元素向后移一位
  • 将新元素插入至 index 处.
  • 将新元素插入至序列指定位置,需要先将该位置及其之后的元素都向后移动一位,为新元素腾出位置。这个操作的时间复杂度为O(N),频繁移动元素可能会导致效率问题,特别是集合中元素数量较多时
  • 在日常开发中,若非所需,我们应当尽量避免在大集合中调用第二个插入方法


ArrayList的remove方法


remove(int index) 按照下标删除


image.png


image.png


image.png


nteger.MAX_VALUE - 8


主要是考虑到不同的JVM,有的JVM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会去比较最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。这个是从jdk1.7开始才有的


参考资料


https://www.cnblogs.com/lcj12121/p/11710065.html


相关文章
|
2月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
2月前
|
存储 Java 索引
【Java集合类面试二十四】、ArrayList和LinkedList有什么区别?
ArrayList基于动态数组实现,支持快速随机访问;LinkedList基于双向链表实现,插入和删除操作更高效,但占用更多内存。
|
16天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表(Arraylist)
Java集合框架主要由接口、实现类及迭代器组成,包括Collection和Map两大类。Collection涵盖List(有序、可重复)、Set(无序、不可重复),Map则由键值对构成。集合通过接口定义基本操作,具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复,Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现,各有适用场景。其中ArrayList实现了动态数组功能,可根据需求自动调整大小。
28 11
|
3月前
|
存储 安全 Java
面试官没想到一个ArrayList,我都能跟他扯半小时
面试官:List集合都知道哪些对象?作为四大集合之一的List,在业务开发中我们比较常见的是以下 3 种:ArrayList、Vector、LinkedList,业务开发我们接触最多就是容器类库了,容器类库可以说是面向对象语言最重要的类库。大家看看在工作里你比较熟悉的是哪个?这篇文章南哥打算专注于List集合,后面四大集合之Map、Queue、Set后续再来填坑,比心心♥。
126 2
面试官没想到一个ArrayList,我都能跟他扯半小时
|
2月前
|
存储 SQL 搜索推荐
一天十道Java面试题----第一天(面向对象-------》ArrayList和LinkedList)
这篇文章是关于Java面试的笔记,涵盖了面向对象、JDK/JRE/JVM的区别、`==`和`equals`、`final`关键字、`String`、`StringBuffer`和`StringBuilder`的区别、重载与重写、接口与抽象类、`List`与`Set`、`hashcode`与`equals`以及`ArrayList`和`LinkedList`的对比等十个主题。
|
3月前
|
存储 安全 Java
Android面试题之ArrayList源码详解
ArrayList是Java中基于数组实现的列表,提供O(1)的索引访问,但插入和删除操作平均时间复杂度为O(n)。默认容量为10,当需要时会通过System.arraycopy扩容。允许存储null,非线程安全。面试常问:List是接口,ArrayList是其实现之一,推荐使用List接口编程以实现更好的灵活性。更多详情见[ArrayList源码](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList.Node)。
26 2
|
3月前
|
设计模式 并行计算 安全
Java面试题: 如何使用装饰器模式来增强ConcurrentHashMap的功能?在什么情况下应该使用CopyOnWriteArrayList而不是ArrayList?
Java面试题: 如何使用装饰器模式来增强ConcurrentHashMap的功能?在什么情况下应该使用CopyOnWriteArrayList而不是ArrayList?
27 0
|
4月前
|
存储 安全 Java
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
32 0
|
4月前
|
Java Android开发 Kotlin
Android面试题:App性能优化之Java和Kotlin常见的数据结构
Java数据结构摘要:ArrayList基于数组,适合查找和修改;LinkedList适合插入删除;HashMap1.8后用数组+链表/红黑树,初始化时预估容量可避免扩容。SparseArray优化查找,ArrayMap减少冲突。 Kotlin优化摘要:Kotlin的List用`listOf/mutableListOf`,Map用`mapOf/mutableMapOf`,支持操作符重载和扩展函数。序列提供懒加载,解构用于遍历Map,扩展函数默认参数增强灵活性。
42 0
|
2月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。