登录
首页 >  数据库 >  MySQL

HashMap的实现原理(看这篇就够了)

来源:SegmentFault

时间:2023-01-19 13:48:54 443浏览 收藏

有志者,事竟成!如果你在学习数据库,那么本文《HashMap的实现原理(看这篇就够了)》,就很适合你!文章讲解的知识点主要包括MySQL、Redis、Java、spring、springboot,若是你对本文感兴趣,或者是想搞懂其中某个知识点,就请你继续往下看吧~

image.png

HashMap 是一线资深 java工程师必须要精通的集合容器,它的重要性几乎等同于Volatile在并发编程的重要性(可见性与有序性)。

本篇通过图文源码详解,深度剖析 HashMap 的重要内核知识,易看易学易懂。建议收藏,多学一点总是好的,万一面试被问到了呢。

我是Mike,10余年BAT一线大厂架构技术倾囊相授本篇重点

  1. HashMap的数据结构
  2. HashMap核心成员
  3. HashMapd的Node数组
  4. HashMap的数据存储
  5. HashMap的哈希函数
  6. 哈希冲突:链式哈希表
  7. HashMap的get方法:哈希函数
  8. HashMap的put方法
  9. 为什么槽位数必须使用2^n?

HashMap的数据结构

首先,我们从数据结构的角度来看:HashMap是:数组+链表+红黑树(JDK1.8增加了红黑树部分)的数据结构,如下所示:

HashMap JDK1.8数据结构

这里需要搞明白两个问题

*数据底层具体存储的是什么?
这样的存储方式有什么优点呢?*

static class Node implements Map.Entry {

    final int hash;//用来定位数组索引位置

    final K key;

    V value;

    Node next;//链表的下一个Node节点

 

    Node(int hash, K key, V value, Node next) {

        this.hash = hash;

        this.key = key;

        this.value = value;

        this.next = next;

    }

 

    public final K getKey()        { return key; }

    public final V getValue()      { return value; }

    public final String toString() { return key + "=" + value; }

 

    public final int hashCode() {

        return Objects.hashCode(key) ^ Objects.hashCode(value);

    }



    public final V setValue(V newValue) {

        V oldValue = value;

        value = newValue;

        return oldValue;

    }



    public final boolean equals(Object o) {

        if (o == this)

            return true;

        if (o instanceof Map.Entry) {

            Map.Entry,?> e = (Map.Entry,?>)o;

            if (Objects.equals(key, e.getKey()) &&

                Objects.equals(value, e.getValue()))

                return true;

        }

        return false;

    }

}

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。

HashMap的数据存储

1.哈希表来存储

HashMap采用哈希表来存储数据。

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构,只要输入待查找的值即key,即可查找到其对应的值。

哈希表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

2.哈希函数

哈希表中元素是由哈希函数确定的,将数据元素的关键字Key作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。

表示为:Addr = H(key),如下图所示:

哈希函数

哈希表中哈希函数的设计是相当重要的,这也是建哈希表过程中的关键问题之一。

3.核心问题

建立一个哈希表之前,需要解决两个主要问题

1) 构造一个合适的哈希函数,均匀性 H(key)的值均匀分布在哈希表中

2) 冲突的处理

冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。

4.哈希冲突:链式哈希表

哈希表为解决冲突,可以采用地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。

链地址法,简单来说,就是数组加链表的结合,如下图所示:

哈希冲突:链式哈希表

HashMap的哈希函数

/**

* 重新计算哈希值

*/

static final int hash(Object key) {

    

    int h;

 

     // h = key.hashCode() 为第一步 取hashCode值

     // h ^ (h >>> 16) 为第二步 高位参与运算

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

//计算数组槽位

(n - 1) & hash

对key进行了 hashCode 运算,得到一个32位的 int 值 h, 然后用 h 异或 h>>>16位。在 JDK1.8 的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:
(h = k.hashCode()) ^ (h >>> 16)。

在这里插入图片描述

这样做的好处是

可以将hashcode高位和低位的值进行混合做异或运算,而且混合后,低位的信息中加入了高位的信息,这样高位的信息被变相的保留了下来。

等于说计算下标时把hash的高16位也参与进来了,掺杂的元素多了,那么生成的hash值的随机性会增大,减少了hash碰撞。

备注:

 - ^异或:不同为1,相同为0
 -  >>> :无符号右移:右边补0
 - &运算:两位同时为“1”,结果才为“1,否则为0

h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方。

为什么槽位数必须使用2^n

1. 为了让哈希后的结果更加均匀

在这里插入图片描述

假如槽位数不是16,而是17,则槽位计算公式变成:(17 – 1) & hash

从上文可以看出,计算结果将会大大趋同,hashcode参加&运算后被更多位的0屏蔽,计算结果只剩下两种0和16,这对于hashmap来说是一种灾难。2.等价于length取模

当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

位运算的运算效率高于算术运算,原因是算术运算还是会被转化为位运算。

最终目的,还是为了让哈希后的结果更均匀的分部,减少哈希碰撞,提升hashmap的运行效率

分析HashMap的put方法:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {

    Node[] tab; Node p; int n, i;

    

    // 当前对象的数组是null 或者数组长度时0时,则需要初始化数组

    if ((tab = table) == null || (n = tab.length) == 0) {

        n = (tab = resize()).length;

    }

    

    // 使用hash与数组长度减一的值进行异或得到分散的数组下标,预示着按照计算现在的

    // key会存放到这个位置上,如果这个位置上没有值,那么直接新建k-v节点存放

    // 其中长度n是一个2的幂次数

    if ((p = tab[i = (n - 1) & hash]) == null) {

        tab[i] = newNode(hash, key, value, null);

    }

    

    // 如果走到else这一步,说明key索引到的数组位置上已经存在内容,即出现了碰撞

    // 这个时候需要更为复杂处理碰撞的方式来处理,如链表和树

    else {

        Node e; K k;

       

        //节点key存在,直接覆盖value

        if (p.hash == hash &&

            ((k = p.key) == key || (key != null && key.equals(k)))) {

            e = p;

        }

        // 判断该链为红黑树

        else if (p instanceof TreeNode) {

            // 其中this表示当前HashMap, tab为map中的数组

            e = ((TreeNode)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);

                    // TREEIFY_THRESHOLD = 8

                    // 从0开始的,如果到了7则说明满8了,这个时候就需要转

                    // 重新确定是否是扩容还是转用红黑树了

                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                        treeifyBin(tab, hash);

                    break;

                }

                // 找到了碰撞节点中,key完全相等的节点,则用新节点替换老节点

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    break;

                p = e;

            }

        }

        // 此时的e是保存的被碰撞的那个节点,即老节点

        if (e != null) { // existing mapping for key

            V oldValue = e.value;

            // onlyIfAbsent是方法的调用参数,表示是否替换已存在的值,

            // 在默认的put方法中这个值是false,所以这里会用新值替换旧值

            if (!onlyIfAbsent || oldValue == null)

                e.value = value;

            // Callbacks to allow LinkedHashMap post-actions

            afterNodeAccess(e);

            return oldValue;

        }

    }

    // map变更性操作计数器

    // 比如map结构化的变更像内容增减或者rehash,这将直接导致外部map的并发

    // 迭代引起fail-fast问题,该值就是比较的基础

    ++modCount;

   

     // size即map中包括k-v数量的多少

   // 超过最大容量 就扩容

    if (++size > threshold)

        resize();

    // Callbacks to allow LinkedHashMap post-actions

    afterNodeInsertion(evict);

    return null;

}

HashMap的put方法执行过程整体如下

① 判断键值对数组 table[i] 是否为空或为null,否则执行 resize() 进行扩容;

② 根据键值 key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加;

③ 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value;

④ 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对;

⑤ 遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥ 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

HashMap总结

HashMap底层结构?基于Map接口的实现,数组+链表的结构,JDK 1.8后加入了红黑树,链表长度>8变红黑树,

两个对象的hashcode相同会发生什么? Hash冲突,HashMap通过链表来解决hash冲突

HashMap 中 equals() 和 hashCode() 有什么作用?HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash(),然后计算下标 ( n-1 & hash),从而获得要找的同的位置。当发生冲突(碰撞)时,利用 key.equals() 方法去链表或树中去查找对应的节点

HashMap 何时扩容?put的元素达到容量乘负载因子的时候,默认16*0.75

hash 的实现吗?h = key.hashCode()) ^ (h >>> 16), hashCode 进行无符号右移 16 位,然后进行按位异或,得到这个键的哈希值,由于哈希表的容量都是 2 的 N 次方,在当前,元素的 hashCode() 在很多时候下低位是相同的,这将导致冲突(碰撞),因此 1.8 以后做了个移位操作:将元素的 hashCode() 和自己右移 16 位后的结果求异或

HashMap线程安全吗?HashMap读写效率较高,但是因为其是非同步的,即读写等操作都是没有锁保护的,所以在多线程场景下是不安全的,容易出现数据不一致的问题,在单线程场景下非常推荐使用。

---END--

关于作者:mikechen,十余年BAT架构经验,资深技术专家,曾任职阿里、淘宝、百度。

欢迎关注个人公众号:mikechen的互联网架构,十余年BAT架构经验倾囊相授!

在公众号菜单栏对话框回复【架构】关键词,即可查看我原创的300期+BAT架构技术系列文章与1000+大厂面试题答案合集。

image.png

文中关于mysql的知识介绍,希望对你的学习有所帮助!若是受益匪浅,那就动动鼠标收藏这篇《HashMap的实现原理(看这篇就够了)》文章吧,也可关注golang学习网公众号了解相关技术文章。

声明:本文转载于:SegmentFault 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表