第2章 Java集合

本章主要介绍Java中集合类！

2.1 说一下List、Set和Map三者的区别？

  • List存储一组不唯一（可以有重复元素）的有序对象。
  • Set存储一组无重复（不可重复）数据的集合。
  • Map使用键值对来存储数据，Key不可重复，Value可重复。

2.2 说一下ArrayList和LinkedList的区别？

  1. 线程安全：两者都是不同步的，所以都是线程不安全的。
  2. 底层实现方式：ArrayList底层采用数组实现，LinkedList底层采用双向链表实现（JDK1.6之前采用循环链表来实现）
  3. 插入和删除是否受元素位置影响：ArrayList底层采用数组实现，所以插入和删除受元素位置影响（执行add()方法时，默认将元素追加到列表末尾，时间复杂度为O(1)。但是当指定插入的位置或者删除某个元素的时候，需要循环遍历数组，时间复杂度为O(n)）。LinkedList的底层采用链表实现，所以插入和删除不受元素位置影响，时间复杂度为O(1)。
  4. 是否支持快速随机访问：ArrayList的get()方法通过索引数组下标可以快速访问，但是LinkedList不支持快速随机访问。
  5. 内存空间占用情况：ArrayList浪费空间体现在：在list列表后面预留若干空间。LinkedList浪费空间体现在：它的每个元素都需要消耗比ArrayList多的空间（需要存放直接后继和直接前驱）。

2.3 ArrayList 与 Vector 区别呢?为什么要⽤Arraylist取代Vector呢？

  • Vector是线程安全的，可以由两个线程安全地访问一个Vector对象，但是当单线程访问Vector对象时，会在同步操作上浪费大量的时间。
  • ArrayList是线程不安全的，在不需要线程安全时建议使用ArrayList节省时间开销。

2.4 说一说 ArrayList 的扩容机制？

  • 扩容时机：当数组的大小大于初始容量的时候(比如默认初始为10，当添加第11个元素的时候)，就会进行扩容，新的容量为旧的容量的1.5倍。
  • 扩容方式：以新的容量创建新的数组，让原来的数组指向新的数组，原数组被抛弃（GC回收）。

2.5 说一下HashMap和Hashtable的区别？

  • 线程是否安全：HashMap是线程不安全的，Hashtable是线程安全的（内部的方法都经过synchronized修饰）。
  • 效率：由于线程安全问题，HashMap的执行效率比Hashtable高（现在几乎不用Hashtable）。
  • 对key = null的支持：HashMap中key可以等于null（这样的键只能有一个）。但是在Hashtable中，如果key等于null，会抛出空指针异常。
  • 初始容量以及扩容：
    • 创建时不指定初始容量
      HashMap的初始容量为16，再次扩容大小为2n；Hashtable的初始容量为11，再次扩容的大小为2n+1。
    • 创建时指定初始容量
      HashMap的初始容量直接扩容大小为2的幂次方大小；Hashtable会直接使用初始容量。
  • 底层数据结构：JDK1.8之后，HashMap在解决哈希冲突上面有了较大变化，当链表大小大于阈值（默认为8）时，将链表转化成红黑树。Hashtable没有此机制。

2.6 说一下HashMap的底层实现？

  • JDK1.8之前：底层是数组+链表（链表散列）结合在一起使用。处理冲突的方法是拉链法（创建一个链表数组，数组中的每一格都是一个链表。若遇到哈希冲突，将冲突的值加入到链表中）。
  • JDK1.8之后：在解决哈希冲突上面有了较大变化，当链表大小大于阈值（默认为8）时，将链表转化成红黑树。

2.7 HashMap的工作原理？

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。

2.8 HashMap中两个对象的hashcode相同会发生什么？

因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

2.9 如果两个键的hashcode相同，你如何获取值对象？

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置。找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

2.10 如果HashMap的大小超过负载因子(load factor)定义的容量，怎么办？

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。

2.11 你了解重新调整HashMap大小存在什么问题吗？

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

2.12 说一下HashMap的长度为什么是2的幂次方？

利用位移运算的效率比直接求余运算效率高。所以数组下标的计算方法是“（n-1）&hash”（底层源码）。当进行位移运算时，如果长度不是2的幂次方很容易出现冲突，所以为了尽量较少碰撞和让数据均匀分布，HashMap的长度取2的幂次方。

2.13 说一下HashMap和HashSet的区别？

HashMap HashSet
实现Map接口 实现Set接口
存储键值对 存储唯一对象
调用put()向map添加元素 调用add ()向set添加元素
HashMap使用键（Key）计算Hashcode HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false

2.14 HashSet如何检查重复的？

首先计算加入对象的hashcode值来判断对象的加入位置，如果存在一个对象的hashcode值和加入的对象的相同，会调用equals()方法来判断两个对象本身是否相同。如果两个对象相同，那么HashSet就不会让操作成功；如果两个对象不同，就会重新散列到其他位置。
拓展：
1.hashCode()作用：获取哈希值，返回一个int整数。哈希值的作用：确定对象在哈希表中的位置。
2.两个对象相同->hashCode相同->equals()方法的返回值相同。
3.两个对象hashCode相同，但是不一定相等。
为什么重写equals的时候，必须重写hashCode方法？
答：hashCode()定义在JDK的Object.java中，任何类都含有hashCode()函数。因此，如果重写equals的时候，必须重写hashCode方法。

2.15 HashMap 多线程操作导致死循环问题？

因为在并发下rehash会造成元素之间形成循环链表，在JDK1.8之后解决了这个问题，但是不建议在多线程下使用HashMap，因为在并发环境下还会出现数据丢失问题。并发环境推荐使用ConcurrentHashMap。

2.16 说一下ConcurrentHashMap和Hashtable的区别？

  • 底层数据结构：

    • ConcurrentHashMap：JDK1.7采用分段的数组+链表实现，JDK1.8采用数组+链表/红黑树实现。
    • Hashtable：一直采用数组+链表，数组是主体，链表只是为了解决哈希冲突。

  • 两者都是线程安全的，但是实现线程安全的方式不同。

    • ConcurrentHashMap（分段锁）：在JDK1.7时，对桶数组进行分段分割，每把锁只锁一部分数据，多线程访问容器内不同的数据段的数据时，不会存在锁竞争，提高并发效率。在JDK1.8时，直接使用数组+链表+红黑树来实现，并发控制使用synchronized和CAS来操作。看起来像优化过的且进程安全的HashMap。

    • Hashtable（全表锁）：使用synchronized保证线程安全，效率低下。当多个线程同时访问同步方法时，有可能进入堵塞或者轮询状态。

2.17 说一下Comparable和Comparator的区别？

  • Comparable接口来自java.lang，Comparator接口来自java.util。
  • Comparable是一个内比较器，支持自己和自己作比较。Comparator是一个外比较器，可以通过重写compare()方法来定制自己想要的比较规则。
    代码如下（示例）： 
Arrays.sort(intervals,new Comparator<int[]>(){
   
    public int compare(int[] a,int[] b){
   
        if(a[0]!=b[0]){
   
            return a[0]-b[0];
        }else{
   
            return a[1]-b[1];
        }
    }
});
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);