这是悦乐书的第299次更新，第318篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第167题（顺位题号是706）。在不使用任何内置哈希表库的情况下设计HashMap。具体而言，你的设计应包括以下功能：
put（key，value）：将一个（key，value）对插入HashMap。如果该值已存在于HashMap中，请更新该值。
get（key）：返回指定键映射到的值，如果此映射不包含键的映射，则返回-1。
remove（key）：如果此映射包含键的映射，则删除值键的映射。
例如：MyHashMap hashMap = new MyHashMap（）;
hashMap.put（1,1）;
hashMap.put（2,2）;
hashMap.get（1）; //返回1
hashMap.get（3）; //返回-1（未找到）
hashMap.put（2,1）; //更新现有值
hashMap.get（2）; //返回1
hashMap.remove（2）; //删除2的映射
hashMap.get（2）; //返回-1（未找到）
注意：所有key和value都将在[0,1000000]范围内。
操作次数将在[1,10000]范围内。
请不要使用内置的HashMap库。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
为了实现键值对的效果，内层使用了二维数组，外层使用ArrayList。其中二维数组是一个一行两列的结构，第一行第一列存储key的值，第一行第二列存储value的值。另外，我们还需要单独写一个contains方法，来判断当前的key是否存在于HashMap中。
put方法的时间复杂度为O(n)，get方法的时间复杂度为O(n)，remove的时间复杂度为O(n)，contains方法的时间复杂度为O(n)。
class MyHashMap { List list; /** Initialize your data structure here. */ public MyHashMap() { list = new ArrayList (); } /** value will always be non-negative. */ public void put(int key, int value) { if (contains(key)) { for (int[][] arr : list) { if (arr != null && arr[0][0] == key) { arr[0][1] = value; break; } } } else { list.add(new int[][]{ {key, value}}); } } public boolean contains(int key){ for (int[][] arr : list) { if (arr != null && arr[0][0] == key) { return true; } } return false; } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { for (int[][] arr : list) { if (arr != null && arr[0][0] == key) { return arr[0][1]; } } return -1; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { if (contains(key)) { for (int i=0; i 03 第二种解法
我们也可以使用一个小track，依旧使用数组，但是变成了一维数组，因为题目给定了key和value的范围，所以数组的容量为其最大范围加1。因为最小值可以为0，而数组默认值是0，避免误判，将数组的初始值全部赋值为-1。
put方法的时间复杂度为O(1)，get方法的时间复杂度为O(1)，remove的时间复杂度为O(1)，但是空间复杂度较高。
class MyHashMap { int[] arr; /** Initialize your data structure here. */ public MyHashMap() { arr = new int[1000001]; Arrays.fill(arr, -1); } /** value will always be non-negative. */ public void put(int key, int value) { arr[key] = value; } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { return arr[key]; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { arr[key] = -1; }}/** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */ 04 第三种解法
使用单链表，此解法是参考至讨论区。传送门：
class MyHashMap { /** Initialize your data structure here. */ ListNode[] nodes; public MyHashMap() { nodes = new ListNode[10000]; } /** value will always be non-negative. */ public void put(int key, int value) { int idx = key%10000; if(nodes[idx]==null){ nodes[idx] = new ListNode(-1,-1); nodes[idx].next = new ListNode(key,value); }else{ ListNode pre = find(nodes[idx], key); if(pre.next == null){ pre.next = new ListNode(key, value); }else{ pre.next.value = value; } } } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { int idx = key%10000; if(nodes[idx] == null) return -1; else{ ListNode pre = find(nodes[idx], key); if(pre.next == null) return -1; else return pre.next.value; } } public ListNode find(ListNode root, int key){ ListNode pre = null; ListNode cur = root; while(cur!=null && cur.key != key){ pre = cur; cur = cur.next; } return pre; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { int idx = key%10000; if(nodes[idx] == null) return; else{ ListNode pre = find(nodes[idx], key); if(pre.next == null) return; else{ pre.next = pre.next.next; } } } class ListNode{ int key; int value; ListNode next; ListNode(int key, int value){ this.key = key; this.value = value; } }}/** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */ 05 小结
算法专题目前已日更超过四个月，算法题文章167+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！