集合

1.为什么数组索引从0开始呢?假如从1开始不行吗?

数组的索引从0开始相对于从1开始性能更高;
因为在获取元素的时候,"内存地址"="数组的首地址"+"索引" * "数据类型的大小"；
假设内存地址为n,数组的首地址为a,索引为b,数据类型大小为c,那么寻址公式就是n=a+b*c；
如果数组的索引从0开始,索引就刚好对应b这个变量,而如果是从1开始,b就等于索引-1，这样就需要加一次减法操作，对于CPU而言就多了一次指令，所以数组索引从0开始相对于从1开始性能更高。

2.操作数组的时间复杂度(查找)

分三种情况:

● 第一种是知道下标,可以直接通过索引访问,所以时间复杂度为O(1);

● 第二种是不知道下标,且数组没有排序,就需要遍历数组,所以时间复杂度为O(n);

● 第三种是不知道下标,但是数组排序了,可以使用二分查找,时间复杂度为O(log n)。

3.操作数组的时间复杂度(插入、删除)

分两种情况:

● 第一种是操作中间的元素,不管是插入还是删除,都需要后面的元素往后或者往前移一位,所以时间复杂度为O(n);

● 第二种是操作最后一位元素,可以直接插入或删除,所以时间复杂度为O(1);

● 所以最好的情况下是O(1),最坏的情况是O(n),平均情况下是O(n)。

4.List相关

(1).如何实现数组和List之间的转换

● 数组转List可以使用JDK中Java.util.Arrays工具类的asList方法

● List转数组,可以使用List的toArray方法。不传参数可以返回Object数组，传入初始化长度的数组对象可以返回对象数组。

(2).用Arrays.asList转换List之后，如果修改了数组内容，list受影响吗？

● 会受影响；因为他的底层使用的是Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装，最终指向的是同一个内存地址。

(3).List用toArray转数组后，如果修改了List内容，数组受影响吗？

● 不受影响；因为调用toArray以后，在底层它是进行了数组的拷贝，所以不受影响。

5.ArrayList和LinkedList的区别是什么?(高频)

数据结构:

● 底层的数据结构不一样,ArrayList是动态数组实现的,而LinkedList是双向链表实现的

查询:

● ArrayList按照下标查询的时间复杂度是O(1),而LinkedList不支持下标查询;

● 不知道下标的情况下ArrayList需要遍历,LinkedList也需要遍历,所以时间复杂度都是O(n);

新增和删除:

● ArrayList尾部插入和删除的时间复杂度是O(1),其它部分删除需要挪动数组,时间复杂度是O(n);

● 而LinkedList头和尾结点增删的时间复杂度是O(1),其它需要遍历,时间复杂度是O(n);

内存空间占用:

● ArrayList底层是数组,内存是连续的,更节省内存;

● 而LinkedList是双向链表,需要存储数据和两个指针,更占用内存;

线程安全:

● 这俩线程都是不安全的;

● 如果需要保证线程安全,有两种方案:

1.在方法内使用,局部变量是线程安全的;

2.使用线程安全的ArrayList和LinkedList,但这样性能差相对差。

6.HashMap相关

(1).HashMap的实现原理(高频)

● HashMap底层使用hash表数据结构，就是数组和链表或者红黑树；

● 在存储的时候，如果出现hash值相同的key，会有两种情况：

1.key相同，会覆盖原来的值；

2.key不相同，会把当前的key-value放入链表或红黑树里。

● 拿的时候，会直接找到Hash值对应的下标，通过判断key是否相同来找到对应的值。

(2).HashMap的JDK1.7和JDK1.8有什么区别？(高频)

● JDK1.8之前用的是拉链法，就是将数组和链表结合，没有使用红黑树；

● JDK1.8之后不仅用了数组和链表，还有红黑树，当链表长度大于8而且数组长度达到64的时候，会把链表转化为红黑树，减少搜索时间。在扩容resize（）的时候，如果红黑树的结点数小于等于临界值6个，就会退化成链表。

(3).HashMap的put方法的具体流程(高频)

● JDK1.8之前用的是拉链法，就是将数组和链表结合，没有使用红黑树；

6.3HashMap的put方法的具体流程(高频)

● 在执行put方法的时候，首先会判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）

● 是就会根据键值key计算hash值得到数组索引

判断table[i]==null，条件成立，直接新建节点添加
如果table[i]==null ,不成立

● 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value

● 不相同则判断table[i] 是否为红黑树，如果是红黑树，就会直接在树中插入键值对

● 如果不是红黑树就遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在直接覆盖value

● 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容。

HashMap的扩容机制？

● 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）每次扩容的时候，都是扩容之前容量的2倍；扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中，没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置如果是红黑树，走红黑树的添加，如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

hashMap的寻址算法？

● 这个哈希方法首先计算出key的hashCode值，然后通过这个hash值右移16位后的二进制进行按位异或运算得到最后的hash值。在putValue的方法中，计算数组下标的时候使用hash值与数组长度取模得到存储数据下标的位置，hashmap为了性能更好，并没有直接采用取模的方式，而是使用了数组长度-1 得到一个值，用这个值按位与运算hash值，最终得到数组的位置

(4).HashMap的扩容机制

● 在添加元素或者是初始化的时候会调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次扩容都是达到了数组长度的0.75倍才会扩容；

● 每次扩容的时候，都是扩容之前容量的2倍；

● 扩容之后，会创建一个数组，需要把老数组中的数据挪动道新的数组中，有三种情况

1.没有hash冲突的结点，会直接使用e.hash & (newCap - 1)计算数组的索引位置

2.如果是红黑树，走红黑树的添加

3.如果是链表，需要遍历链表，可能需要拆分链表，判断（e.hash & oldCap）是否为0，这个元素要么停留在原始位置，要么移动到原始位置 + 增加的数组大小这个位置上。

(5).为什么HashMap的数组长度一定是2的次幂？

● 这样计算索引效率更高，因为如果是2的n次幂可以用位与运算代替取模；

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

(6).HashMap在1.7情况下的多线程死循环问题

● 在jdk1.7的hashmap中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

● 比如说，现在有两个线程

线程一:读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入

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

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

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

集合

集合