【2021Java后端面试题整理】Java集合框架

Java集合

1.List、Set、Map的区别

• List： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象（顺序可重）
• Set: 不允许重复的集合。不会有多个元素引用相同的对象。（乱序不可重复）
• Map: 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。（key-value键值对）

2.Arraylist 与 LinkedList 区别?

线程安全上来说：Arraylist 与 LinkedList都是不同步的，不能保证线程安全

从底层实现数据结构来说：Arraylist 底层使用的是Object数组， LinkedList使用的是双向链表

增删是否受到元素位置的影响：Arraylist 底层是数组，如果增删操作，需要将操作位置数的前后所有节点都移动，而 LinkedList 增删操作很快，但是需要移动到需要增删操作的位置需要O（n）的复杂度

是否支持快速访问：LinkedList底层是双向链表，而 ArrayList 支持。快速随机访问就是通过元素下标快速获取元素对象(对应于get(int index)方法)。

内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

3.ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist。

4.ArrayList的扩容机制

ArrayList的初始化有三中方式：

1.ArrayList list = new ArrayList();

空参构造，初始默认容量设置为10

2.ArrayList list = new ArrayList(n);

初始容量设置为n，开一个容量为n的ArrayList

3.ArrayList list = new ArrayList(Collection);

将collection 的内容深拷贝到新集合中

ArrayList新建的时候,默认空间是10,之后如果add到元素上线,就会出发grow()方法,扩容为原来的1.5呗,在进行深拷贝

使用add()方法后，将元素加入到集合中，如果达到容量上限后，触发grow()方法，将容量变成原来的1.5倍以后，再进行添加

5.HashMap 和 Hashtable 的区别

线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

6.HashMap 和 HashSet区别

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

public HashSet() {
    map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

接口实现：HashMap实现Map接口；HashSet实现了Set接口

存储方式：HashMap存储方式是K,V；HashSet仅仅存储对象

添加元素方法：HashMap使用put方法将k,v；HashSet使用add方法，就是调用HashMap的put方法

比较相等：HashMap对key进行hashcode值的计算；HashSet使用放入的对象的hashcode值计算，因为底层就是调用hashmap的计算方式，而放入的对象是放在key的位置，value是final常量

7. HashSet如何检查重复

HashSet底层就是调用HashMap，首先会将放入的对象计算他的hashcode值，如果对象的hashcode相等，那么再比较里面具体的值是否相等，使用equals()方法进行比较。底层都是使用HashMap()方法

8.HashMap的底层实现

JDK1.8 之前HashMap底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

简而言之，就是将数据挂载到对应 (n - 1) & hash 的位置，如果该位置有数据了，判断对应的hashcode值是否一致，如果一致，则覆盖，如果不一致，则挂载在链表下

jdk8以后，当某个位置的挂载结点数量超过阈值后（8个），会转换成红黑树。（用红黑树是为了解决二叉查找树的弊端，极端情况下会呈现线性结构）

9.HashMap 的长度为什么是2的幂次方（不太明白位运算）

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

10.HashMap 多线程操作导致死循环问题

主要原因在于 并发下的Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

11.ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：

图片来源：http://www.cnblogs.com/chengxiao/p/6842045.html

12.ConcurrentHashMap线程安全的具体实现方式/底层具体实现

JDK1.7（上面有示意图）
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

JDK1.8 （上面有示意图）
ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

13.Comparable 和 Comparator的区别

都是两个用来比较的接口

Comparable接口要实现的方法是compareTo(Object obj)方法

Comparator接口要实现的方法是compare(Object obj1,Object obj2)方法

在应用来上说，通常我们都是在集合中使用排序，Comparable通常是对象来继承，然后重写compareTo方法，将对象按一定顺序进行排序，如果方法返回<0的数，那么前排；如果>0，就往后排。而Comparator一般是用于定制排序，用于各种集合的sort方法，使用匿名内部类来实现一个new Comparator的compare方法，如果返回o1-o2,则按从小到大排列，o2-o1则是逆序

14.请你说说Iterator和ListIterator的区别？

Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。

Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。ListIterator实现了Iterator接口，并包含其他的功能：增加元素，替换元素，获取前一个和后一个元素的索引

15.集合框架底层数据结构总结

Collection

1. List

• Arraylist： Object数组
• Vector： Object数组
• LinkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)

2. Set

• HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
• LinkedHashSet： LinkedHashSet 继承于 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
• TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树)

Map

• HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap： 红黑树（自平衡的排序二叉树）

16.如何选用集合

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用Map接口下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时，就选择实现Collection接口的集合，需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet，不需要就选择实现List接口的比如ArrayList或LinkedList，然后再根据实现这些接口的集合的特点来选用。

17.重写equals方法需同时重写hashCode方法

关于HashMap的源码分析就介绍到这儿了，最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题

/**
 * Created by chengxiao on 2016/11/15.
 */
public class MyTest {
    private static class Person{
        int idCard;
        String name;

        public Person(int idCard, String name) {
            this.idCard = idCard;
            this.name = name;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()){
                return false;
            }
            Person person = (Person) o;
            //两个对象是否等值，通过idCard来确定
            return this.idCard == person.idCard;
        }

    }
    public static void main(String []args){
        HashMap<Person,String> map = new HashMap<Person, String>();
        Person person = new Person(1234,"乔峰");
        //put到hashmap中去
        map.put(person,"天龙八部");
        //get取出，从逻辑上讲应该能输出“天龙八部”
        System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
    }
}

实际输出结果：

结果：null

如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）

所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

18.HashMap红黑树退化成链表的条件

1.remove时退化

// 在 removeTreeNode的方法中
// 在红黑树的root节点为空 或者root的右节点、root的左节点、root左节点的左节点为空时 说明树都比较小了
if (root == null || (movable && (root.right == null || (rl = root.left) == null|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}

2.在扩容时 low、high 两个TreeNode 长度小于6时 会退化为链表。

19.HashMap的扰动函数是什么?为什么要用扰动函数

扰动函数就是求得hash值以后,高十六位和低十六位进行异或操作得到hash值以后再和len-1进行与运算

扰动函数保留了高十六位和第十六位的特征,混合原本hash码的高位和地位,加大低位的随机性,让数据更加均匀

20.你知道CopyOnWriteArrayList吗?

既然你说到，ArrayList非线程安全，会出现并发修改异常，基于fast-fail机制，那么GUC也提供了一个并发的这样的类去解决问题。

CopyOnWriteArrayList是采用读写分离的思想，读操作不加锁，写操作加独占锁，其他线程都进入阻塞状态，这样肯定是不好的

于是他的原理就是在写操作的时候，不直接写到当前容器，而是将当前容器复制一份，添加到复制的容器中，这时候还是可以进行读操作，等复制完以后再将旧的指针指向新的容器

但这样也存在一定的缺陷。这时候会抛出来一个新的问题，也就是数据不一致的问题。如果写线程还没来得及写会内存，其他的线程就会读到了脏数据。

这就是CopyOnWriteArrayList 的思想和原理。就是拷贝一份写。所以使用条件也很局限，那就是在读多写少的情况下比较好。