Java教程

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

本文主要是介绍高薪程序员&面试题精讲系列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总结

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

2. 原因分析(略)

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

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

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