devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

手写简易版HashMap_手写hashmap

作者：花生_TL007 | 2024-03-13 02:40:30

赞

踩

手写hashmap

目录

前言

HashMap源码解析

1.hash值算法和幂等性

2. get()方法源码解析

3. put() 方法源码解析

手写HashMap

1. 定义Map接口

2. 定义Entry 对象

3 .定义HashMap 实现类

4. 测试

前言

    我们发现HashMap在jdk 1.8之后用了数组+链表+红黑树的结构，为了加深对HashMap底层设计的理解，自己也读了一些hashmap相关的源码，因此想通过手写hashmap去理其底层的操作原理。

    目标:  基于数组+链表结构实现一个HashMap，包含get()、put()、remove()方法。

    环境:  jdk1.8

    知识储备:  hashcode, 幂等性， 数组，链表，红黑树。

    原理:   Hashmap 是先通过key计算得到一个hash值，通过hash值%(length-1)找到桶的位置，找到位置通过比对key 和hash值就能得到key对应的value， 如果有链表遍历链表，如果有红黑树就遍历红黑树，然后再进行相应的操作，如get,put, remove等。

HashMap源码解析

1.hash值算法和幂等性

    通过此hash值和map的length计算得到key 在hashmap桶里的位置index, 使用到的hash算法也是采用散列思想，能够均匀分布在hashmap的桶里面。

    先看一段源代码, hash(object key)方法

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

可以发现， HashMap计算hash值是依据hashcode实现的，由于hashcode的幂等性，每次结算得出来的结果是相等的， 写一个小demo，多次运行程序:

        发现每次结算出来的结果是相同的, 因为幂等性，存放到桶里的key 对应的hash值是不相同的，同时也是固定的。

2. get()方法源码解析

      看一下hashmap里get()里一个重要的方法:  getNode()

       1) 根据hash值计算出位置赋值给first, 然后比较first的key是否与传入的key 相等，如果相等就返回，如果不相等，那么就遍历first的next。

       2) 如果first是一颗红黑树，那么就执行getTreeNode()方法，如果first不是那么就遍历链表。

具体的流程如下: 

1. 通过key 进行hash 计算得到index
2. 根据index  判断是否为空，如果为空就直接返回null。
3. 如果不为空，有查询的key与当前key 进行比较,如果当前节点的next是否为空，那么就返回当前节点，如果为不为空那么就取遍历next,判断node是否为树，如果是树，那么遍历树，如果是链表那么遍历链表，通过比较hash值和key来判断，直到相等为止。
4. 如果相等就直接返回数据。

3. put() 方法源码解析

        在Put 到桶里的元素之前，每个元素可以看作为一个Node, Node里包含 hash值，hash值是必须要有的，因为在遍历链表的时候，不能仅通过hashcode计算出来的index来比较，还有需要比较hash，才能找到指定的key, hashmap中定义的Node的结构如下:

  1.     static class Node<K,V> implements Map.Entry<K,V> {
  2.         final int hash;
  3.         final K key;
  4.         V value;
  5.         Node<K,V> next;
  6.  
  7.         Node(int hash, K key, V value, Node<K,V> next) {
  8.             this.hash = hash;
  9.             this.key = key;
  10.             this.value = value;
  11.             this.next = next;
  12.         }

  put 流程分析: 

   

具体的流程如下: 

1. 算出hashcode, 取模得到下标，然后通过下标拿到对象。

2. 如果为根据index取到的值为空那么可以直接赋值。

3.  如果不为空，那么使用链表进行存储， 每次存储的时候需要用新的节点的next指向之前的节点。

  看了几个方法的源码后，发现他们都有相似的规律:  通过hash值去找到node, 然后判断node是否是链表或者红黑树，然后遍历链表或TreeNode(红黑树)，然后再操作。

手写HashMap

1. 定义Map接口

           HashMap实现了Map接口，可以定义如下常用方法，另外需要添加一个Entry<K,V>接口，此接口用来获取节点(Entry)的key 和value。

  1. package com.example.hashmap;
  2.  
  3. /**
  4.  * @author bingbing
  5.  * @date 2021/5/15 0015 15:51
  6.  */
  7. public interface MyMap<K, V> {
  8.  
  9.     int size();
  10.  
  11.     V put(K k, V v);
  12.  
  13.     V get(K k);
  14.  
  15.     V remove(K k);
  16.  
  17.  
  18.     interface Entry<K, V> {
  19.  
  20.         K getKey();
  21.  
  22.         V getValue();
  23.  
  24.     }
  25. }

2. 定义Entry 对象

         主要包含当前节点的key、value、next指针以及hash值，另外实现Map里的Entry接口。

  1. class Entry<K, V> implements MyMap.Entry<K, V> {
  2.  
  3.         int hash;
  4.         K k;
  5.         V v;
  6.         Entry<K, V> next;
  7.  
  8.  
  9.         public Entry(K k, V v, Entry<K, V> next, int hash) {
  10.             this.k = k;
  11.             this.v = v;
  12.             this.hash = hash;
  13.             this.next = next;
  14.         }
  15.  
  16.         @Override
  17.         public K getKey() {
  18.             return k;
  19.         }
  20.  
  21.         @Override
  22.         public V getValue() {
  23.             return v;
  24.         }
  25.     }

3 .定义HashMap 实现类

        注意: 

             1)  put()方法，在new Node时将计算得到的hash值和当前的entry 当作next赋赋值给node。  table[index] = new Entry<>(k, v, entry, hash);

             2)  get()方法，在遍历链表的时候，需要比较hash值和next,key 。

             3)  remove()方法，如果在链表里，那么用前一个节点的next指向当前节点next即可删除。

  1. package com.example.hashmap;
  2.  
  3. /**
  4.  * @author bingbing
  5.  * @date 2021/5/15 0015 15:52
  6.  */
  7. public class MyHashMap<K, V> implements MyMap<K, V> {
  8.  
  9.  
  10.     Entry[] table = null;
  11.  
  12.     int size = 0;
  13.  
  14.  
  15.     public MyHashMap() {
  16.         table = new Entry[16];
  17.     }
  18.  
  19.     @Override
  20.     public int size() {
  21.         return size;
  22.     }
  23.  
  24.  
  25.     /**
  26.      * 算出hashcode, 取模得到下标，然后通过下标拿到对象。
  27.      * 如果为空那么可以直接赋值。
  28.      * 如果不为空，那么使用链表进行存储
  29.      *
  30.      * @param k
  31.      * @param v
  32.      * @return
  33.      */
  34.     @Override
  35.     public V put(K k, V v) {
  36.         int index = hash(k);
  37.         int hash = k.hashCode();
  38.         Entry<K, V> entry = table[index];
  39.         if (null == entry) {
  40.             table[index] = new Entry<>(k, v, null, hash);
  41.             size++;
  42.         } else {
  43.             // 链表
  44.             table[index] = new Entry<>(k, v, entry, hash);
  45.         }
  46.         return (V) table[index].getValue();
  47.     }
  48.  
  49.     private int hash(K k) {
  50.         int index = k.hashCode() % (table.length - 1);
  51.         if (index < 0) {
  52.             // 如果取的到为负数
  53.             return -index;
  54.         }
  55.         return index;
  56.     }
  57.  
  58.  
  59.     /**
  60.      * 1. 通过key 进行hash 计算得到index
  61.      * 2. 根据index  判断是否为空，如果为空就直接返回null。
  62.      * 3. 如果不为空，有查询的key与当前key 进行比较,如果当前节点的next是否为空，那么就返回当前节点，如果为不为空那么就取遍历next,直到相等为止。
  63.      * 4. 如果相等就直接返回数据。
  64.      *
  65.      * @param k
  66.      * @return
  67.      */
  68.     @Override
  69.     public V get(K k) {
  70.         int index = hash(k);
  71.         int hash = k.hashCode();
  72.         Entry<K, V> entry = table[index];
  73.         if (null == entry) {
  74.             return null;
  75.  
  76.         } else {
  77.             if (entry.getKey() == k && hash == entry.hash) {
  78.                 return entry.getValue();
  79.             }
  80.             Entry<K, V> next = entry.next;
  81.             while (null != next) {
  82.                 if (next.getKey() == k&& hash == next.hash) {
  83.                     return next.getValue();
  84.                 }
  85.                 next = next.next;
  86.             }
  87.         }
  88.         return null;
  89.     }
  90.  
  91.     @Override
  92.     public V remove(K k) {
  93.         int index = hash(k);
  94.         int hash = k.hashCode();
  95.         Entry<K, V> entry = table[index];
  96.         if (null == entry) {
  97.             return null;
  98.         } else {
  99.             if (entry.getKey() == k && entry.hash == hash) {
  100.                 // 直接移除该元素
  101.                 entry = entry.next;
  102.                 table[index] = entry;
  103.                 return (V) table[index];
  104.             }
  105.             if (null != entry.next) {
  106.                 // 链表
  107.                 Entry<K, V> head = entry;
  108.                 Entry<K, V> p = head;
  109.                 Entry<K, V> next = head.next;
  110.                 do {
  111.                     if (next.getKey() == k && next.hash == hash) {
  112.                         // 删除该节点, 前一个节点的next 指向该节点的next
  113.                         p.next = next.next;
  114.                         break;
  115.                     }
  116.                     p = next;
  117.                     next = next.next;
  118.                 } while (next != null);
  119.             } else {
  120.                 // 数组
  121.                 table[index] = null;
  122.             }
  123.             return table[index] == null ? null : (V) table[index].getValue();
  124.         }
  125.     }
  126.  
  127.     class Entry<K, V> implements MyMap.Entry<K, V> {
  128.  
  129.         int hash;
  130.         K k;
  131.         V v;
  132.         Entry<K, V> next;
  133.  
  134.  
  135.         public Entry(K k, V v, Entry<K, V> next, int hash) {
  136.             this.k = k;
  137.             this.v = v;
  138.             this.hash = hash;
  139.             this.next = next;
  140.         }
  141.  
  142.         @Override
  143.         public K getKey() {
  144.             return k;
  145.         }
  146.  
  147.         @Override
  148.         public V getValue() {
  149.             return v;
  150.         }
  151.     }
  152. }

4. 测试

      测试get(), put () ,remove()方法

  1. package com.example.hashmap;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author bingbing
  8.  * @date 2021/5/15 0015 15:19
  9.  */
  10.  
  11. public class HashMapDemo {
  12.  
  13.  
  14.     private static MyInnerMap myInnerMap = new MyInnerMap(16);
  15.  
  16.     public static void main(String[] args) {
  17.         Map<Object, Object> map = new HashMap<>(16);
  18.         map.put("张三", "张三");
  19.         map.put("李四", "李四");
  20.         map.put("王五", "王五");
  21.         map.put("刘六", "刘六");
  22.         System.out.println(map);
  23.         myInnerMap.put("张三", "张三");
  24.         myInnerMap.put("李四", "李四");
  25.         myInnerMap.put("王五", "王五");
  26.         myInnerMap.put("刘六", "刘六");
  27.         myInnerMap.put("小二", "小二");
  28.         myInnerMap.put("李七", "李七");
  29.         myInnerMap.put("赵九", "赵九");
  30.         myInnerMap.put("周十", "周十");
  31.         myInnerMap.put("孙一", "孙一");
  32.  
  33.         //  使用自定义的Map
  34.         MyMap<Object, Object> myMap = new MyHashMap<>();
  35.         myMap.put("张三", "张三");
  36.         myMap.put("李四", "李四");
  37.         Object o = myMap.put("周十", "周十");
  38.         System.out.println(myMap.get("张三"));
  39.         System.out.println(myMap.get("李四"));
  40.         System.out.println(myMap.get("周十"));
  41.         myMap.remove("周十");
  42.         System.out.println(myMap.get("周十"));
  43.         myMap.remove("李四");
  44.         System.out.println(myMap.get("李四"));
  45.  
  46.  
  47.     }
  48.  
  49.  
  50.     static class MyInnerMap {
  51.  
  52.         int length;
  53.  
  54.         MyInnerMap(int capacity) {
  55.             this.length = capacity;
  56.         }
  57.  
  58.  
  59.         // 利用数组的特性去取模，得到的hashcode 遵循幂等性
  60.         public void put(Object key, Object value) {
  61.             System.out.println("key:" + key + ",hashcode:" + key.hashCode() + ",位置:" + Math.abs(key.hashCode()) % (length - 1));
  62.         }
  63.     }
  64.  
  65. }

    打印结果如下:

 

   源码地址:  java-source-learining: java框架源码学习

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/227361
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号