手写一个简单的HashMap

实现一个简单的HashMap

朋友面试，遇到了一个问题，在没有提供HashMap API的情况下，怎么实现一个HashMap

这个问题，考察的无非是对HashMap的理解，考察的HashMap的底层结构

话不多说直接上图

构建思路

HashMap实现了太多的方法，我觉得在面试中不会让你一次性直接完成全部的方法，下面我们首先实现HashMap最基本的get和put方法，当然你要手撕HashMap的前提是，HashMap的源码已经了解，怎么个执行流程，如果不是请先补课。

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。

代码实现

首先定义一个MyMap接口

package com.bestrookie.mymap;

/**
 * @author : bestrookie
 * @date : 14:04 2021/5/10
 */
public interface MyMap <K,V>{
    /**
     * 向map中添加数据
     * @param key key
     * @param value value
     * @return v
     */
    V put(K key ,V value);
    V get(K key);
    /**
     * 模拟Hash中的结点
     * @param <K> key
     * @param <V> value
     */
    interface Entry<K,V>{
        /**
         * 获取key
         * @return 返回key
         */
        K getKey();
        V getValue();
    }
}

自定义一个MyHashMap类继承MyMap接口

package com.bestrookie.mymap;

/**
 * @author : bestrookie
 * @date : 14:20 2021/5/10
 */
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];
    }
    /**
     * hash计算散列 为了是散列更加均匀，减少hash冲突
     * @param key key
     * @return hash
     */
    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) {
        //计算出存储的位置（数组的索引）
        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{
            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;
        }
        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;
    }
    /**
     * 节点类
     * @param <K> key
     * @param <V> value
     */
    class Entry<K,V> implements MyMap.Entry<K,V>{
        K key;
        V value;
        Entry<K,V> next;
        int index;//记录下标
        Entry(K key, V value, Entry<K,V> next,int index){
            this.key = key;
            this.value = value;
            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;
        }
    }
}