1.问题

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

0 <= key, value <= 106
At most 104 calls will be made to put, get, and remove.

2. 解题思路

方法1：

1.定义arr数组
2.arr的数组长度为1000000+1 （0 <= key <= 106），将数组值填充为-1；
3.arr的key为value
4.取出key的value值
5.将key的value值设定为-1

方法2：

使用链表的方式

3. 代码

代码1：

class MyHashMap {
    int[] arr;//1.定义arr数组
    public MyHashMap() {
        arr=new int[1000000+1];//2.arr的数组长度为1000000+1 （0 <= key <= 106），将数组值填充为-1；
        Arrays.fill(arr,-1);
    }
    public void put(int key, int value) {
    //3.arr的key为value
        arr[key]=value;            
    }
    public int get(int key) {
     //4.取出key的value值  
         return arr[key];
    }
    public void remove(int key) {
    //5.将key的value值设定为-1 
        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);
 */

代码2：

class MyHashMap{
        final ListNode[] nodes = new ListNode[10000];//1.10000 calls will be made to put, get, and remove.因此新建ListNode的数组
        public void put(int key, int value){
            int i = idx(key);
            if(nodes[i] == null)
                nodes[i] = new ListNode(-1, -1);
            ListNode prev = find(nodes[i], key);
            if(prev.next == null)
                prev.next = new ListNode(key, value);
            else prev.next.val = value;
        }
        public int get(int key){
            int i = idx(key);
            if(nodes[i] == null)
                return -1;
            ListNode node = find(nodes[i], key);
            return node.next == null ? -1 : node.next.val;
        }
        public void remove(int key){
            int i = idx(key);
            if(nodes[i] != null){
                ListNode prev = find(nodes[i], key);
                if(prev.next != null)
                    prev.next = prev.next.next;
            }
        }
        int idx(int key){
    return Integer.hashCode(key) % nodes.length;}
        ListNode find(ListNode bucket, int key){
            ListNode node = bucket, prev = null;
            for(; node != null && node.key != key; node = node.next)
                prev = node;
            return prev;
        }
        class ListNode{
            int key, val;
            ListNode next;
            ListNode(int key, int val){
                this.key = key;
                this.val = val;
            }
        }
    }

以上的解题思路基本相同

class MyHashMap
{
    ListNode[] nodes = new ListNode[10000];//1.10000 calls will be made to put, get, and remove.因此新建ListNode的数组
    public int get(int key)
    {
        int index = getIndex(key);//获取当前值的索引位置
        ListNode prev = findElement(index, key);//
        return prev.next == null ? -1 : prev.next.val;
    }
    public void put(int key, int value)//从key中得到索引值，并查询结点，如果没有则添加新的结点
    {
        int index = getIndex(key);
        ListNode prev = findElement(index, key);
        if (prev.next == null)
            prev.next = new ListNode(key, value);
        else 
            prev.next.val = value;
    }
    public void remove(int key)//从key中得到索引值，并查询结点，如果有则删除结点
    {
        int index = getIndex(key);
        ListNode prev = findElement(index, key);
        if(prev.next != null)
            prev.next = prev.next.next;
    }
    private int getIndex(int key)//获取当前值的索引位置
    {
        return Integer.hashCode(key) % nodes.length;
    }
    private ListNode findElement(int index, int key)//查找元素
    {
        if(nodes[index] == null)//如果索引的值为null，链表的索引和值为-1
            return nodes[index] = new ListNode(-1, -1);
        ListNode prev = nodes[index];
        while(prev.next != null && prev.next.key != key)//当prev.next != null && prev.next.key != key，查找元素
        {
            prev = prev.next;
        }
        return prev;
    }
    private static class ListNode
    {
        int key, val;
        ListNode next;
        ListNode(int key, int val)
        {
            this.key = key;
            this.val = val;
        }
    }
}