OOD - Design HashMap

info

HashMap 和 HashSet 的区别是 HashMap 保存的每个元素 key-value 对，而 HashSet 保存的是某个元素 key 是否出现过。所以我们把 HashSet 稍作改进即可。

HashMap 是在 时间和空间 上做权衡的经典例子：如果不考虑空间，我们可以直接设计一个超大的数组，使每个 key 都有单独的位置，则不存在冲突；如果不考虑时间，我们可以直接用一个无序的数组保存输入，每次查找的时候遍历一次数组。

为了时间和空间上的平衡，HashMap 基于数组实现，并通过 hash 方法求键 key 在数组中的位置，当 hash 后的位置存在冲突的时候，再解决冲突。

Leetcode 例题 706

Constraints and assumptions

• For simplicity, are the keys integers only? Yes
• For collision resolution, can we use chaining? Yes
• Do we have to worry about load factors? No
• Can we assume inputs are valid or do we have to validate them? Assume they're valid
• Can we assume this fits memory? Yes

Solution

Java Implementation

class MyHashMap {
    int size;
    Node[] buckets;
    
    private class Node{
        int key;
        int val;
        Node next;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    public MyHashMap() {
        size = 10001;
        buckets = new Node[size];
    }
    
    public int hashing(int key) {
        return Integer.hashCode(key);
    }
    
    public int getIndex(int hash) {
        int n = buckets.length;
        return hash & (n - 1);
    }
    
    public void put(int key, int value) {
        int hash = hashing(key);
        int index = getIndex(hash);
        
        if (buckets[index] == null) {
            buckets[index] = new Node(-1, -1);
        }

		Node node = getNode(index, key);
		if (node.next == null)
			node.next = new Node(key, value);
		else 
			node.next.val = value;
    }
    
    public int get(int key) {
        int hash = hashing(key);
        int index = getIndex(hash);
        
        Node node = getNode(index, key);
        return node.next == null ? -1 : node.next.val;
    }
    
    public void remove(int key) {
        int hash = hashing(key);
        int index = getIndex(hash);
        
        Node node = getNode(index, key);
        if (node.next != null) {
		    node.next = node.next.next;   
        }
    }
    
    public Node getNode(int index, int key) {
        // bad case        
        if (buckets[index] == null) {
            buckets[index] = new Node(-1, -1);
        }
        
        Node node = buckets[index];

        while (node.next != null && node.next.key != key) {
            node = node.next;
        }
        
        return node;
    }
}

/**
 * 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);
 */

class MyHashMap:
    '''
    time: O(n/b)
    space: O(n)
    '''
    def __init__(self):
        self.buckets = 1009
        self.table = [[] * self.buckets for _ in range(self.buckets)]

    def hash(self, key: int) -> int:
        return key % self.buckets

    def put(self, key: int, value: int) -> None:
        hashkey = self.hash(key)
        for item in self.table[hashkey]:
            if item[0] == key:
                item[1] = value
                return
        self.table[hashkey].append([key, value])

    def get(self, key: int) -> int:
        hashkey = self.hash(key)
        for item in self.table[hashkey]:
            if item[0] == key:
                return item[1]
        return -1

    def remove(self, key: int) -> None:
        hashkey = self.hash(key)
        for i, item in enumerate(self.table[hashkey]):
            if item[0] == key:
                del self.table[hashkey][i]
                return



# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)