再有人问你HashMap,把这篇文章甩给他!

2020-02-11 16:08:01来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

再有人问你HashMap,把这篇文章甩给他!

声明:本文以jdk1.8为主!

搞定HashMap

作为一个Java从业者,面试的时候肯定会被问到过HashMap,因为对于HashMap来说,可以说是Java==集合中的精髓==了,如果你觉得自己对它掌握的还不够好,我想今天这篇文章会非常适合你,至少,看了今天这篇文章,以后不怕面试被问HashMap了

其实在我学习HashMap的过程中,我个人觉得HashMap还是挺复杂的,如果真的想把它搞得明明白白的,没有足够的内力怕是一时半会儿做不到,不过我们总归是在不断的学习,因此真的不必强迫自己把现在遇到的一些知识点全部搞懂。

但是,对于HashMap来说,你所掌握的应该足够可以让你应对面试,所以今天咱们的侧重点就是学会那些经常被问到的知识点。

我猜,你肯定看过不少分析HashMap的文章了,那么你掌握多少了呢?从一个问题开始吧

新的节点在插入链表的时候,是怎么插入的?

怎么样,想要回答这个问题,还是需要你对HashMap有个比较深入的了解的,如果仅仅知道什么key和value的话,那么回答这个问题就比较难了。

这个问题大家可以先想想,后面我会给出解答,下面我们一步步的来看HashMap中几个你必须知道的知识点。

Map是个啥?

HashMap隶属于Java中集合这一块,我们知道集合这块有list,set和map,这里的HashMap就是Map的实现类,那么在Map这个大家族中还有哪些重要角色呢?

上图展示了Map的家族,都是狠角色啊,我们对这些其实都要了解并掌握,这里简单的介绍下这几个狠角色:

TreeMap从名字上就能看出来是与树有关,它是基于树的实现,而HashMap,HashTable和ConcurrentHashMap都是基于hash表的实现,另外这里的HashTable和HashMap在代码实现上,基本上是一样的,还记得之前在讲解ArrayList的时候提到过和Vector的区别嘛?这里他们是很相似的,一般都不怎么用HashTable,会用ConcurrentHashMap来代替,这个也需要好好研究,它比HashTable性能更好,它的锁粒度更小。

由于这不是本文的重点,只做简单说明,后续会发文单独介绍。

简单来说,Map就是一个映射关系的数据集合,就是我们常见的k-v的形式,一个key对应一个value,大致有这样的图示

这只是简单的概念,放到具体的实例当中,比如在HashMap中就会衍生出很多其他的问题,那么HashMap又是个啥?

HashMap是个啥

上面简单提到过,HashMap是基于Hash表的实现,因此,了解了什么是Hash表,那对学习HashMap是相当重要。

建议了解了哈希表之后再学习HashMap,这样很多难懂的也就不那么难理解了。

接着,HashMap是基于hash表的实现,而说到底,它也是用来存储数据供我们使用的,那么底层是用什么来存储数据的呢?可能有人猜到了,还是数组,为啥还是数组?想想之前的ArrayList。

所以,对于HashMap来说,底层也是基于数组实现,只不过这个数组可能和你印象中的数组有些许不同,我们平常整个数组出来,里面会放一些数据,比如基础数据类型或者引用数据类型,数组中的每个元素我们没啥特殊的叫法。

但是在HashMap中人家就有了新名字,我发现这个知识点其实很多人都不太清楚:

在HashMap中的底层数组中,每个元素在jdk1.7及之前叫做Entry,而在jdk1.8之后人家又改名叫做Node。

这里可能还是会有人好奇这Entry和Node长啥样,这个看看源码就比较清楚了,后面我们会说。

到了这里你因该就能简单的理解啥是HashMap了,如果你看过什么是哈希表了,你就会清楚,在HashMap中同样会出现哈希表所描述的那些问题,比如:

  1. 如何确定添加的元素在底层数组的哪个位置?
  2. 怎么扩容?
  3. 出现冲突了怎么处理?
  4. 。。。

没事,这些问题我们后续都会谈到。

HashMap初始化大小是多少

先来看HashMap的基础用法:

HashMap map = new HashMap();
 

就这样,我们创建好了一个HashMap,接下来我们看看new之后发生了什么,看看这个无参构造函数吧

  public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
 

解释下新面孔:

  1. loadFactor : 负载因子,之前聊哈希表的时候说过这个概念
  2. DEFAULT_LOAD_FACTOR : 默认负载因子,看源码知道是0.75

很简单,当你新建一个HashMap的时候,人家就是简单的去初始化一个负载因子,不过我们这里想知道的是底层数组默认是多少嘞,显然我们没有得到我们的答案,我们继续看源码。

在此之前,想一下之前ArrayList的初始化大小,是不是在add的时候才创建默认数组,这里会不会也一样,那我们看看HashMap的添加元素的方法,这里是put

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

 

这里大眼一看,有两个方法;

  1. putVal 重点哦
  2. hash

这里需要再明确下,这是我们往HashMap中添加第一个元素的时候,也就是第一次调用这个put方法,可以猜想,现在数据已经过来了,底层是不是要做存储操作,那肯定要弄个数组出来啊,好,离我们想要的结果越来越近了。

先看这个hash方法:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

记得之前聊哈希表的时候说过,哈希表的数据存储有个很明显的特点,就是根据你的key使用哈希算法计算得出一个下标值,对吧。

而这里的hash就是根据key得到一个hash值,并没有得到下标值哦。

重点要看这个putVal方法,可以看看源码:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

 

咋样,是不是感觉代码一下变多了,我们这里逐步的有重点的来看,先看这个:

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;?

 

这个table是啥?

transient Node<K,V>[] table;
 

看到了,这就是HashMap底层的那个数组,之前说了jdk1.8中数组中的每个元素叫做Node,所以这就是个Node数组。

那么上面那段代码啥意思嘞?其实就是我们第一次往HashMap中添加数据的时候,这个Node数组肯定是null,还没创建嘞,所以这里会去执行resize这个方法。

resize方法的主要作用就是初始化和增加表的大小,说白了就是第一次给你初始化一个Node数组,其他需要扩容的时候给你扩容

看看源码:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
 

感觉代码也是比较多的啊,同样,我们关注重点代码:

newCap = DEFAULT_INITIAL_CAPACITY; 

有这么一个赋值操作,DEFAULT_INITIAL_CAPACITY字面意思理解就是初始化容量啊,是多少呢?

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 

这里是个移位运算,就是16,现在已经确定具体的默认容量是16了,那具体在哪创建默认的Node数组呢?继续往下看源码,有这么一句

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 

ok,到这里我们发现,第一次使用HashMap添加数据的时候底层会创建一个长度为16的默认Node数组。

那么新的问题来了?

为啥初始化大小是16

这个问题想必你在HashMap相关分析文章中也看到过,那么该怎么回答呢?

想搞明白为啥是16不是其他的,那首先要知道为啥HashMap的容量要是2的整数次幂?

为什么容量要是 2 的整数次幂?

先看这个16是怎么来的:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 

这里使用了位运算,为啥不直接16嘞?这里主要是位运算的性能好,为啥位运算性能就好,那是因为位运算人家直接操作内存,不需要进行进制转换,要知道计算机可是以二进制的形式做数据存储啊,知道了吧,那16嘞?为啥是16不是其他的?想要知道为啥是16,我们得从HashMap的数据存放特性来说。

对于HashMap而言,存放的是键值对,所以做数据添加操作的时候会根据你传入的key值做hash运算,从而得到一个下标值,也就是以这个下标值来确定你的这个value值应该存放在底层Node数组的哪个位置。

那么这里一定会出现的问题就是,不同的key会被计算得出同一个位置,那么这样就冲突啦,位置已经被占了,那么怎么办嘞?

首先就是冲突了,我们要想办法看看后来的数据应该放在哪里,就是给它找个新位置,这是常规方法,除此之外,我们是不是也可以聚焦到hash算法这块,就是尽量减少冲突,让得到的下标值能够均匀分布。

好了,以上巴拉巴拉说一些理念,下面我们看看源码中是怎么计算下标值得:

i = (n - 1) & hash

这是在源码中第629行有这么一段,它就是计算我们上面说的下标值的,这里的n就是数组长度,默认的就是16,这个hash就是这里得到的值:

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 

继续看它:

i = (n - 1) & hash

 

这里是做位与运算,接着我们还需要先搞明白一个问题

为什么要进行取模运算以及位运算

要知道,我们最终是根据key通过哈希算法得到下标值,这个是怎么得到的呢?通常做法就是拿到key的hashcode然后与数组的容量做取模运算,为啥要做取模运算呢?

比如这里默认是一个长度为16的Node数组,我们现在要根据传进来的key计算一个下标值出来然后把value放入到正确的位置,想一下,我们用key的hashcode与数组长度做取模运算,得到的下标值是不是一定在数组的长度范围之内,也就是得到的下标值不会出现越界的情况。

要知道取模是怎么回事啊!明白了这点,我们再来看:

i = (n - 1) & hash

这里就是计算下标的,为啥不是取模运算而是位与运算呢?使用位与运算的一方面原因就是它的性能比较好,另外一点就是这里有这么一个等式:

(n - 1) & hash  =  n % hash
 

因此,总结起来就是使用位与运算可以实现和取模运算相同的效果,而且位与运算性能更高!

接着,我们再看一个问题

为什么要减一做位运算

理解了这个问题,我们就快接近为什么容量是2的整数次幂的答案了,根据上面说的,这里的n-1是为了实现与取模运算相同的效果,除此之外还有很重要的原因在里面。

在此之前,我们需要看看什么是位与运算,因为我怕这块知识大家之前不注意忘掉了,而它对理解我们现在所讲的问题很重要,看例子:

比如拿5和3做位与运算,也就是5 & 3 = 1(操作的是二进制),怎么来的呢?

5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101

3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011

1转换为二进制:0000 0000 0000 0000 0000 0000 0000 0001

所以啊,位与运算的操作就是:第一个操作数的的第n位于第二个操作数的第n位如果都是1,那么结果的第n位也为1,否则为0

看懂了吧,不懂得话可以去补补这块的知识,后续我也会单独发文详细说说这块。

我们继续回到之前的问题,为什么做减一操作以及容量为啥是2的整数次幂,为啥嘞?

告诉你个秘密,2的整数次幂减一得到的数非常特殊,有啥特殊嘞,就是2的整数次幂得到的结果的二进制,如果某位上是1的话,那么2的整数次幂减一的结果的二进制,之前为1的后面全是1

啥意思嘞,可能有点绕,我们先看2的整数次幂啊,有2,4,8,16,32等等,我们来看,首先是16的二进制是: 10000 ,接着16减一得15,15的二进制是: 1111 ,再形象一点就是:

16转换为二进制:0000 0000 0000 0000 0000 0000 0001 0000

15转换为二进制:0000 0000 0000 0000 0000 0000 0000 1111

再对照我给你说的秘密,看看懂了不,可以再来个例子:

32转换为二进制:0000 0000 0000 0000 0000 0000 0010 0000

31转换为二进制:0000 0000 0000 0000 0000 0000 0001 1111

这会总该懂了吧,然后我们再看计算下标的公式:

(n - 1) & hash  =  n % hash
 

n是容量,它是2的整数次幂,然后与得到的hash值做位于运算,因为n是2的整数次幂,减一之后的二进制最后几位都是1,再根据位与运算的特性,与hash位与之后,得到的结果是不是可能是0也可能是1,,也就是说最终的结果取决于hash的值,如此一来,只要输入的hashcode值本身是均匀分布的,那么hash算法得到的结果就是均匀的。

啥意思?这样得到的下标值就是均匀分布的啊,那冲突的几率就减少啦。

而如果容量不是2的整数次幂的话,就没有上述说的那个特性,这样冲突的概率就会增大。

所以,明白了为啥容量是2的整数次幂了吧。

那为啥是16嘞?难道不是2的整数次幂都行嘛?理论上是都行,但是如果是2,4或者8会不会有点小,添加不了多少数据就会扩容,也就是会频繁扩容,这样岂不是影响性能,那为啥不是32或者更大,那不就浪费空间了嘛,所以啊,16就作为一个非常合适的经验值保留了下来!

出现哈希冲突怎么解决

我们上面也提到了,在添加数据的时候尽管为实现下标值的均匀分布做了很多努力,但是势必还是会存在冲突的情况,那么该怎么解决冲突呢?

这就牵涉到哈希冲突的解决办法了,了解了哈希冲突的解决办法之后我们还要关注一个问题,那就是新的节点在插入到链表的时候,是怎么插入的?

回答开篇的问题

现在你应该知道,当出现hash冲突,可以使用链表来解决,那么这里就有问题,新来的Node是应该放在之前Node的前面还是后面呢?

Java8之前是头插法,啥意思嘞,就是放在之前Node的前面,为啥要这样,这是之前开发者觉得后面插入的数据会先用到,因为要使用这些Node是要遍历这个链表,在前面的遍历的会更快。

为什么使用尾插法?

但是在Java8及之后都使用尾插法了,就是放到后面,为啥这样?

这里主要是一个链表成环的问题,啥意思嘞,想一下,使用头插法是不是会改变链表的顺序,你后来的就应该在后面嘛,如果扩容的话,由于原本链表顺序有所改变,扩容之后重新hash,可能导致的情况就是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。

这样的话在多线程操作下就会出现死循环,而使用尾插法,在相同的前提下就不会出现这样的问题,因为扩容前后链表顺序是不变的,他们之间的引用关系也是不变的。

关于扩容

下面我们继续说HashMap的扩容,经过上面的分析,我们知道第一次使用HashMap是创建一个默认长度为16的底层Node数组,如果满了怎么办,那就需要进行扩容了,也就是之前谈及的resize方法,这个方法主要就是初始化和增加表的大小,关于扩容要知道这两个概念:

  1. Capacity:HashMap当前长度。
  2. LoadFactor:负载因子,默认值0.75f。

这里怎么扩容的呢?首先是达到一个条件之后会发生扩容,什么条件呢?就是这个负载因子,比如HashMap的容量是100,负载因子是0.75,乘以100就是75,所以当你增加第76个的时候就需要扩容了,那扩容又是怎么样步骤呢?

首先是创建一个新的数组,容量是原来的二倍,为啥是2倍,想一想为啥容量是2的整数次幂,这里扩容为原来的2倍不正好符号这个规则嘛。

然后会经过重新hash,把原来的数据放到新的数组上,至于为啥要重新hash,那必须啊,你容量变了,相应的hash算法规则也就变了,得到的结果自然不一样了。

关于链表转红黑树

在Java8之前是没有红黑树的实现的,在jdk1.8中加入了红黑树,就是当链表长度为8时会将链表转换为红黑树,为6时又会转换成链表,这样时提高了性能,也可以防止哈希碰撞攻击。

HashMap增加新元素的主要步骤

下面我们分析一下HashMap增加新元素的时候都会做哪些步骤:

  1. 首先肯定时根据key值,通过哈希算法得到value应该放在底层数组中的下标位置
  2. 根据这个下标定位到底层数组中的元素,当然,这里可能时链表,也可能时树,知道为啥吧,给你个提醒,链表转红黑树
  3. 拿到当前位置上的key值,与要放入的key比较,是否==或者equals,如果成立的话就替换value值,并且需要返回原来的值
  4. 当然,如果是树的话就要循环树中的节点,继续==和equals的判断,成立替换,否则添加到树里
  5. 链表的话就是循环遍历了,同样的判断,成立替换,否则就添加到链表的尾部

所以啊,这里面的重点就是判断放入HashMap中的元素要不要替换当前节点的元素,那怎么判断呢?总结起来只要满足以下两点即可替换:

1、hash值相等。

2、==或equals的结果为true。

感谢阅读

好了,到了这里就差不多了,开篇就说过HashMap可以说是Java集合的精髓了,想要彻底搞懂真心不容易,但是我们所掌握的应该足够应对平常的面试,关于HashMap更多的高级内容,后续会继续分享。

感谢大家的阅读,如有错误之处欢迎指正!

想要阅读更多精彩内容,可以关注我的微信公众号:Java技术zhai,这是我的私人公众号,专注于Java原创,主要涉及数据结构与算法,计算机基础以及Java核心知识的讲解,期待你的参与。


原文链接:https://www.cnblogs.com/lfs2640666960/p/12297446.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:SpringBoot 开发的那些小趣事儿

下一篇:什么是栈?