【手撕代码】手写一个简单的HashMap

柔光的暖阳◎ 2021-12-15 12:25 303阅读 0赞

最近看面经发现很多人都遇到手写 HashMap 的场景。我们都知道 JDK1.7 和 JDK1.8 中的 HashMap 实现差别还是比较大的，主要是 JDK1.8中的 HashMap 引入了红黑树。那么面试过程中，应该不会让你手写红黑树的（我觉得），所以只需要掌握一个简单的 put、get、resize 方法即可。本文先写了 put 和 get 方法，其他方法后续再完善。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

1、先新建 16个 桶即 bucket（16是源码默认的，可以自定义），给桶分别标上 1~16 标号；

2、put 一个键值对之后，用 key 的 hash 值对 16 取余，结果肯定也是一个 1~16 范围内的数值，把这对键值对放到取余后的值对应的那个的桶里（注意，不可能为每一个 hash 值都创建一个桶，那样的话代价太大，这里只创建了16个桶，所以很有可能一个桶里放入多个键值对。如果偏巧那个桶里是空的，直接把 key、value 放进去，如果桶不为空，就要一个一个比对桶里原有的 key 是否和现在要放进去的 key 是同一个（即 hash 值相同且 equals 为 true），如果是同一个，那么就用新的 value 覆盖替换原来的 value 就行，如果遍历完了，没有一个相同的 key，那么就放到所有 key 的最后面（jdk1.8之后是放在最前面），这样有多个键值对的桶里就形成了一个链表结构，而多个桶之间是数组元素的关系，所以说 HashMap 就是数组+链表结构。

3、get 一个 key 的值，也是现根据 key 的 hash 对 16 取余，确定其在数组中的 index，然后判断 数组下标为 index 处是否为空，如果为空，则直接返回空（所以说：HashMap 无法判断 value 为空是 key 为空还是 不存在 key 的节点），否则遍历 index 处的节点，直到找到 key，返回其对应的 value。

*  ## 代码实现 ##

### 第 1 步：自定义 MyMap 接口  ###

public interface MyMap<K, V> {
    
        // 插入一个值
        V put(K key, V value);
    
        // 获取一个值
        V get(K key);
    
        // HashMap 中的节点
        interface Entry<K, V>{
            K getKey();
    
            V getValue();
        }
    }

###  第 2 步：自定义 MyHashMap，实现 put、get 方法 ###

public class MyHashMap<K, V> implements MyMap<K, V>{
    
        private static final int DEFAULT_INITIAL_CAPACITY = 16;
        private static final float DEFAULT_LOAD_FACTOR = 0.75f;
        private float loadFactor = 0;
        private int initCapacity = 0;
        private Entry<K, V>[] table = null;
    
        // 默认构造函数
        public MyHashMap(){
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            this.initCapacity = DEFAULT_INITIAL_CAPACITY;
            table = new Entry[this.initCapacity];
        }
    
        // 自定义构造函数
        public MyHashMap(int initCapacity, float loadFactor){
            this.loadFactor = loadFactor;
            this.initCapacity = initCapacity;
            table = new Entry[this.initCapacity];
        }
    
        private int hash(K key){
            int h;
            return (key == null) ? 0 : Math.abs((h = key.hashCode())) ^ (h >>> 16);
        }
    
        @Override
        public V put(K key, V value) {
            // 确定index
            int index = hash(key) % initCapacity;
            if(table[index] != null){
                Entry<K, V> e = table[index];
                Entry<K, V> e2 = null;
                while(e != null){
                    if(hash(e.key) == hash(key) && e.key.equals(key)){
                        // 如果键相同，则更新值
                        e.value = value;
                    }
                    // 遍历链表判断是否已经存在相同的key
                    e2 = e;
                    e = e.next;
                }
                // 如果不存在相同的key，则直接插到尾结点的后面
                e2.next = new Entry<>(key, value, null, index);
            }else{
                // 如果table[index]处为空，则直接插入
                Entry<K, V> e = new Entry<>(key, value, null, index);
                table[index] = e;
            }
            return value;
        }
    
        @Override
        public V get(K key) {
            // 根据key，计算下标index
            int index = hash(key) % initCapacity;
            Entry<K, V> e = table[index];
            if(e == null){
                return null;
            }
    
            // 遍历index处的链表找到key
            while(e != null){
                if(e.key == null && key == null || hash(e.key) == hash(key) && e.key.equals(key)){
                    return e.value;
                }
                e = e.next;
            }
            return null;
        }
    
        // HashMap中存储节点信息的数据结构
        class Entry<K, V> implements MyMap.Entry<K, V>{
            K key;
            V value;
            Entry<K, V> next;
            int index;  // 记录下标
    
            Entry(K key, V val, Entry<K, V> next, int index){
                this.key = key;
                this.value = val;
                this.next = next;
                this.index = index;
            }
    
            @Override
            public K getKey() {
                return key;
            }
    
            @Override
            public V getValue() {
                return value;
            }
    
            public Entry<K, V> getNext() {
                return next;
            }
        }
    }

### 第 3 步：测试 ###

public class TestMyHashMap {
    
        public static void main(String[] args) {
    
            MyMap<String, Object> map = new MyHashMap<>();
            map.put("name", "zuozhen");
            map.put("age", 23);
            map.put("weight", 75);
            map.put(null, "zuozhen2");
    
            System.out.println(map.get("name"));
            System.out.println(map.get("age"));
            System.out.println(map.get("weight"));
            System.out.println(map.get(null));
    
            map.put("name", "zuozhen1");
            System.out.println(map.get("name"));
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20211214/5b3e6eb1c61744768ab09a3e1fbac092.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20211214/5f9cabffd5654ca99ce11febf5325c53.png