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

小灰灰 2024-04-07 14:17 30阅读 0赞

### 写在前面 ###

最近有很多的粉丝私信我，说自己在面试的时候，老是被人问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原理而编写的，区块链就不做更多的阐述了。