投稿
  1. 极客之音首页
  2. 其他分类
  3. 微信精选

阿里面试官叫我手写HashMap，我两分钟就给他整出来了！！！

小半 • • 微信精选 • 阅读 202


  • 前言

  • 撸起袖子开始造

    • 实现数组 + 链表

    • 实现获取Key对应数组索引的方法

    • 实现get方法

    • 实现put方法

    • 实现remove方法

    • 测试一下

  • 完整代码



前言

今天看面经看得到大厂面试题，说实话HashMap感觉真的很了解，源码看了也很多遍了，相信大部分小伙伴都能有这个程度。但是，突然给你来这么一手，还是有点懵圈！所以，今天给各位小伙伴整理一下，帮助各位掌握！


正常来说，面试时遇到手写HahsMap，基本上都是要求实现get、put方法，我就稍微全面那么一点，再加一个remove方法。

JDK7、8HashMap的get()、put()方法流程

JDK7、8HashMap扩容详解

重点掌握

手写LRU、LFU，让面试官对你刮目相看！！！

HashMap在JDK7、JDK8中不安全的地方到底在哪里？？？


好了好了，话不多说，我们开始吧。

撸起袖子开始造

实现数组 + 链表

众所周知，HashMap无论是JDK7还是JDK8，底层都是数组 + 链表，只是JDK8多了一个红黑树，按道理讲不会还有手写红黑树的吧，😰。

既然是数组 + 链表，那我就实现一个链表

参考JDK8源码阿里面试官叫我手写HashMap，我两分钟就给他整出来了！！！

我们就没必要那么高级，🤭

static class Node {
    int key, value; //保存该节点的Key、Value
    Node next; //指向下一个节点

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

链表有了，就再来个数组（面试过程基本上不要求扩容，所以我们就直接给数组定义一个差不多的值就OK了）

private final int CAPACITY = 10000;
Node[] nodes = new Node[CAPACITY];


实现获取Key对应数组索引的方法

参考源码

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key))  null ? null : e.value;
}

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


final Node<K,V> getNode(int hash, Object key) {
   Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
   if ((tab = table) != null && (n = tab.length) > 0 &&
       (first = tab[(n - 1) & hash]) != null) {
       if (first.hash  hash && // always check first node
           ((k = first.key)  key || (key != null && key.equals(k))))
           return first;
       if ((e = first.next) != null) {
           if (first instanceof TreeNode)
               return ((TreeNode<K,V>)first).getTreeNode(hash, key);
           do {
               if (e.hash  hash &&
                   ((k = e.key)  key || (key != null && key.equals(k))))
                   return e;
           } while ((e = e.next) != null);
       }
   }
   return null;
}

图示讲解（温馨提示：看不清的可以鼠标右键在新标签页打开图片哦）阿里面试官叫我手写HashMap，我两分钟就给他整出来了！！！

实现

因为int为基本数据类型，所以我们用Integer.hashCode(int value)

而Integer.hashCode(int value)，返回的其实就是你传入的值

public static int hashCode(int value) {
    return value;
}
private int getIndex(int key) {
    int hash = Integer.hashCode(key);
    //高16位异或低16位
    hash ^= (hash >>> 16);
    //与数组长度取模，得到对应的索引下标
    return hash % CAPACITY;
}


实现get方法

流程很简单

  1. 获取到传入的 key 的对应的索引下标
  2. 拿到对应下标对应的链表首节点
  3. 非空判断
  4. 如果链表首节点的Key是目标Key，那么直接返回对应的Value值；如果不是，那么对链表进行遍历获取，如果遍历完成都没有去返回Value值，那么说明HashMap没有这个数据，那么就返回-1.
public int get(int key) {
    int idx = getIndex(key);
    Node now = nodes[idx];

    if (now != null) {
        if (now.key  key) {
            return now.value;
        } else {
            while (now != null) {
                if (now.key  key) {
                    return now.value;
                }
                now = now.next;
            }
        }
    }

    return -1;
}

参考源码

final Node<K,V> getNode(int hash, Object key) {
 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        //如果是首节点，那么直接返回
        if (first.hash  hash && // always check first node
            ((k = first.key)  key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
			//红黑树判断不用管
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //遍历获取
            do {
                if (e.hash  hash &&
                    ((k = e.key)  key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //如果还没有就返回null值
    return null;
}


实现put方法

流程介绍

注意：我们需要保存前一个节点，这样如果put的是一个新键值对的话，我们可以获取到链表的最后一个不为null的节点

  1. 获取Key对应的索引值
  2. 非空判断，如果为空，说明该索引对应的链表为空，可直接创建新节点添加
  3. 不为空则循环遍历，遍历过程更新 prev ，如果遍历过程中找到则返回value值
  4. 如果遍历完成还没有返回，说明没有该节点可以添加，那么根据 prev 是否为null进行添加；
public void put(int key, int value) {
    int idx = getIndex(key);
    Node now = nodes[idx], tmp = now;
    
    if (tmp != null) {
        Node prev = null;
        while (tmp != null) {
            if (tmp.key  key) {
                tmp.value = value;
                return;
            }
            prev = tmp;
            tmp = tmp.next;
        }
        tmp = prev;
    }

    Node node = new Node(key, value);
    if (tmp != null) {
        tmp.next = node;
    } else {
        nodes[idx] = node;
    }
}


实现remove方法

大致流程跟get方法差不多，区别就是我们我们需要保存需要删除节点的前一个节点

 public void remove(int key) {
 	 //得到索引
     int idx = getIndex(key);
     //拿到首节点
     Node now = nodes[idx];

	 //非空判断
     if (now != null) {
     	 //保存前节点
         Node prev = null;
         //遍历查找
         while (now != null) {
             //如果找到
             if (now.key  key) {
             	 //这里有两种情况
             	 //1. 如果要删除的节点是首节点，那么直接让当前数组下标对应的首节点位为其下一个节点
             	 //2. 如果不是，那么让前一个节点的下一个节点指向当前要删除节点的下一个节点就实现了删除效果
                 if (prev != null) {
                     prev.next = now.next;
                 }else {
                     nodes[idx] = now.next;
                 }
                 //不管是怎么删除的，都让当前节点的下一个节点为null，方便垃圾挥手（加分点哦）
                 now.next = null;
                 return;
             }
             //如果没找到，让前节点指向当前节点，当前节点指向其下一个节点
             prev = now;
             now = now.next;
         }
     }
 }


测试一下

public static void main(String[] args) {
    MyHashMap map = new MyHashMap();
    map.put(1,1);
    map.put(2,2);
    map.put(1,40);
    map.put(2,200);

    System.out.println(map.get(1));
    System.out.println(map.get(2));
}
阿里面试官叫我手写HashMap，我两分钟就给他整出来了！！！
在这里插入图片描述


完整代码 

public class MyHashMap {

    static class Node {
        int key, value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int CAPACITY = 10000;
    Node[] nodes = new Node[CAPACITY];

    public void put(int key, int value) {
        int idx = getIndex(key);
        Node now = nodes[idx], tmp = now;
        if (tmp != null) {
            Node prev = null;
            while (tmp != null) {
                if (tmp.key  key) {
                    tmp.value = value;
                    return;
                }
                prev = tmp;
                tmp = tmp.next;
            }
            tmp = prev;
        }

        Node node = new Node(key, value);
        if (tmp != null) {
            tmp.next = node;
        } else {
            nodes[idx] = node;
        }
    }

    public int get(int key) {
        int idx = getIndex(key);
        Node now = nodes[idx];

        if (now != null) {
            if (now.key  key) {
                return now.value;
            } else {
                while (now != null) {
                    if (now.key  key) {
                        return now.value;
                    }
                    now = now.next;
                }
            }
        }

        return -1;
    }

    public void remove(int key) {
        int idx = getIndex(key);
        Node now = nodes[idx];

        if (now != null) {
            Node prev = null;
            while (now != null) {
                if (now.key  key) {
                    if (prev != null) {
                        prev.next = now.next;
                    }else {
                        nodes[idx] = now.next;
                    }
                    now.next = null;
                    return;
                }
                prev = now;
                now = now.next;
            }
        }
    }

    private int getIndex(int key) {
        int hash = Integer.hashCode(key);
        hash ^= (hash >>> 16);
        return hash % CAPACITY;
    }

}
阿里面试官叫我手写HashMap，我两分钟就给他整出来了！！！
在这里插入图片描述


原文始发于微信公众号（JavaCodes）：阿里面试官叫我手写HashMap，我两分钟就给他整出来了！！！

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/189319.html

赞 (0)
小半的头像小半
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！