乐鱼电竞

  • 教育行业A股IPO第一股（股票代码 003032）

    全国咨询/投诉热线：400-618-4000

    了解HashMap底层设计思想，教你手写一个迷你版的HashMap!【java培训】

    更新时间:2020年04月09日14时58分 来源:乐鱼播客 浏览次数:

    HashMap是Java中常用的集合，而且HashMap的一些思想，对于我们平时解决业务上的一些问题，在思路上有帮助，基于此，本文将分析HashMap底层设计思想，并手写一个迷你版的HashMap!

    对HashMap的思考

    HashMap的思考01


    HashMap底层数据结构第一，如图所示，HashMap有3个要素：hash函数+数组+单链表。

    第二，对于hash函数而言，需要考虑些什么?

    要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢?显然是位运算!要均匀分布，要较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，不希望大量数据发生碰撞，导致链表过长。那么怎么办到呢?也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。

    如果发生了碰撞怎么办?上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么?比如说，如果发生冲突，那么记下这个冲突的位置为 index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法!

    通过写一个迷你版的HashMap来深刻理解定义接口

    定义接口

    HashMap的思考02

    接口

    定义一个接口，对外暴露快速存取的方法。注意MyMap接口内部定义了一个内部接口Entry。

    接口实现

    HashMap的思考03

    HashMap的要素之一，就是数组，自然在这里，我们要定义数组，数组的初始化大�。挂悸抢┤莸姆е�。

    看MyHashMap的构造

    HashMap的思考04


    构造方法有什么好说的呢?

    仔细观察下，你会发现，其实这里使用到了“门面模式”。这里的2个构造方法其实指向的是同一个，但是对外却暴露了2个“门面”!

    Entry

    HashMap的思考05

    HashMap的要素之一，单链表的体现就在这里!

    看put如何实现

    HashMap的思考06

    第一，要考虑是否扩容?

    HashMap中的Entry的数量(数组以及单链表中的所有Entry)是否达到阀值?

    第二，如果扩容，意味着新生成一个Entry[]，不仅如此还得重新散列。

    第三，要根据Key计算出在Entry[]中的位置，定位后，如果Entry[]中的元素为null，那么可以放入其中，如

    果不为空，那么得遍历单链表，要么更新value，要么形成一个新的Entry“挤压”单链表!

    hash函数

    HashMap的思考07

    MyHashMap提供的hash函数

    HashMap的思考08


    JDK的HashMap提供的hash函数

    我这里参考了JDK的HashMap的hash函数的实现，这里也再次说明了：要想散列均匀，就得进行二进制的位运算!

    resize和rehash

    HashMap的思考09

    这里可以看出，对于HashMap而言，如果频繁进行resize/rehash操作，是会影响性能的。

    resize/rehash的过程，就是数组变大，原来数组中的entry元素一个个的put到新数组的过程，需要注意的是一些状态变量的改变。

    get实现

    HashMap的思考10.png

    get

    get很简单，只需要注意在遍历单链表的过程中使用== or equals来判断下即可。

    Test测试

    HashMap的思考11

    利用MyHashMap进行存取

    运行结果

    HashMap的思考12

    OK，一个迷你版的HashMap就写好了，你学到了么?

    猜你喜欢：
    java中级程序员学习线路图

    如何使用solr完成vip等级排名?

    0 分享到：
    和我们在线交谈！
    • 【网站地图】【sitemap】