Java后端开发面试题——集合篇
ArrayList底层的实现原理是什么
底层数据结构
ArrayList底层是用动态的数组实现的
初始容量
ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
扩容逻辑
ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
添加逻辑
确保数组已使用长度（size）加1之后足够存下下一个数据.
计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）
确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
返回添加成功布尔值。
ArrayList list=new ArrayList(10)中的list扩容几次
该语句只是声明和实例了一个 ArrayList，指定了容量为 10，未扩容
如何实现数组和List之间的转换
数组转List
String[] strs = {"aaa","bbb","ccc"};
List<String> list = Arrays.asList(strs);List转数组
List<String> list = new ArrayList<String>();list.add("aaa");list.add("bbb");list.add("ccc");String[] array = list.toArray(new String[list.size()]);用Arrays.asList转List后，如果修改了数组内容，list受影响吗
修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址
List用toArray转数组后，如果修改了List内容，数组受影响吗
修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响
ArrayList 和 LinkedList 的区别是什么？
底层数据结构
ArrayList 是动态数组的数据结构实现
LinkedList 是双向链表的数据结构实现
操作数据效率
查找时间复杂度都是O(n)
新增和删除时间复杂度是O(n)
内存空间占用
ArrayList底层是数组，内存连续，节省内存
LinkedList 是双向链表需要存储数据，和两个指针，更占用内存
线程安全
都不是线程安全的
在方法内使用，局部变量则是线程安全的
使用线程安全的ArrayList和LinkedList
List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());
二叉搜索树
在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值,没有键值相等的节点
红黑树
一种自平衡的二叉搜索树(BST)
性质1：节点要么是红色,要么是黑色
性质2：根节点是黑色
性质3：叶子节点都是黑色的空节点
性质4：红黑树中红色节点的子节点都是黑色
性质5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质
散列表（Hash Table）
是根据键（Key）直接访问在内存存储位置值（Value）的数据结构,利用了数组支持按照下标进行随机访问数据的特性
散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标。
如果key1==key2，那么经过hash后得到的哈希值也必相同即：hash(key1) == hash(key2）
如果key1 != key2，那么经过hash后得到的哈希值也必不相同即：hash(key1) != hash(key2)
散列冲突
不同的key计算得到的散列值都不同几乎是不可能的
链表法（拉链）
所有散列值相同的元素我们都放到相同槽位对应的链表中,链表法中的链表如果是红黑树（可以防止DDos攻击）
HashMap实现原理
底层使用hash表数据结构，即数组和链表或红黑树
当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时，如果出现hash值相同的key，此时有两种情况
a. 如果key相同，则覆盖原始值；
b. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中
获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
链表的长度大于8 且 数组长度大于64 转换为红黑树（减少搜索时间）
红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表
jdk1.7采用的是拉链法 链表和数组相结合
HashMap的put方法的具体流程
HashMap是懒惰加载，在创建对象时并没有初始化数组
在无参的构造函数中，设置了默认的加载因子是0.75
讲一讲HashMap的扩容机制
hashMap的寻址算法
计算对象的 hashCode()
再进行调用 hash() 方法进行二次哈希， hashcode值右移16位再异或运算，让哈希分布更为均匀
最后 (capacity – 1) & hash 得到索引
hashmap在1.7情况下的多线程死循环问题
尾插法