如何写一个自己的HashMap

r囧r小猫 2022-05-12 09:06 276阅读 0赞

想必很多Java工程师出去面试的时候都会被问到HashMap的底层实现原理，很多人觉得没什么必要，反正我会用就行，就我的感觉而言，在初期确实没什么必要，但是站在公司角度想，如果面试者连底层实现都搞定了，还怕一点表层应用的东西吗？又或者说，我看到了另一个答案最能打动我：**沉下去有多深，浮上来就有多高**。

开始说一下必要的准备阶段：

1.在写自己的HashMap之初，我们需要对一定HashMap有一个初步的认识，比如HashMap底层是由数组和链表实现的，具体的结构图如图所示：

![1024555-20161113235348670-746615111.png][]

还有比如说最大容量，初始容量，加载因子，红黑树等等概念

推荐几个具体点的地址：

A.微信公众号 --- 码农翻身，搜索HashMap就有

B.[https://mubu.com/edit/mY8GnK94oi][https_mubu.com_edit_mY8GnK94oi] 幕布思维导图

C.网易云课堂搜索HashMap，有一门只要一分钱的课程，40多分钟，看完也可以有一个比较明确的了解

2.开始撸代码了

A.首先定义一个自己的Map接口，和链表接口：

public interface MyMapInterface<k,v> {
        // 大小
        int size();
        // 是否为空
        boolean isEmpty();
        // 根据key获取元素
        Object get(Object key);
        // 添加元素
        Object put(Object key,Object value);
    
        // 内部接口
        interface Entry<k,v>{
            k getKey();
            v getValue();
        }
    }

B.编写实现类：

public class MyHashMap<k,v> implements MyMapInterface {
        // 初始容量大小 --- 源码写法 1 << 4
        private final int DEFAULT_INITIAL_CAPACITY = 16;
        // 加载因子
        private final float DEFAULT_LOAD_FACTOR = 0.75f;
        // 根据定义的静态内部类，初始化链表，长度为默认长度
        Node[] table = new Node[DEFAULT_INITIAL_CAPACITY];
        // 长度
        private  int size = 0;
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public Object put(Object key, Object value) {
            // 计算key的hash值
            int hashValue = hash(key);
            // 计算出应该存放的位置
            int i = indexFor(hashValue,table.length);
            // 如果i处有数据且key一样,进行覆盖
            for(Node node = table[i];node != null; node = node.next){
                Object k;
                if(node.hash == hashValue && ((k = node.key)==key||key.equals(k))){
                    Object oldValue = node.value;
                    node.value = value;
                    return  oldValue;
                }
            }
            // 如果i位置没有数据，或i位置有数据，但key是新的key,新增节点
            addEntry(key,value,hashValue,i);
            return null;
        }
    
    
        @Override
        public Object get(Object key) {
            // 根据对象的hashcode计算hash值
            int hashValue = hash(key);
            // 根据hash值和链表长度，获取插入位置的索引
            int i = indexFor(hashValue,table.length);
            for(Node node = table[i];node != null;node = node.next){
                if(node.key.equals(key) && hashValue == node.hash){
                    return node.value;
                }
            }
            return null;
        }
    
        // 向Entry添加元素
        // hashvalue --- hash值
        // i --- 索引位置
        public void addEntry(Object key,Object value,int hashValue,int i){
            // 如果超过了数组约定长度，就扩容
            if(++size >= table.length * DEFAULT_LOAD_FACTOR){
                Node[] newTable = new Node[table.length << 1];
                // 复制数组
                //System.arraycopy(table,0,newTable,0,table.length);
                transfer(table,newTable);
                table = newTable;
            }
            // 得到i处的数据
            Node eNode = table[i];
            // 新增节点，将该节点的next指向前一个节点
            table[i] = new Node(hashValue,key,value,eNode);
        }
    
        // 引用JDK1.7的复制代码
        public void transfer(Node[] src,Node[] newTable) {         //src引用了旧的Entry数组
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
                Node e = src[j];             //取得旧Entry数组的每个元素
                if (e != null) {
                    src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                    do {
                        Node next = e.next;
                        int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                        e.next = newTable[i]; //标记[1]
                        newTable[i] = e;      //将元素放在数组上
                        e = next;             //访问下一个Entry链上的元素
                    } while (e != null);
                }
            }
        }
    
    
        // 获取插入的位置(取模运算 有瑕疵)
        public int indexFor(int hashValue,int length){
            return hashValue % length;
        }
    
        // 获取插入的位置,根据Obeject对象的hashcode 获取hash值
        public int hash(Object key){
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    
        static class Node implements MyMapInterface.Entry{
            // hash值
            int hash;
            Object key;
            Object value;
            //指向下个节点（单链表）
            Node next;
            Node(int hash,Object key,Object value,Node next){
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            @Override
            public Object getKey() {
                return key;
            }
    
            @Override
            public Object getValue() {
                return value;
            }
        }
    }

C.注释还是很清楚的，在了解了一部分基础知识的情况下，可以完全看动，至少我是这样过来的，需要说明遇到的一个坑，在写代码的初期，进行扩容操作的时候，我用的是System.arraycopy方法进行复制链表，但始终会出现莫名其妙的问题，因此我引入了JDK1.7的源码方法，transfer方法，进行一定的修改后，替换掉上面的复制方法，结果就正常了

D.测试类截图：

![70][]

如果有错误的地方，希望各位指出，需要互相交流的可以联系我，Q806857264

[1024555-20161113235348670-746615111.png]: /images/20220512/c2f2710f1f134467b763f9ee915e14fc.png
[https_mubu.com_edit_mY8GnK94oi]: https://mubu.com/edit/mY8GnK94oi
[70]: /images/20220512/5caf9d97729c49349da35cf608f4a3ca.png