面试题-Java集合（新更新版本）

前言

Java集合部分的题目，是我根据Java Guide的面试突击版本V3.0再整理出来的，其中，我选择了一些比较重要的问题，并重新做出相应回答，希望对大家起到一定的帮助。

Java集合

说说Arraylist 与 LinkedList 区别?
- 底层数据结构：ArrayList是数组，LinkedList是链表，那么问题就变成了数组和链表这两种数据结构的区别
- 增删、查的平均时间复杂度：
  - 插入和删除（注意，这里的插入和删除并不包括查找，仅仅看操作本身的时间复杂度。另外，下面讨论的前提是需要维护数组有序。）
    - 数组如果插（删除）在尾部，这种情况是最优时间复杂度，为O(1)，如果插（删除）在头部，这种情况是最差时间复杂度，为O(N)；平均时间复杂度为 (1+2+3+...n)n/2 = O(N)。
      - 注意：如果数组是无序的，完全可以把待插入数据和插入位置的数据交换一下，实现O(1)的时间复杂度。
    - 链表插入（删除）的时间复杂度，最好最差和平均都是O(1)
  - 查找
    - 数组根据下标的随机查找，最好最坏平均都是O(1)
    - 链表根据下标的随机查找，最好是O(1)，最坏是O(N)，平均为O(N)
      - JAVA实现中优化了链表根据下标查找的过程，先判断待查找的索引下标是在前半段还是后半段，如果在前半段，就从头开始查；如果在后半段，就从尾开始查。
    - 数组和链表，根据值查找，都需要遍历，时间复杂度都为O(N)
- 空间复杂度：
  - 链表需要额外存储指针数据，数组不需要，但是JAVA实现中会冗余一些数组位置，也增加了空间复杂度。
说⼀说 ArrayList 的扩容机制
- 扩容原理：ArrayList的add方法，在真正add之前，会检查是否需要扩容，扩容的关键就是确定新的数组长度，java源码中是按照原始长度的1.5倍来确定新长度的。具体的拷贝过程，就是建立一个新的长度的数组，把原始数组中的数据拷贝到新数组中
- 最佳实践：在已知需要加入list中的元素个数时，可以调用ensureCapacity方法来提前扩容到指定的大小，避免添加的过程中不断扩容，提高性能
HashMap和Hashtable的区别？
- 线程安全性和性能：HashTable使用synchronized加锁，线程安全，但是性能较差
- Nullkey和NullValue的支持：HashTable中key和value都不能为null，如果为空，直接抛出空指针异常；HashMap中支持为null的key，也支持为null的value
HashMap和HashSet的区别？
- HashSet底层用的就是HashMap实现的，key存储实际的对象，value存储一个默认的Object
说一说HashMap的底层数据结构
- JDK1.8之前，HashMap的底层数据结构是数组+链表
- JDK1.8之后，Java优化了HashMap的链表部分，当链表达到默认阈值8时，会转变为红黑树，提高搜索效率，等值查询的平均时间复杂度从链表的O(N)变为红黑树的O(logN)
HashMap的扩容机制
- 和ArrayList类似，初始都是一个空的数组，当实际添加数据时，会初始化一个默认长度为16的数组
- 负载因子：HashMap的扩容依据是当当前容器中的键值对个数大于数组长度×负载因子=负载个数时，进行扩容，扩容为之前长度的2倍。
HashMap的长度为什么是2的幂次方
- hash值是int类型的，默认有很大的范围，但是数组又不可能那么大，所以需要按照数组的实际大小取模
- 位运算的效率高于取模的效率，所以要尽可能转化为位运算。
  - 当长度为2的幂次方时，h%length取模的操作可以转化为h&（length-1）
HashMap 多线程操作导致死循环问题

这个问题的关键就是在rehash的过程中，多线程导致环形链表。HashMap本身就是线程不安全的，多线程的情况下应该使用ConcurrentHashMap。
ConcurrentHashMap 和 Hashtable 的区别?

这两个数据结构主要区别就在于实现线程安全的方式不同。
- 在jdk1.7的时候，concurrentHashMap底层使用的是分段锁的概念，和HashTable比提高了并发度
- 在jdk1.8之后，摒弃了分段锁的概念，使用synchronized加CAS来实现线程安全，synchronized只锁当前链表或者红黑树的头节点，效率和分段锁比又大大提升。
comparable 和 Comparator的区别?
- comparable提供一个compareTo方法，代表了该类可以被比较
- comparator是一个比较器，方法参数是两个对象，实现两个对象的比较