Design a hashtable

706. Design HashMap

double linked list

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = self.next = None
class DLinkedList:
    def __init__(self):
        self.len = 0
        self.dummy = Node(-1, -1)
        self.dummy.prev = self.dummy.next = self.dummy
    def __len__(self):
        return self.len
    def find(self, key):
        node = self.dummy
        while True:
            node = node.next
            if node == self.dummy:
                return None
            if key == node.key:
                return node
     
    def put(self, key, val):
        node = self.find(key)
        if node is None:
            new_node = Node(key, val)
            self.dummy.next.prev = new_node
            new_node.next = self.dummy.next
            self.dummy.next = new_node
            new_node.prev = self.dummy
            self.len += 1
        else:
            node.val = val
    def get(self, key):
        node = self.find(key)
        if node is None:return -1
        return node.val
    def remove(self, key):
        node = self.find(key)
        if node is None:return
        node.prev.next = node.next
        node.next.prev = node.prev
        self.len -= 1
    
class MyHashMap:
def __init__(self):
        """
        Initialize your data structure here.
        """
        self.capacity = 9521
        self.hashtable = [DLinkedList()]*self.capacity
def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """
        hashkey = key%self.capacity
        self.hashtable[hashkey].put(key, value)
def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        """
        hashkey = key%self.capacity
        return self.hashtable[hashkey].get(key)
def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        """
        hashkey = key%self.capacity
        return self.hashtable[hashkey].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)

This one is running slow

Runtime: 7920 ms, faster than 5.05% of Python3 online submissions for Design HashMap.
Memory Usage: 19.9 MB, less than 21.40% of Python3 online submissions for Design HashMap.

single linked list

class LinkedList:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
class MyHashMap:
def __init__(self):
        """
        Initialize your data structure here.
        """
        self.capacity = 9851
        self.hashtable = [None]*self.capacity
def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """
        i = key%self.capacity
        if self.hashtable[i] is None:
            self.hashtable[i] = LinkedList(key,value)
            return
        node = self.hashtable[i]
        while node:
            if node.key==key:
                node.val=value
                return
            if node.next is None:
                node.next = LinkedList(key,value)
                return
            node = node.next
def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        """
        i = key%self.capacity
        if self.hashtable[i] is None:return -1
        node = self.hashtable[i]
        while node:
            if node.key==key:return node.val
            node = node.next
        return -1
def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        """
        i = key%self.capacity
        if self.hashtable[i] is None:return
        prev, curr = self.hashtable[i], self.hashtable[i].next
        if prev.key==key:
            prev.next=None
            self.hashtable[i] = curr
            return
        while curr:
            if curr.key==key:
                prev.next = curr.next
                prev.next=None
                return
            prev, curr = curr, curr.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)

Another implementation

class LinkedListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
class MyHashMap:
def __init__(self):
        """
        Initialize your data structure here.
        """
        self.capacity = 9521
        self.hashtable = [None]*self.capacity
def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """
        hashkey = key%self.capacity
        if self.hashtable[hashkey] is None:
            self.hashtable[hashkey] = LinkedListNode(key, value)
            return
        node = self.hashtable[hashkey]
        while node:
            if node.key == key:
                node.val = value
                return
            if node.next is None:
                new_node = LinkedListNode(key, value)
                node.next = new_node
                return 
            node = node.next
def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        """
        hashkey = key%self.capacity
        if self.hashtable[hashkey] is None:
            return -1
        node = self.hashtable[hashkey]
        while node:
            if node.key == key:
                return node.val
            if node.next is None:
                return -1
            node = node.next
def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        """
        hashkey = key%self.capacity
        if self.hashtable[hashkey] is None:
            return
        node = self.hashtable[hashkey]
        if node.key == key:
            self.hashtable[hashkey] = node.next
            return
        while node:
            if node.next is not None and node.next.key == key:
                node.next = node.next.next
                return
            if node.next is None:
                return
            node = node.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)

This one is pretty fast

Runtime: 208 ms, faster than 87.20% of Python3 online submissions for Design HashMap.
Memory Usage: 17.3 MB, less than 37.41% of Python3 online submissions for Design HashMap.