LeetCode（Linked List)706. Design HashMap

怼烎@ 2023-09-23 22:48 50阅读 0赞

# 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;
    		}
    	}
    }