706. Design HashMap

Easy


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.




 class Bucket:
    def __init__(self):
        self.bucket = []

    def update(self, key, val):
        found = False
        for i, kv in enumerate(self.bucket):
            if kv[0] == key:
                self.bucket[i] = (key, val)
                found = True
            if found:
                break
        if not found:
            self.bucket.append((key, val))

    def get(self, key):
        for k,v in self.bucket:
            if k == key:
                return v
        return -1


    def remove(self, key):
        for i, kv in enumerate(self.bucket):
            if kv[0] == key:
                del self.bucket[i]



class MyHashMap:

    def __init__(self):
        self.key_space = 2069
        self.hash_table = [Bucket() for i in range(self.key_space)]


    def put(self, key: int, value: int) -> None:
        hash_key = key % self.key_space
        self.hash_table[hash_key].update(key, value)

    def get(self, key: int) -> int:
        hash_key = key % self.key_space 
        return self.hash_table[hash_key].get(key)


    def remove(self, key: int) -> None:        
        hash_key = key % self.key_space 
        self.hash_table[hash_key].remove(key)


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

Random Note


  1. Effectively Using Django REST Framework Serializers
  2. How To Use DRF Serializers Effectively in Django
  3. My personal django rest framework serializer notes
  4. How to use DRF serializers effectively during write operations