前言
我们在面试时候，数据集合肯定是必不可少的一个内容，要想代码写得好，不应该把瓶子使用的精妙
小知识
1.1、时间复杂度on、o1、o（log n）区别
- o1 只需要查询一次就能找到元素，例如get(index)下标查询
- on 需要从头查到尾，时间不知道多久，例如根据元素查询的链表Map
- o（log n） 范围性以此类推查询，缩短时间，红黑树、二叉树
数组和链表区别
- 数组：保证数据有序、可以基于下标查询，时间复杂度O1，删除需要移动下标。
- 链表：有单向链表和双向链表区别，可以基于下标查询但是时间复杂度On，增删只需要改变指针引向
一、ArrayList集合源码分析
1.2、底层原理
采用数组形式实现
1.3、扩容
add()：扩容因子是1.5倍
1.4、缩容
remove()：将目标元素后面的所有元素向前移动1个位置，时间复杂度为on
1.5、时间复杂度
时间复杂度On
1.6、优缺点
查询快，新增删除慢
1.7、ArrayList和Vector
- 相同：都是数组实现的，默认初始容量为10
- 不同：
- Vector线程安全，ArrayList线程不安全
- Vector扩容2倍，ArrayList扩容1.5倍
二、Vector集合
2.1、数据结构
数组结构
2.2、时间复杂度
O1
2.3、扩容
原来2倍
2.4、安全
线程安全
三、、LinkedList集合源码分析
3.1、原理
基于双向链表结构
四、HashMap集合源码
详情见源码分析那一章节面试题
4.1、HashMap是否允许key重复
不允许，比较hash值相等并且equal不等
4.2、只有扩容，没有缩容
五、HashSet集合源码分析
5.1、底层原理
基于HashMap实现，key为HashSet存放的元素 value值空的object对象
5.2、为什么是无序的
因为HashMap遍历key就是无序的
5.3、底层数据结构模型是什么
数组+链表+红黑树