当前位置：首页 > news >正文

针对面试-java集合篇

news 2025/5/25 19:59:08

1.什么是数组

数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

2.数组下标为什么从0开始

寻址公式是:baseAddress+i*dataTy@eSize，计算下标的内存地址效率较高

3.查找的时间复杂度

随机(通过下标)查询的时间复杂度是O(1)

查找元素(未知下标)的时间复杂度是O(n)

查找元素(未知下标但排序)通过二分查找的时间复杂度是O(logn)

4.插入和删除时间复杂度

需要挪动数组元素，平均插入和删除的时候，为了保证数组的内存连续性，时间复杂度为O(n)

5.ArrayList底层的实现原理是什么

ArrayList底层是用动态的数组实现的

ArrayList初始容量为0,当第一次添加数据的时候才会初始化容量为10

ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组

ArrayList在添加数据的时候:
1. 确保数组已使用长度(size)加1之后足够存下下一个数据
2.计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容(原来的1.5倍)

3.确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。

4.返回添加成功布尔值。

6.如何实现数组和List之间的转换

6.1 数组转List ，使用JDK中java.util.Arrays工具类的asList方法

6.2 List转数组，使用List的toArray方法。无参toArray方法返回Object数组，传入初始化长度的数组对象，返回该对象数组

7. 用Arrays.asList转List后，如果修改了数组内容，list受影响吗List用toArray转数组后，如果修改了List内容，数组受影响吗

7.1 Arrays.asList转换list之后，如果修改了数组的内容，list会受影响因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址（数组转list会发生改变）
7.2 list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响（list转数组不会发生改变）

8.ArrayList 和 LinkedList 的区别是什么?

1.底层数据结构
ArrayList 是动态数组的数据结构实现LinkedList 是双向链表的数据结构实现

2.操作数据效率
2.1 ArrayList按照下标査询的时间复杂度O(1)【内存是连续的，根据寻址公式】， LinkedList不支持下标

2.2查询查找(未知索引): ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)

2.3新增和删除
ArrayList尾部插入和删除，时间复杂度是O(1);其他部分增删需要挪动数组，时间复杂度是O(n)

LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)

3.内存空间占用
ArrayList底层是数组，内存连续，节省内存LinkedList 是双向链表需要存储数据，和两个指针，更占用内存

4.线程安全
ArrayList和LinkedList都不是线程安全的如果需要保证线程安全，有两种方案
4.1 在方法内使用，局部变量则是线程安全的

4.2 使用线程安全的ArrayList和LinkedList

9.说-下HashMap的实现原理?

底层使用hash表数据结构，即数组+(链表红黑树)

添加数据时，计算key的值确定元素在数组中的下标

        key相同则替换
        不同则存入链表或红黑树中
        获取数据通过key的hash计算数组下标获取元素

10.HashMap的jdk1.7和jdk1.8有什么区别

JDK1.8之前采用的拉链法，数组+链表
JDK1.8之后采用数组+链表+红黑树，链表长度大于8目数组长度大于64则会从链表转化为红黑树

11.HashMap的put方法的具体流程

1.判断键值对数组table是否为空或为nul，否则执行resize()进行扩容(初始化)
2.根据键值key计算hash值得到数组索引
3.判断table[i]==nul，条件成立，直接新建节点添加
4.如果table[i]==null ,不成立
4.1 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
否是红黑树，如果是红黑树，则直接在树中插入键值对

4.2 判断table[i] 是否为treeNode，即table[i]

4.3 遍历table[]，链表的尾部插入数据，然后半断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在直接覆盖value
5.插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold(数组长度*0.75)，如果超过，进行扩容

12.讲-讲HashMap的扩容机制

1. 在添加元素或初始化的时候需要调用resize方法送行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值(数组长度*0.75)
2. 每次扩容的时候，都是扩容之前容量的2倍

3. 扩容之后，会新创建一个数组，需要把老数组中数据挪动到新的数组中
3.1没有hash冲突的节点，则直接使用 e.hash &(new(ap-1)计算新数组的索引位置
3.2如果是红黑树，走红黑树的添加
3.3如果是链表，则需要遍历链表，可能需要拆分判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动链表到原始位置+增加的数组大小这个位置上