Leetcode 706. Design HashMap

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Design HashMap

2. Solution

• Version 1

class MyHashMap:

    def __init__(self):
        self.maps = [[] for _ in range(1000)]


    def put(self, key: int, value: int) -> None:
        index = self.hash(key)
        self.remove(key)
        self.maps[index].append([key, value])


    def get(self, key: int) -> int:
        index = self.hash(key)
        for k, v in self.maps[index]:
            if k == key:
                return v
        return -1
        

    def remove(self, key: int) -> None:
        index = self.hash(key)
        for k, v in self.maps[index]:
            if k == key:
                self.maps[index].remove([k, v])
                break


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

• Version 2

class ListNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class MyHashMap:

    def __init__(self):
        self.maps = [None] * 1000


    def put(self, key: int, value: int) -> None:
        index = self.hash(key)

        if self.maps[index] is None:
            self.maps[index] = ListNode(key, value)
        else:
            current = self.maps[index]
            while True:
                if current.key == key:
                    current.value = value
                    break
                elif current.next is None:
                    current.next = ListNode(key, value)
                    break
                current = current.next


    def get(self, key: int) -> int:
        index = self.hash(key)
        current = self.maps[index]
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return -1


    def remove(self, key: int) -> None:
        index = self.hash(key)
        current = self.maps[index]
        if current is not None and current.key == key:
            self.maps[index] = current.next
        else:
            while current:
                if current.key == key:
                    pre.next = current.next
                    break
                pre = current
                current = current.next


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

Reference

1. https://leetcode.com/problems/design-hashmap/