Java面试之集合那些事

1.ArrayDeque和LinkedList的区别

• 联系：两者都继承了Deque接口，都可以做队列的功能。
• 区别：ArrayDeque底层是数组+双指针实现的，会存在扩容 *** 作，不可以存null值，性能较LinkedList高。
  LinkedList是基于链表实现的，每次插入数据都要申请空间，耗时高。

2.PriorityQueue基于什么数据结构实现的？

• 亲身经历的腾讯云面试题目。
• 基于二叉堆实现的，可以对某个关键字进行排序。应用：数组中第k大的数。

3.集合接口中概念的理解

• 有序的：是指数据在集合中的排列是按照插入顺序排列的，比如：List，Queue，Deque。
• 无序的：是指数据在集合中顺序和插入顺序不一样，Set、HashMap.
• 排好序的：是指数据按照某个特定的规则排好顺序的（比如按照大小排好顺序），比如：Set、PriorityQueue。

4.HashTable和HashMap的区别

• HashTable是线程安全的，是由Synchronized关键字来实现的，初始容量为11，扩容变成2n+1。HashMap是线程不安全的，HashMap效率要比HashTable要高，初始容量为16，扩容为2的n次幂的大小，底层数据结构也不一样，HashMap在jik8的时候发生很大变化。

5.HashSet如何重复

• 现根据HashCode判断是否相同，若相同的话，还需要调用equals方法进行判断，若相同则代表对象相同，若不相同则表示两对象不相同。

6.谈一谈HashMap

• 在jdk1.7的时候，HashMap是由数组+链表组成，处理冲突采用拉链法，插入链表采用头插法，可能会在多线程的情况下造成环的问题。
• 在jdk1.8时候，HashMap采用数组+链表/红黑树组成，处理冲突采用拉链法，插入链表采用尾插法。当数组的大小大于64，链表的长度超过8的时候，链表会转换成红黑树。

7.HashMap的数组长度为什么是2的次幂？

• 查看源码们就能看到index=hash&(length-1):length是表示数组的长度，hash是表示key经过哈希之后的值。当length-1=2的次幂的时候，hash&(length-1)=hash%(length)，证明如下图所示。尽然可以相等为啥要选择前者呢，因为在计算机中的数据都是以二进制的方式存储的，一切 *** 作都是基于加减和移位来完成的，顾前者效率远远高于后者。
  

8.谈一谈ConcurrentHashMap

• ConcurrentHashMap是线程安全的，在jdk1.7和1.8的实现原理是一样的。
• 在jdk1.7的时候，是基于segement实现的线程安全的，一个ConcurrentHashMap中多个segement，每个segement智能由一个线程访问。
• 在jdk1.8的时候是基于synchronized+CAS来保证线程安全的。

9.集合遍历中的安全失败和快速失败

• 快速失败，就是在遍历的过程中如果对Map进行修改的话，是直接修改在原Map上面的。如下图所示是快速失败。
  
• 安全失败，在遍历的过程中是遍历Map的副本，对原Map进行修改不影响当前遍历的Map副本。如下图所示是安全失败。