题目描述

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。

注意：所有的值都在 [0, 1000000]的范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-hashmap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法思路

哈希映射的基础就是哈希集合，在【力扣日记】705 设计哈希集合的基础上随便改改就得到哈希映射了。

class MyHashMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.keyRange = 769 #确定桶的数量
        self.bucketArray = [Bucket() for i in range(self.keyRange)]

    def _hash(self, key):
        return key % self.keyRange

    def put(self, key,value):
        """
        :type key: int
        :rtype: None
        """
        bucketIndex = self._hash(key)
        self.bucketArray[bucketIndex].insert(key,value)

    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        bucketIndex = self._hash(key)
        self.bucketArray[bucketIndex].delete(key)

    def get(self, key):
        """
        Returns true if this set contains the specified element
        :type key: int
        :rtype: bool
        """
        bucketIndex = self._hash(key)
        fg= self.bucketArray[bucketIndex].exists(key)
        if fg==-1:return-1
        return fg.value


class Node:# 链表作为容器
    def __init__(self, key,value=0, nextNode=None):
        self.key=key
        self.value = value
        self.next = nextNode

class Bucket:# 桶的定义
    def __init__(self):
        # a pseudo head
        self.head = Node(0)

    def insert(self, key,newValue):
        # if not existed, add the new element to the head.
        fg=self.exists(key)
        if fg==-1:
            newNode = Node(key,newValue, self.head.next)
            # set the new head.
            self.head.next = newNode
        else:
            fg.value=newValue

    def delete(self, key):
        prev = self.head
        curr = self.head.next
        while curr is not None:
            if curr.key == key:
                # remove the current node
                prev.next = curr.next
                return
            prev = curr
            curr = curr.next

    def exists(self, key):
        curr = self.head.next
        while curr is not None:
            if curr.key == key:
                # value existed already, do nothing
                return curr
            curr = curr.next
        return -1

执行用时 :340 ms, 在所有 Python3 提交中击败了39.80%的用户
内存消耗 :17 MB, 在所有 Python3 提交中击败了100.00%的用户

最后

以上就是专注香烟为你收集整理的【力扣】706：设计哈希映射 | 数据结构题目描述算法思路的全部内容，希望文章能够帮你解决【力扣】706：设计哈希映射 | 数据结构题目描述算法思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。