Java集合面试题

什么是数组？

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

• 查找的时间复杂度：

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

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

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

• 插入和删除时间复杂度：

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

数组下标为什么从0开始？

寻址公式是：baseAddress+i*data_typeSize，计算下标的内存地址效率较高

数组与集合区别？

• 数组是固定长度的数据结构，一旦创建长度就无法改变，而集合是动态长度的数据结构，可以根据需要动态增加或减少元素。

• 数组可以包含基本数据类型和对象，而集合只能包含对象。

• 数组可以直接访问元素，而集合需要通过迭代器或其他方法访问元素。

说说Java中的集合？

List：存储的元素是有序的、可重复的。常用的实现List的类有ArrayList，LinkedList，Vector，Stack。

(1) ArrayList底层实现原理

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

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

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

(2) LinkedList本质是一个双向链表，与ArrayList相比，其插入和删除速度更快，但随机访问速度更慢。

(3) Vector底层使用Object[] 存储，线程安全

1. LinkedList

2. HashMap：基于哈希表的Map实现，存储键值对，通过键快速查找值。

3. HashSet：基于HashMap实现的Set集合，用于存储唯一元素。

4. TreeMap：基于红黑树实现的有序Map集合，可以按照键的顺序进行排序。

5. LinkedHashMap：基于哈希表和双向链表实现的Map集合，保持插入顺序或访问顺序。

ArrayList底层的实现原理是什么

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

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

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

• ArrayList在添加数据的时候：

1.确保数组已使用长度(size)加1之后足够存下下一个数据

2.计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容(原来的1.5倍)

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

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

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

• 用ArrayList转List后，如果修改了数组内容，list受影响吗

ArrayList转List之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

• List用toArray转数组后，如果修改了List内容，数组受影响吗

list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响

ArrayList和LinkedList的区别是什么？

1. 底层数据结构

ArrayList是动态数组的数据结构实现

LinkedList是双向链表的数据结构实现

2. 操作数据效率

• ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】，LinkedList不支持下标查询

• 查找（未知索引）：ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)

• 新增和删除：

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

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

3. 内存空间占用

• ArrayList底层是数组，内存连续，节省内存

• LinkedList是双向链表需要存储数据，和两个指针，更占用内存

4. 线程安全

• ArrayList和LinkedList都不是线程安全的

• 如果需要保证线程安全，有两种方案：

在方法内使用，局部变量则是线程安全的

使用线程安全的ArrayList和LinkedList

List<>Object> syncArrayList = Collections.synchronizedList(newArrayList<>());

List<>Object> syncLinkedList = Collections.synchronizedList(newLinkedList<>());