您当前的位置:首页 > 互联网百科 > 区块链

浅谈HashMap原理,并手写HashMap并实现部分区块链特征

时间:2022-09-08 11:29:35  来源:今日头条  作者:Java那点事儿

写在前面

最近有很多的粉丝私信我,说自己在面试的时候,老是被人问HashMap的原理,但是在实际的工作中,也只是使用HashMap,从来就没有关注过它的原来,今天博主本人,根据自己的实际经验,浅谈一下HashMap的实现原理。并附上自己根据原理,手写的MHashMap,并且还带上了部分区块链的特征。

JDK7和JDK8中的HashMap

JDK7:数组和链式结构 JDK8:数组和链式结构,红黑树 两者之间的区别就是,JDK8中加上了红黑树。 因为今天是一个HashMap的原理浅析,这里就不附带讲解红黑树,后面的博文,我会专门来讲解红黑树。

正文

现在我开始正式进入我对HashMap讲解中来。 HashMap的特征

存储结构:key,value键值对的形式

查询数据: 1,通过key进行mod(取模),获取到当前数组对应的node, 2,根据node存放的hash和key对应的hash进行比较,是否一致,如果不一致,则同当前node的下一个node进行比对。 3,还是不一致,就继续从当前比较的Node取下一个节点进行比较。

存储数据: 1,对key进行mod计算 2,将数据存放到data[mod]中去 3,如果当前的data[mod]已经有值存在了,则将当前已经存在的对象oldNode,存放到新的Node的next中去

我们定义一个数组,并给给它一个默认的长度

private final static int defaultDataLength = 16;

再创建一个指定长度的数组

private Node[] data = new Node[defaultDataLength];

这里的Node为我们自己定义的一个内部类对象

@Getter
    @Setter
    static class Node {
        private int hashCode;
        private Object key;
        private Object value;
        private Node next;

        public static Node instance(int hashCode, Object key, Object value, Node next) {
            Node node = new Node();
            node.setHashCode(hashCode);
            node.setKey(key);
            node.setValue(value);
            node.setNext(next);
            return node;
        }
    }

它由四个元素组成,当前传入key的hash值,当前的key,当前的value及下一个对象。

完整代码

package com.moonl.jvm.utils;

import lombok.Getter;
import lombok.Setter;

import JAVA.io.Serializable;
import java.util.AbstractMap;
import java.util.Map;
import java.util.Set;

public class MHashMap<K, V> {

    private final static int defaultDataLength = 16;

    private Node[] data = new Node[defaultDataLength];

    private Integer previousHashCode = 0;


    public V put(K key, V value) {
        int hash = hash(key);
        int mod = hashMod(key);
        if (null == data[mod]) {
            data[mod] = Node.instance(hash, key, value, null);
            return value;
        }
        //旧的node缓存
        Node oldNode = data[mod];
        //新的key,存放到指定位置的数组中去,并将原有节点存放到next中
        data[mod] = Node.instance(hash, key, value, oldNode);
        return value;
    }

    public V get(K key) {
        Node node = data[hashMod(key)];
        //root node hashCode
        this.previousHashCode = hash((K) ("root_" + hashMod(key)));
        return findKey(node, key);
    }


    public V findKey(Node node, K key) {

        if (null == key) {
            return null;
        }
        if (node == null) {
            return null;
        }
        String chain = "The Previous HashCode:" + previousHashCode + " Now HashCode :" + node.getHashCode();
        //传入的key对应的hash
        int hash = hash(key);
        //当前节点存储的hashCode
        int hashCode = node.getHashCode();
        if (hash == hashCode) {
            System.out.println("input key is :" + key + " and hash:" + hashCode);
            System.out.println("query key is :" + node.getKey() + " and hash:" + node.getHashCode());
            return (V) node.getValue();
        }
        //当前找到的节点的下一个节点
        Node nextNode = node.getNext();
        //如果要从下一个节点开始查询,则当前节点变更为上一个节点
        previousHashCode = node.getHashCode();
        chain = chain + " Next Node HashCode :" + nextNode.getHashCode();
        System.out.println(chain);
        return findKey(nextNode, key);
    }

    public int hash(K key) {
        int hashCode = 0;
        return key == null ? 0 : key.hashCode();
    }

    public int hashMod(K key) {
        return Math.abs(key.hashCode() % 16);
    }

    @Getter
    @Setter
    static class Node {
        private int hashCode;
        private Object key;
        private Object value;
        private Node next;

        public static Node instance(int hashCode, Object key, Object value, Node next) {
            Node node = new Node();
            node.setHashCode(hashCode);
            node.setKey(key);
            node.setValue(value);
            node.setNext(next);
            return node;
        }
    }


}

在代码中,我对根节点,也就是数组节点的记录方式是"root_"+mod值共同生成的hash // 现在我们开始使用封装数据(put),并逐步(get)数据

@Test
    public void testHashMap() {
//        Map<String, Object> maps = new HashMap<String, Object>();
        MHashMap<String, Object> zhaoMaps = new MHashMap<String, Object>();
        for (int i = 0; i < 1000; i++) {
            zhaoMaps.put("赵"+i+"姐","赵颖"+i+"姐 is 250");
        }
        MHashMap<String, Object> yingMaps = new MHashMap<String, Object>();
        for (int i = 0; i < 1000; i++) {
            yingMaps.put("大颖"+i+"姐","大颖"+i+"姐 is 250");
        }
        System.out.println(zhaoMaps.get("赵162姐"));
        System.out.println(yingMaps.get("大颖456姐"));
    }

输出的结果是

The Previous HashCode:-925311973 Now HashCode :-914498616 Next Node HashCode :-914499608
The Previous HashCode:-914498616 Now HashCode :-914499608 Next Node HashCode :-914500600
The Previous HashCode:-914499608 Now HashCode :-914500600 Next Node HashCode :-914501592
The Previous HashCode:-914500600 Now HashCode :-914501592 Next Node HashCode :-914502584
The Previous HashCode:-914501592 Now HashCode :-914502584 Next Node HashCode :-914503576
The Previous HashCode:-914502584 Now HashCode :-914503576 Next Node HashCode :-914529368
The Previous HashCode:-914503576 Now HashCode :-914529368 Next Node HashCode :-914530360
The Previous HashCode:-914529368 Now HashCode :-914530360 Next Node HashCode :-914531352
The Previous HashCode:-914530360 Now HashCode :-914531352 Next Node HashCode :-914532344
The Previous HashCode:-914531352 Now HashCode :-914532344 Next Node HashCode :-914533336
The Previous HashCode:-914532344 Now HashCode :-914533336 Next Node HashCode :-914560120
The Previous HashCode:-914533336 Now HashCode :-914560120 Next Node HashCode :-914561112
The Previous HashCode:-914560120 Now HashCode :-914561112 Next Node HashCode :-914562104
The Previous HashCode:-914561112 Now HashCode :-914562104 Next Node HashCode :-914563096
The Previous HashCode:-914562104 Now HashCode :-914563096 Next Node HashCode :-914584424
The Previous HashCode:-914563096 Now HashCode :-914584424 Next Node HashCode :-914590872
The Previous HashCode:-914584424 Now HashCode :-914590872 Next Node HashCode :-914591864
The Previous HashCode:-914590872 Now HashCode :-914591864 Next Node HashCode :-914592856
The Previous HashCode:-914591864 Now HashCode :-914592856 Next Node HashCode :-914614184
The Previous HashCode:-914592856 Now HashCode :-914614184 Next Node HashCode :-914615176
The Previous HashCode:-914614184 Now HashCode :-914615176 Next Node HashCode :-914621624
The Previous HashCode:-914615176 Now HashCode :-914621624 Next Node HashCode :-914622616
The Previous HashCode:-914621624 Now HashCode :-914622616 Next Node HashCode :-914643944
The Previous HashCode:-914622616 Now HashCode :-914643944 Next Node HashCode :-914644936
The Previous HashCode:-914643944 Now HashCode :-914644936 Next Node HashCode :-914645928
The Previous HashCode:-914644936 Now HashCode :-914645928 Next Node HashCode :-914652376
The Previous HashCode:-914645928 Now HashCode :-914652376 Next Node HashCode :-914673704
The Previous HashCode:-914652376 Now HashCode :-914673704 Next Node HashCode :-914674696
The Previous HashCode:-914673704 Now HashCode :-914674696 Next Node HashCode :-914675688
The Previous HashCode:-914674696 Now HashCode :-914675688 Next Node HashCode :-914676680
The Previous HashCode:-914675688 Now HashCode :-914676680 Next Node HashCode :-914703464
The Previous HashCode:-914676680 Now HashCode :-914703464 Next Node HashCode :-914704456
The Previous HashCode:-914703464 Now HashCode :-914704456 Next Node HashCode :-914705448
The Previous HashCode:-914704456 Now HashCode :-914705448 Next Node HashCode :-914706440
The Previous HashCode:-914705448 Now HashCode :-914706440 Next Node HashCode :-914707432
The Previous HashCode:-914706440 Now HashCode :-914707432 Next Node HashCode :-914733224
The Previous HashCode:-914707432 Now HashCode :-914733224 Next Node HashCode :-914734216
The Previous HashCode:-914733224 Now HashCode :-914734216 Next Node HashCode :-914735208
The Previous HashCode:-914734216 Now HashCode :-914735208 Next Node HashCode :-914736200
input key is :赵162姐 and hash:-914736200
query key is :赵162姐 and hash:-914736200
赵颖162姐 is 250
The Previous HashCode:-925311975 Now HashCode :-2010266582 Next Node HashCode :-2010267574
The Previous HashCode:-2010266582 Now HashCode :-2010267574 Next Node HashCode :-2010268566
The Previous HashCode:-2010267574 Now HashCode :-2010268566 Next Node HashCode :-2010269558
The Previous HashCode:-2010268566 Now HashCode :-2010269558 Next Node HashCode :-2010270550
The Previous HashCode:-2010269558 Now HashCode :-2010270550 Next Node HashCode :-2010271542
The Previous HashCode:-2010270550 Now HashCode :-2010271542 Next Node HashCode :-2010296342
The Previous HashCode:-2010271542 Now HashCode :-2010296342 Next Node HashCode :-2010297334
The Previous HashCode:-2010296342 Now HashCode :-2010297334 Next Node HashCode :-2010298326
The Previous HashCode:-2010297334 Now HashCode :-2010298326 Next Node HashCode :-2010299318
The Previous HashCode:-2010298326 Now HashCode :-2010299318 Next Node HashCode :-2010300310
The Previous HashCode:-2010299318 Now HashCode :-2010300310 Next Node HashCode :-2010301302
The Previous HashCode:-2010300310 Now HashCode :-2010301302 Next Node HashCode :-2010302294
The Previous HashCode:-2010301302 Now HashCode :-2010302294 Next Node HashCode :-2010326102
The Previous HashCode:-2010302294 Now HashCode :-2010326102 Next Node HashCode :-2010327094
The Previous HashCode:-2010326102 Now HashCode :-2010327094 Next Node HashCode :-2010328086
The Previous HashCode:-2010327094 Now HashCode :-2010328086 Next Node HashCode :-2010329078
The Previous HashCode:-2010328086 Now HashCode :-2010329078 Next Node HashCode :-2010330070
The Previous HashCode:-2010329078 Now HashCode :-2010330070 Next Node HashCode :-2010331062
The Previous HashCode:-2010330070 Now HashCode :-2010331062 Next Node HashCode :-2010332054
The Previous HashCode:-2010331062 Now HashCode :-2010332054 Next Node HashCode :-2010333046
The Previous HashCode:-2010332054 Now HashCode :-2010333046 Next Node HashCode :-2010355862
The Previous HashCode:-2010333046 Now HashCode :-2010355862 Next Node HashCode :-2010356854
The Previous HashCode:-2010355862 Now HashCode :-2010356854 Next Node HashCode :-2010357846
The Previous HashCode:-2010356854 Now HashCode :-2010357846 Next Node HashCode :-2010358838
The Previous HashCode:-2010357846 Now HashCode :-2010358838 Next Node HashCode :-2010359830
The Previous HashCode:-2010358838 Now HashCode :-2010359830 Next Node HashCode :-2010360822
The Previous HashCode:-2010359830 Now HashCode :-2010360822 Next Node HashCode :-2010361814
The Previous HashCode:-2010360822 Now HashCode :-2010361814 Next Node HashCode :-2010362806
The Previous HashCode:-2010361814 Now HashCode :-2010362806 Next Node HashCode :-2010363798
The Previous HashCode:-2010362806 Now HashCode :-2010363798 Next Node HashCode :-2010385622
The Previous HashCode:-2010363798 Now HashCode :-2010385622 Next Node HashCode :-2010386614
The Previous HashCode:-2010385622 Now HashCode :-2010386614 Next Node HashCode :-2010387606
The Previous HashCode:-2010386614 Now HashCode :-2010387606 Next Node HashCode :-2010388598
The Previous HashCode:-2010387606 Now HashCode :-2010388598 Next Node HashCode :-2010389590
The Previous HashCode:-2010388598 Now HashCode :-2010389590 Next Node HashCode :-2010390582
The Previous HashCode:-2010389590 Now HashCode :-2010390582 Next Node HashCode :-2010391574
The Previous HashCode:-2010390582 Now HashCode :-2010391574 Next Node HashCode :-2010392566
The Previous HashCode:-2010391574 Now HashCode :-2010392566 Next Node HashCode :-2010393558
The Previous HashCode:-2010392566 Now HashCode :-2010393558 Next Node HashCode :-2010394550
The Previous HashCode:-2010393558 Now HashCode :-2010394550 Next Node HashCode :-2010416374
The Previous HashCode:-2010394550 Now HashCode :-2010416374 Next Node HashCode :-2010417366
The Previous HashCode:-2010416374 Now HashCode :-2010417366 Next Node HashCode :-2010418358
The Previous HashCode:-2010417366 Now HashCode :-2010418358 Next Node HashCode :-2010419350
input key is :大颖456姐 and hash:-2010419350
query key is :大颖456姐 and hash:-2010419350
大颖456姐 is 250

通过输出的日志,我们可以看见,node节点的存储结构是按照区块链的特性,记录上个节点的信息和下一个节点的信息关系来存储数据。

当然,这里我们对Node对象再写深入一些,加上一些共识的算法,加密解密验签的算法,并做节点的共享,那么一个简单的区块链就完成了。

本文,主要是为了解答粉丝在面试过程中,面试官不停问HashMap原理而编写的,区块链就不做更多的阐述了。



Tags:HashMap   点击:( )  评论:( )
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:[email protected]),我们将及时更正、删除,谢谢。
▌相关推荐
写在前面最近有很多的粉丝私信我,说自己在面试的时候,老是被人问HashMap的原理,但是在实际的工作中,也只是使用HashMap,从来就没有关注过它的原来,今天博主本人,根据自己的实际经验...【详细内容】
2022-09-08  Tags: HashMap  点击:(0)  评论:(0)  加入收藏
1、HashMap主要成员变量size 记录了 Map 中 KV 对的个数。loadFactor 装载印子,用来衡量 HashMap 满的程度。loadFactor 的默认值为 0.75f。threshold 临界值,当实际 KV 个数...【详细内容】
2021-06-08  Tags: HashMap  点击:(301)  评论:(0)  加入收藏
场景描述我们在日常学习和研发中,经常会接触一些底层的源码,有些同学在遇到位运算(提高系统的运行效率)实现的方法时,读起来就有些吃力了,例如HashMap类中的tableSizeFor(int cap...【详细内容】
2021-04-06  Tags: HashMap  点击:(283)  评论:(0)  加入收藏
前言本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。01、...【详细内容】
2021-01-18  Tags: HashMap  点击:(218)  评论:(0)  加入收藏
本节让我们一起研究一下该容器是如何在保证线程安全的同时又能保证高效的操作。 ConcurrentHashMap 是线程安全且高效的 HashMap 。...【详细内容】
2020-10-16  Tags: HashMap  点击:(116)  评论:(0)  加入收藏
絮叨学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是java程序员都知道,HashMap...【详细内容】
2020-09-27  Tags: HashMap  点击:(112)  评论:(0)  加入收藏
一、前言得益于Doug Lea老爷子的操刀,让HashMap成为使用和面试最频繁的API,没办法设计的太优秀了!HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和...【详细内容】
2020-08-11  Tags: HashMap  点击:(69)  评论:(0)  加入收藏
TL:DR他们将键映射到值。哈希映射可能是映射概念最常用的实现。 它们允许将任意对象与其他任意对象关联。这对于执行诸如通过某些公共属性将数据分组或连接在一起之类的工作...【详细内容】
2020-07-19  Tags: HashMap  点击:(98)  评论:(0)  加入收藏
jdk1.7中的底层实现过程(底层基于数组+链表)在我们new HashMap()时,底层创建了默认长度为16的一维数组Entry[ ] table。当我们调用map.put(key1,value1)方法向HashMap里添加数...【详细内容】
2020-06-28  Tags: HashMap  点击:(62)  评论:(0)  加入收藏
通过Map.values()遍历所有的value,不能遍历key public class TestDemo{ public static void main(String[] args) { HashMap<String,String> hashMap = new Has...【详细内容】
2020-03-08  Tags: HashMap  点击:(97)  评论:(0)  加入收藏
▌哈哈电竞推荐
写在前面最近有很多的粉丝私信我,说自己在面试的时候,老是被人问HashMap的原理,但是在实际的工作中,也只是使用HashMap,从来就没有关注过它的原来,今天博主本人,根据自己的实际经验...【详细内容】
2022-09-08  Java那点事儿  今日头条  Tags:HashMap   点击:(0)  评论:(0)  加入收藏
什么是区块链技术?区块链技术是一个相对较新的概念,有可能彻底改变我们存储和管理数据的方式。区块链的核心是一个分布式数据库,允许安全、透明和防篡改的数据存储。区块链技...【详细内容】
2022-08-26  木白说币     Tags:区块链   点击:(16)  评论:(0)  加入收藏
“区块链”技术有哪些特点?一是“去中心化”,没有中心,或者人人都是中心,个体独立,有效防止“中心”滥用职权。比如,类似希特勒、萨达姆等独裁政权,因为“去中心化”,就难以形成;或...【详细内容】
2022-08-10  oiom4425    Tags:区块链   点击:(31)  评论:(0)  加入收藏
在《web3:一场概念游戏》与《web3:赛博资本主义的诞生》中,我们讨论了将“可拥有”当作web3新技术愿景的核心,实际上是一种违背常识的荒谬文字游戏。这种将意识形态“技术化”的...【详细内容】
2022-08-09  品玩    Tags:区块链   点击:(22)  评论:(0)  加入收藏
在这个教程中,我们将学习如何编写 Rust 智能合约并使用 Metaplex 在 Solana 上铸造 NFT。 用熟悉的语言学习 Web3.0 开发 : Java | Php | Python | .Net / C# | Golang | Node...【详细内容】
2022-08-03  新缸中之脑    Tags:NFT   点击:(37)  评论:(0)  加入收藏
为了理解智能合约以及为什么它对 Web 3.0 很重要,首先必须了解互联网从 Web 1.0 到 Web 3.0 的演变。 自从1980 年代初首次推出以来,由于从 Web 1.0 开始的多次调整和改进,互联...【详细内容】
2022-08-01  听朕有话要讲    Tags:智能合约   点击:(24)  评论:(0)  加入收藏
什么是REITs CHAIN?REITs CHAIN全球资产数字化生态公链,是去中心化、开源的有智能合约的公链。有着丰富的Web3+DeFi+NFTs+DAOs+Metaverse新生态。采用PoW+DPoS混合机制,两个账...【详细内容】
2022-07-26  REITsCHAIN    Tags:区块链   点击:(53)  评论:(0)  加入收藏
渤海银行被曝挪用客户28亿资金的新闻曾经冲上热搜。如果新闻属实,那如此体量的大客户的钱都不能保证安全,我们这些小虾米的钱的安全就更加不好说了。所以,这个新闻事情对银行业...【详细内容】
2022-07-15  石桥上的狐狸    Tags:区块链   点击:(9)  评论:(0)  加入收藏
在区块链世界中,智能合约是不可缺少的一部分。而作为一种真正意义上运行在去中心化网络上的合约,Solidity在智能合约的编写中占据了非常大的份额,学习solidity属于入门区块链的...【详细内容】
2022-07-14  程序员客栈    Tags:区块链   点击:(28)  评论:(0)  加入收藏
本文为万向区块链双碳项目负责人李群在“商业认知研究院&middot;每周研讨”上分享的内容。“碳中和”是全人类面临的共同议题,世界大部分国家都开始坚定地执行此策略。中国也...【详细内容】
2022-06-15  万向区块链    Tags:区块链   点击:(35)  评论:(0)  加入收藏
站内最新
站内热门
站内头条