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情况下的多线程死循环问题

尾插法