针对面试-java集合篇

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，该元素的位置要么停留在原始位置，要么移动链表到原始位置+增加的数组大小这个位置上

13.hashMap的寻址算法

计算对象的 hashCode()
再进行调用 hash()方法进行二次哈希， hashcode值右移16位再异或运算，让哈希分布更为均匀
最后(capacity（数组长度）-1)& hash 得到索引

14.为何HashMap的数组长度一定是2的次幂?

计算索引时效率更高:如果是2的n次幂可以使用位与运算代替取模

扩容时重新计算索引效率更高:hash & oldCap ==0的元素留在原来位置，否则新位置=旧位置+oldCap

15.hashmap在1.7情况下的多线程死循环问题

在jdk1.7的hashmap中在数组进行扩容的时候，因链表是头插法，在进行数据迁移的过程中，有可能导致死循环
比如说，现在有两个线程
线程一:读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入

线程二:也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。

线程一:继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环,当然，JDK8将扩容算法做了调整，不再将元素加入链表头(而是保持与扩容前一样的顺序)，尾插法，就避免了idk7中死循环的问题。