1.集合概述

• Java 集合是什么

  Java 集合，也叫做容器，主要由两大接口派生：Collection 接口，主要用于存放单个元素，另一个是 Map 接口，主要存放键值对

• List、Set、Queue、Map 四者的区别

  • List：存储的元素是有序、可重复的
  • Set：存储的元素是无序、不可重复的
  • Map：使用键值对来存储，键是无序、不可重复的，值不做要求

• 集合框架底层数据结构

  • List
    • ArrayList：Object[] 数组
    • Vector：Object[] 数组
    • LinkedList：双向链表
  • Set
    • HashSet：基于 HashMap 实现，底层采用 HashMap 来保存元素
    • LinkedHashSet：是 HashSet 的子类，底层是通过 LinkedHashMap 来实现的
    • TreeSet：基于红黑树
  • Queue
    • ArrayQueue：Object[] 数组 + 双指针
  • Map
    • HashMap：JDK 1.8 前由数组+链表组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突。JDK 1.8 后，当链表长度大于 8 时，将链表转化为红黑树，减少搜索时间【链表转红黑树的时候会判断，当前数组长度小于 64，那么会选择进行数组扩容，而不是转换为红黑树】
    • LinkedHashMap：LinkedHashMap 继承自 HashMap，底层同样是数组+链表或红黑树组成，但在这个结构的基础上，增加了双向链表，可以保持键值对的插入顺序
    • Hashtable：数组 + 链表组成，数组是 Hashtable 的主体，链表主要是为了解决哈希冲突
    • TreeMap：基于红黑树实现

• 如何选用集合？

  根据每个集合的特点来选择合适的集合，比如【需要存放键值对的时候，使用 Map 接口下的集合，需要排序则是 TreeMap，不需要则 HashMap】【存放的是单个元素时，选择 Collection 接口下的集合，元素可以重复选择 List，可以不重复则选择 Set】

2.List

• ArrayList 和数组的区别？

  • ArrayList 内部基于动态数组实现，比静态数组更加灵活
  • ArrayList 创建时不需要指定大小，并且会根据存储的元素动态的扩大或缩小，而数组创建时必须指定大小，并且数组创建后不能改变它的长度
  • ArrayList 允许使用泛型确保类型，数组不可以
  • ArrayList 只能存储对象，对于基本类型也需要使用对应的包装类。数组两者都可以存储

• ArrayList 可以添加 null 值么

  ArrayList 可以存储任何类型的对象，包括 null，但不建议，因为没有意义，反而有什么忘记做判断空时，会导致空指针异常

• ArrayList 插入和删除元素的时间复杂度？

  • 插入
    • 头部插入：将所有元素都向后移动一个位置，时间复杂度是 O(n)
    • 尾部插入：如果 ArryList 的长度没达到极限，末尾插入元素的时间复杂度是 O(1)【因为只需要在数组末尾添加一个元素就可以了】。当长度达到极限需要扩容的时候，需要执行一次 O(n) 的操作将原数组复制到扩容后新的数组中，然后在执行 O(1) 的操作添加元素
    • 指定位置插入：将目标位置之后的元素都向后移动一个位置，然后再吧新元素放入指定位置。这个操作需要移动平均 n/2 个元素，时间复杂度为 O(n)
  • 删除
    • 头部删除：将所有元素一次向前移动一个位置，时间复杂度为 O(n)
    • 尾部删除：直接进行尾部删除，时间复杂度为 O(1)
    • 指定位置删除：将不妙位置之后的元素都向前移动一个位置，这个操作需要移动平均 n/2 个元素，时间复杂度为 O(n)

• ArrayList 与 LinkedList 区别？

  • ArrayList 和 LinkedList 都是不同步的，不保证线程的安全
  • ArrayList 底层使用的是 Object 数组，LinkedList 底层使用的是双向链表数据结构
  • ArrayList 采用数组存储，插入和删除元素的时间复杂度受元素位置的影响【比如执行 add() 方法的时候，ArrayList 会吧元素追加到末尾，时间复杂度为 O(1)，而如果要指定位置上进行删除和插入，需要前移或后移一位，时间复杂度为 O(n)】。LinkedList 采用链表存储，因为存在 addFirst、addLast、removeFirst、removeLast，所以在头尾插入或删除不受元素位置影响，时间复杂度为 O(1)。如果要指定位置，需要先移动到指定位置再插入和删除，时间复杂度为 O(n)
  • ArrayList 的空间浪费体现在 list 列表的结尾会预留一定的容量空间，而 LinkedList 体现在每一个元素都要消耗比 ArrayList 更多的空间

• ArrayList 扩容机制

  以无参数构造方法创建 ArrayList 的时候，实际上初始化赋值的是一个空数组，当真正对数组进行添加元素的时候，才会分配容量，数组容量扩为 10。有参构造函数创建，传入带初始容量参数，那分配的数组容量就是传入的实参数。传入一个集合，那么就会将这个集合转为数组，作为初始数组【如果转为数组不是 Object 类型的，会重新拷贝这个数组将类型改为 Object】。ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（因为扩容新数组的长度是 旧数组长度 + 就数组长度/2，偶数则1.5倍，基数会丢掉小数部分）

3.Set

• Comparable 和 Comparator 的区别

  • Comparable 接口是 java.long 包中的，通过 compareTo(Object obj) 方法用来排序
  • Comparator 接口是 java.util 包中的，通过 compare(Object obj1,Object obj2) 方法用来排序

  一般需要对一个集合使用自定义排序的时候，就要重写 compareTo() 或者 compare() 方法。如果需要同时实现两种排序方式，比如分别对员工的年龄和入职日期来排序，可以重写 compareTo() 和 自制的 Comparator中的排序方法，也可以使用两个 Comparator 自制排序

• 无序性和不可重复性的含义是什么

  • 无序性：指存储的数据在底层数组中不是按照数组索引顺序排列的，而是根据数据的哈希值决定
  • 不可重复性：指的是添加的元素进行 equals() 判断的时候返回 false。需要同时重写 equals() 和 hashCode() 方法

• HashSet、LinkedHashet、TreeSet 三者的异同

  • HashSet、LinkedHashet、TreeSet都是 Set 接口的实现类，都能保证元素唯一，并且线程都是非安全的
  • 三者的主要区别在于底层数据结构不同，HashSet 的底层数据结构是哈希表（基于 HashMap 实现），LinkedHashSet 的底层数据接口是链表和哈希表，TreeSet 底层数据结构是红黑树
  • 三者的应用场景不同，需要有序使用 LinkedHashSet，需要自定义排序使用 TreeSet，其它使用 HashSet

4.Map

• HashMap 和 Hashtable 的区别

  • HashMap 线程是非安全的，Hashtable 线程是安全的。因为 hashtable 内部的方法基本都进行了同步锁
  • 因为线程安全的问题，HashMap 要比 hashtable 效率更高【hashtable 基本已经被淘汰了】
  • HashMap 可以键值都可以存 null，但 null 作为键只能由一个，值作为 null 可以有多个。Hashtable 键值都不可以为 null，否则会抛出空指针
  • 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充都是原来的 2n+1。Hash 默认的初始大小为 16，之后每次扩充为都是原来的 2 倍。创建时如果指定了容量初始值，Hashtable 会直接使用给定的大小，而 HashMap 会将其扩充 2 的次方大小
  • JDK 1.8 后的 HashMap 当链表长度大于 8 的时候，将链表转为红黑树（转红黑树前判断，数组长度小于 64 则会先进行数组扩容，不是转为红黑树），以减少搜索时间

• HashMap 和 HashSet 区别

  • HashSet 的底层就是基于 HashMap 实现的
  • HashMap 实现接口是 Map，HashSet 实现接口是 Set
  • HashMap 存储的是键值对，HashSet 存储的是单个元素对象
  • HashMap 使用键来计算 hashcode，HashSet 使用对象计算 hashcode

• HashMap 和 TreeMap 的区别

  HashMap 和 TreeMap 都继承自 AbstractMap，TreeMap 比 HashMap 多了对集合中的元素根据键排序的能力【继承NavigableMap】和对集合内元素的搜索能力【继承SortedMap】

• HashMap 的底层实现

  • JDK 1.8 之前

  底层是数组和链表结合在一起使用，HashMap 通过 key 的 hashcode 值，再通过 hashcode 判断当前元素存放的位置，如果存在元素，判断该元素与要存入的元素 hashcode 值以及 key 是否相同，相同则直接覆盖，不相同就通过拉链法解决冲突【拉链法就是将链表和数组相结合，也就是说创建一个链表数组，数组中每一个都是一个链表，若遇到哈希冲突，则将冲突的值加入链表中】

  • JDK 1.8 之后

  在解决哈希冲突有所裱花，当链表长度大于 8 （转红黑树前会判断，如果数组长度小于 64，则会先进行数组扩容，而不是转红黑树）时，将链表转化为红黑树，以减少搜索时间

• HashMap 多线程操作导致死循环的问题

  JDK 1.7 之前是由于当有多个元素需要进行扩容的时候，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。JDK 1.8 为解决这个问题，次啊用了尾插法来避免链表倒置，使得插入的节点永远都是存放在链表的末尾，避免了链表中的环形结构【但不建议在多线程情况使用 HashMap，因为还是会存在数据覆盖的问题，并发环境下使用 ConcurrentHashMap】

• HashMap 为什么线程不安全？

  比如：两个线程 1，2，同时进行 put 操作，并且发生了哈希冲突。不同线程可能在不同的时间获得 CPU 执行的机会，当线程 1 执行完哈希冲突判断后，由于时间耗尽挂起，线程 2 先完成了插入操作。随后线程 1 获得执行时间，由于之前已经进行过了 hash 碰撞的判断，所以此时会直接插入，这就导致了线程 2 插入的数据被线程 1 覆盖了

• HashMap 的遍历方式有哪些？

  • 使用迭代器 EntrySet 和 KeySet 的方式进行遍历
  • 使用 For Each EntrySet 和 keySet 的方式遍历
  • 使用 Lambda 表达式进行遍历
  • 使用 Streams API 的方式进行遍历