[leetcode] 706. Design HashMap

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 ListNode:
    def __init__(self, key = None, value = None):
        self.key = key 
        self.value = value 
        self.next = None

class MyHashMap(object):

    def __init__(self):
        self.size = 1000 
        self.table = collections.defaultdict(ListNode)

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        index = key % self.size 
        # 인덱스에 노드가 없다면 삽입 후 종료 
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return 

        # 인덱스에 노드가 존재하는 경우 연결 리스트 처리 
        p = self.table[index]
        while p : 
            if p.key == key:
                p.value = value 
                return 
            if p.next is None: 
                break
            p = p.next
        p.next = ListNode(key, value)

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        index = key % self.size 
        if self.table[index].value is None:
            return -1 

        # 노드가 존재할 때 일치하는 키 탐색 
        p = self.table[index]
        while p:
            if p.key == key:
                return p.value 
            p = p.next 

        return -1 
        
    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        index = key % self.size 
        if self.table[index].value is None:
            return
        
        # 인덱스의 첫번째 노드일때 삭제 처리 
        p = self.table[index]
        if p.key == key:
            self.table[index] = ListNode() if p.next is None else p.next 
            return 

        # 연결 리스트 노드 삭제 
        prev = p 
        while p:
            if p.key == key:
                prev.next = p.next 
                return 
            prev, p = p, p.next 
            
        


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