#
# [817] Design HashMap
#
# https://leetcode.com/problems/design-hashmap/description/
#
# algorithms
# Easy (37.04%)
# Total Accepted:    2.8K
# Total Submissions: 7.4K
# Testcase Example:  '["MyHashMap","put","put","get","get","put","get", "remove", "get"]\n[[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]'
#
# Design a HashMap without using any built-in hash table libraries.
# 
# To be specific, your design should include these functions:
# 
# 
# put(key, value) : Insert a (key, value) pair into the HashMap. If the value
# already exists in the HashMap, update the value.
# get(key): Returns the value to which the specified key is mapped, or -1 if
# this map contains no mapping for the key.
# remove(key) : Remove the mapping for the value key if this map contains the
# mapping for the key.
# 
# 
# 
# Example:
# 
# 
# MyHashMap hashMap = new MyHashMap();
# hashMap.put(1, 1);          
# hashMap.put(2, 2);         
# hashMap.get(1);            // returns 1
# hashMap.get(3);            // returns -1 (not found)
# hashMap.put(2, 1);          // update the existing value
# hashMap.get(2);            // returns 1 
# hashMap.remove(2);          // remove the mapping for 2
# hashMap.get(2);            // returns -1 (not found) 
# 
# 
# 
# Note:
# 
# 
# All keys and values will be in the range of [0, 1000000].
# The number of operations will be in the range of [1, 10000].
# Please do not use the built-in HashMap library.
# 
# 
#
class LinkNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class MyHashMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.hash_list = [None] * 10000

    def hash(self, key):
        return key % 10000
        

    def put(self, key, value):
        """
        value will always be non-negative.
        :type key: int
        :type value: int
        :rtype: void
        """
        hash_value = self.hash(key)
        if self.hash_list[hash_value] == None:
            self.hash_list[hash_value] = LinkNode(key, value)
        else:
            ptr = self.hash_list[hash_value]
            while ptr.next != None and ptr.key != key:
                ptr = ptr.next
            if ptr.key == key:
                ptr.value = value
            else:
                ptr.next = LinkNode(key, value)

        

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        hash_value = self.hash(key)
        if self.hash_list[hash_value] == None:
            return -1
        else:
            ptr = self.hash_list[hash_value]
            while ptr != None and ptr.key != key:
                ptr = ptr.next

            if ptr == None:
                return -1
            else:
                return ptr.value

        

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: void
        """
        hash_value = self.hash(key)
        if self.hash_list[hash_value] == None:
            return
        else:
            ptr = self.hash_list[hash_value]
            if ptr.key == key:
                self.hash_list[hash_value] = ptr.next
                return

            while ptr.next != None and ptr.next.key != key:
                ptr = ptr.next
            if ptr.next == None:
                return
            elif ptr.next.key == key:
                ptr.next = ptr.next.next
            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)
