高薪程序员&面试题精讲系列35之List、Set、Map对空值处理策略的底层原因探究？

2021/12/10 9:17:02

编程Tag： 面试题源码 value Map Set key null hashmap add

本文主要是介绍高薪程序员&面试题精讲系列35之List、Set、Map对空值处理策略的底层原因探究？，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一. 面试题及剖析

1. 今日面试题

List中为什么可以存null？

Map中对null是怎么处理的？

HashMap的key、value可以为null吗？为什么？

ConcurrentHashMap中的key、value可以为空吗？为什么？

Set中可以有空值吗？为什么？

Set不重复是基于什么原理？

.......

2. 题目剖析

在上一篇文章中，壹哥其实已经通过代码实验，给大家展示了不同集合对null值的处理，如果你认真的学习了我的上一篇文章，现在应该知道哪些集合可以存null，哪些集合不可以存null。但我们现在还不知道这些集合为什么会这样处理，即有的集合可以存null，有的集合就不可以存null，这是为什么呢？所以本文壹哥会承接上文，给大家继续探究其底层原因。上一篇文章链接如下所示：

高薪程序员&面试题精讲系列34之List、Set、Map可不可以存空值？

二. 底层原因

上文壹哥通过几个案例，已经明确的告诉了大家List、Set、Map中到底能不能存null，以及可以存几个null，这个结论我希望大家都能牢牢记住，以后出去面试直接把这个结论甩面试官脸上就OK了。但是此时就怕面试官又多嘴多舌的来一句，为啥List中可以存多个null？为啥有的Set和Map子类不能存null？

那么本着知其然还要知其所以然的精神，壹哥这里再带大家深究一下之所以会有上面这些结论的底层原因，让大家弄明白其中的原理，这样无论这个面试官有多刁难，我们也不惧他。

老规矩，壹哥还是针对三种集合，分别来探究其底层原因。

1. List对null车里策略探究

壹哥先带大家来探究一下，为什么List的这3个子类，都可以存null，并且可以想存几个null就存几个null。为了弄明白这个问题，我觉得没有比查看ArrayList、LinkedList、Vector这3个子类源码更好的办法了，所以我们分别看一下这几个类对null处理相关的源码。那么源码那么多，到底在哪里处理的null呢？其实稍微一想就能知道，我们要把null作为数据元素添加到集合中，肯定要从 “添加” 操作入手，所以对于null的处理策略，我们去相应的add、put、set等方法中去找就可以了。

1.1 ArrayList的add()源码

我们先来看看ArrayList中add()方法的源码是怎么定义的，源码如下：

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

其实你会发现，ArrayList中add()方法的源码其实很简单，方法体内部总共就3行代码。首先add()方法的注释上已经说明了，ArrayList#add()用于把指定的元素添加到List集合的最后面，那么是添加到哪个地方的最后面呢？壹哥在上一篇文章中就给大家分析过ArrayList的源码，我们知道ArrayList内部其实是一个Object[]动态数组，数组名称是elementData[]，这是一个用于存储数据的缓冲数组，我们添加到List中的每一个数据都会先添加到这个elementData数组中。

所以从add()方法的源码中我们可以看到，add(E e)方法的泛型参数e，会按照数组的索引顺序，直接添加到elementData数组的最后位置。也就是说，第一个e会添加到数组的第1个位置上，第2个e会添加到数组的第2个位置上，以此类推。但是我们没有发现ArrayList对这个e本身做出任何的检查和限制，也就是不管这个e是什么类型，什么内容，都会一股脑的挨个排到elementData数组后面。

所以这也就是ArrayList为什么可以存null，且可以存多个null的原因，就是因为其底层对数据类型和内容没有做任何的限制啊。只要是Object的子类，你爱存什么就存什么，爱存几个就存几个，只要elementData数组足够大，你往里使劲存就好咯。

1.2 LinkedList的add()源码

接下来我们再来看看LinkedList#add()方法的源码吧。

    /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

	/**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

	//Node节点源码
	private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
		
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

我们会发现LinkedList#add()的源码也很简单。LinkedList#add()执行时，也是把E元素添加到List集合的最后面，不同的是LinkedList采用的数据结构不是数组，而是一个双向链表，这块内容我之前就给大家讲过了。所以这里每次添加一个新的E元素，就会把该E元素封装成Node节点，把e封装到Node节点的item属性中。

但是在这个过程中，你会发现，LinkedList同样对数据E的类型和数量没有做任何的检查和限制！每次添加一个元素E，这个新的E就会 “缀在“ 原先的最后一个节点后面，从而自己就成了最后的节点，再来一个E元素，就再这么搞一下，以此类推。所以同样的，我们想在LinkedList中存几个null都行！

1.3 Vector的add()源码

最后我们看看Vector#add()的源码。

    /**
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

这里我们基本就不同分析啦，你会发现其内部的处理策略，与ArrayList#add()的处理策略是一模一样的。唯一不同的地方在于Vector#add()方法带有synchronized同步，这里和null值的处理策略没关系，我们就不再说了，前文有介绍。

2. Map对null处理策略探究(重点)

2.1 HashMap的put()源码

我们先来看看HashMap#put()方法的源码，这么看起来并不是很复杂，但实际很复杂。这里我只对key为null时的情况做简要分析，后面会专门给大家讲解HashMap的源码和原理，所以要长期关注壹哥哦。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//对key进行hash运算
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对HashMap的底层原理，我先不做特别详细的讲解，后面我还会单独讲解HashMap的原理。这里我们先知道，Java 8之后，HashMap内部有3种数据结构用来保存数据，即数组+链表+红黑树。

其内部对key-value键值对的处理是这样的。如果某个key-value键值对和别的节点有冲突，则用链表或者红黑树来解决冲突。但如果某个key-value键值对不和别的节点有冲突，一般就是把该key-value存储到数组中，但并不是像List那样按先来后到的顺序将key-value存到这个数组中，而是要对key进行hash计算。

所以在上面的这段源码中，putVal()方法会进行存值之前，先调用hash(key)方法对key进行hash运算，计算key的hash值，最终确定这个key的存储位置。所以hash(key)方法是一个很重要的方法，它对key进行了判断和计算，这里我对hash(key)方法进行必要的解释：

①. 如果key等于null，这个就很好办了，直接把key的hash值分配为0。
②. 如果key不等于null，则分2步进行操作：先是通过h=key.hashCode()得到key的hash值h，然后再将h和h>>>16进行异或高位运算，最终得到一个int类型的hash值。

得到了这个int类型的hash值之后，把该hash值与 table的length-1 进行与运算，会得到一个table数组的索引值，也就是靠(n-1)&hash这句话来完成的。这个索引值，就是我们某个key-value键值对存储在Map 数组中的位置。具体处理策略看下图：

所以通过对上面这段源码的分析可知，HashMap中的key可以为null，但只能有一个key为null。如果key为null，则这个key对应的hash值就直接为0；如果此时还有第二个key也是null，那么它的hash值也是0。这样这两个key-value键值对就会存到同一个位置上，这就是产生了冲突。那么这时候，HashMap内部会对这个冲突进行处理，处理方案要么就是用新键值对覆盖原有的键值对，要么就是采用链表或红黑树来进行处理。因为我们这里两个key都是null，两个key的hash也必然都是0，根据源码中的判断可知，新的key-value键值对会直接覆盖掉原有的key-value键值对！所以，我们可以往HashMap中存储为null的key，但不管存几个null，最终也只能有一个空key存在，后面的把前面的给覆盖掉了！

这样我们就知道了，HashMap中的key可以为null，但只能有一个！另外HashMap对value并没有任何限制，你爱存什么存什么，存null也无所谓，存100个null也无所谓，没有对value进行非空限制嘛对不对，所以HashMap中可以存多个null的value。

2.2 LinkedHashMap的put()源码

接下来我们再来看看LinkedHashMap，先看看LinkedHashMap与HashMap的关系，如下图所示：

你会发现，原来LinkedHashMap是HashMap的亲儿子啊!

那我们再看看LinkedHashMap的构造方法源码，如下图所示：

我们发现，LinkedHashMap的默认构造方法内部很简单，第一句话就是我们很熟悉的super关键字！也就是说，当我们调用new LinkedHashMap()语句的时候，实际上就相当于在new HashMap()啊！这完完全全就是亲儿子了！

而且，LinkedHashMap自身根本就没有实现put()方法，完全就是继承自它老子的put()方法，所以LinkedHashMap对key-value的null值处理策略是完全一样的！

2.3 TreeMap的put()源码

接着我们看TreeMap#put()方法的源码。我这里直接对源码进行了截图，如下图所示：

在截图上我们可以明确看到一个注释信息，”如果TreeMap指定的key为null，则直接抛出空指针异常“，那么在哪里抛的空指针异常呢？请看下面的源码。

因为这个方法的源码很长，很多与本面试题的中心思想没有关系，所以我把一些非必要的代码略去了，只保留了最关键的源代码，如下所示。

    public V put(K key, V value) {
        ......
        if (cpr != null) {
           ......
        }
        else {
            if (key == null)
                throw new NullPointerException();
             ......
        }
        ......
        return null;
    }

所以根据源码可知，如果TreeMap的key为null，对不起！TreeMap直接不陪你玩了，直接甩了你一脸空指针异常！

那么TreeMap中的value能不能为空呢？我们还是看这个put()方法的源码，如下图所示：

由上图可知，TreeMap中可以存储空value，而且存几个空value都可以！

2.4 Hashtable的put()源码

现在轮到我们看Hashtable#put()方法的源码啦，有点小激动哎，看看吧。这里我直接贴图了，方便为大家画出重点！

我们会发现，Hashtable这家伙挺狠呢！上来就对value做了非空检查，如果为空，直接扔我们一脸空指针异常！看来Hashtable中value是不能为空了！

那接着看看key吧！

其实我们会发现，Hashtable中对可以的处理，与HashMap对key的处理有点类似，也是先获取key的hash值！但是，重点来啦！你仔细看看，Hashtable与HashMap对key的判断实际上是不一样的，我们上面有HashMap对可以的判断源码，还能想起来吗？如果想不起来，可以往上翻刚才我对HashMap的源码讲解，或者看下图：

我们发现，HashMap对key是做了非空判断的，如果key为null，hash值为0，否则才执行key.hashCode()方法，所以HashMap中的可以即使等于null，也不会产生空指针异常！

但是，Hashtable就不一样了！在上面Hashtable的源码截图中，我给大家对key的hash值计算部分做了重点标记，你会看到，Hashtable没有判断key是否等于空，就直接执行key.hashCode()方法了！！！这有什么隐患呢请问？如果key此时等于null，你去执行key.hashCode()方法，这不是空指针了吗？所以，Hashtable中的key，也不能为空！

2.5 ConurrentHashMap的put()源码

再然后，我们来看看名字非常长的一个Map---ConcurrentHashMap，看看它的put()方法中对key和value是怎么处理的。铛铛珰，源码来啦，如下图所示：

你会看到，ConcurrentHashMap的put()方法，对key和value的处理，简直就是直接又粗暴，上来就是进行了非空判断，谁为null，就直接抛空指针异常！

这就对了嘛，上面的几个Map中，对key和value整的也太复杂啦，直接进来做个非空判断不香吗？整那一堆虚头巴脑的干哈呀。

3. Set对null处理策略探究

接下来我们看看Set的源码中对null是怎么处理的。这里我们先明确一点，Set只有value，没有key哦！

3.1 HashSet的add()方法源码

那就先看看HashSet的源码吧。先看看HashSet的构造方法，如下图所示：

哎？什么鬼？HashSet的构造方法中，进入给我们new 了一个HashMap？！！！

闹了半天，原来HashSet就是在HashMap的外面套了个壳子，感情我们本质上还是在操作HashMap啊！

那既然如此，看看这个所谓的add()方法内部啥样吧，如下图所示：

果不其然，HashSet的add()方法，内部就是在调用HashMap的put()方法，而且本来在HashSet中作为value的e，到了put()方法中竟然成了key！所以我们就知道了，HashSet中的元素是不可能重复的！因为HashMap的key就不可能重复啊！HashMap内部会对key进行hash计算，且会进行判断，如果两个key一样，hash值也一样，后面的节点就直接覆盖了前面的节点了！

关于HashMap的key前面已经做了详细说明，如果你想不明白，请自行回过头去看。

3.2 LinkedHashSet的add()方法源码

接下来我们看看LinkedHashSet的源码吧。先看看类关系，原来LinkedHashSet竟然是HashSet的亲儿子啊，好像前面我们说过LinkedHashMap是HashMap的亲儿子对吧。

而且当我们构造LinkedHashSet对象的时候，实际是利用的super关键字进行对象创建的。

那既然这样，还有什么好说的呢，所以LinkedHashSet#add()方法的源码，与上面说的HashSet一样，内部也是利用的HashMap对key的处理策略。

3.1 TreeSet的add()方法源码

最后，我们怀着激动忐忑的心情，来看看TreeSet#add()方法的源码吧，最后一个咯，好开心啊！

我们进入TreeSet的构造方法中，可以看到如下图所示的源码：

这是会发现，TreeSet的内部是构造了一个TreeMap对象！so，你明白了吧？当我们调用TreeSet的add()方法的时候，实际是把value传递给了TreeMap中，这个value其实会作为TreeMap的key来存在。我们知道，TreeMap的key是不能为null的，否则直接空指针异常。所以TreeSet的value也是不能为空的哦！

三. 结语

至此，壹哥就给各位讲清楚了List、Set、Map中到底能不能存null，以及可以存几个null，还有这其中的底层原理，相信你应该会有所收获了。最后壹哥再对今天的内容进行简单总结梳理。

1. List、Set、Map中能不能存null总结

List的子类ArrayList、LinkedList、Vector中可以存储多个null；
HashSet、LinkedHashSet中可以存储一个null，TreeSet中不能存储null，否则会产生空指针异常；
HashMap、LinkedHashMap中的key与value均可以是null，但只能有一个key是null，可以有多个value是null；
TreeMap的key不可以为null，否则会产生空指针异常，而value可以为null；
Hashtable、ConurrentHashMap中的key与value都不能是null，否则会产生空指针异常。

2. 原因分析(略)

各种结合能不能存null的原因，壹哥已经非常详细的给大家讲解了，我觉得全网没有比壹哥讲的更细的了，希望你可以记住，具体原因请参考上面的源码分析部分。

现在你知道，为什么有的集合可以存null，甚至多个null，而有的集合却不能存null了吧？码字创作不易，请给壹哥来个三连吧！

这篇关于高薪程序员&面试题精讲系列35之List、Set、Map对空值处理策略的底层原因探究？的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！