当前位置: 首页 > 编程笔记 >

用Python设计HashMap

管和志
2023-03-14
本文向大家介绍用Python设计HashMap,包括了用Python设计HashMap的使用技巧和注意事项,需要的朋友参考一下

假设我们要设计一个HashMap而不使用任何内置的哈希表库。将有以下不同的功能-

  • put(key,value)-这会将与key关联的值插入到HashMap中。如果HashMap中已经存在该值,请更新该值。

  • get(key)-这将返回指定键所映射到的值,如果此映射不包含该键的映射,则返回-1。

  • remove(key)-如果此映射包含键的映射,则它将删除值键的映射。

因此,如果输入类似于初始化后,请按如下所示调用put和get方法-

  • put(1,1);

  • put(2,2);

  • get(1);

  • get(3);

  • put(2,1);

  • get(2);

  • remove(2);

  • get(2);

那么输出将分别为1,-1(不存在),1 -1(不存在)。

为了解决这个问题,我们将遵循以下步骤-

  • 创建一个称为node的新数据结构,并将其初始化,将有一些字段,如(key,val,next),next最初为null

  • 定义一个链表,方法如下:

  • 定义一个初始化程序,它将如下工作:

    • prehead:=一个新节点,节点为key = null,val = null

  • 定义一个功能search()。这将需要关键

  • p:= prehead.next

  • 当p不为null时,执行

    • 返回p

    • 如果p.key与key相同,则

    • p:= p.next

  • 不返回

  • 定义一个功能add()。这将需要键,val

  • p:=搜索(关键字)

  • 如果p不为null,则

    • p.val:= val

  • 除此以外,

    • node:=具有(key,val)的新节点

    • prehead.next:=节点,node.next:= prehead.next

  • 定义一个功能get()。这将需要关键

  • p:=搜索(关键字)

  • 如果p不为null,则

    • 返回p.val

  • 除此以外,

    • 返回null

  • 定义一个功能删除。这将需要关键

  • 上一页:=前置

  • cur:=上一页下一页

  • 当cur不为空时,

    • prev.next:= cur.next

    • 从循环中出来

    • 如果cur.key与key相同,则

    • 上一页:= curr,cur:= cur.next

    • 如果cur不为null,则

    • 定义一个功能serialize()

    • p:= prehead.next

    • ret:=一个新列表

    • 当p不为null时,执行

      • 在末尾插入[p.key,p.val]到ret

      • p:= p.next

    • 返回ret

    • 自定义哈希映射中,定义方法如下:

    • 定义一个初始化器。

    • 大小:= 1033

    • arr:=LinkedList()长度与大小相同的数组

    • 定义一个函数_hash()。这将需要关键

    • 返回键mod大小

    • 定义一个功能put()。这将需要关键,值

    • h:= _hash(键)

    • arr [h]的add(key,value)

    • 定义一个功能get()。这将需要关键

    • h:= _hash(键)

    • ret:= get [key] of arr [h]

    • 如果ret不为null,则

      • 返回ret

    • 除此以外,

      • 返回-1

    • 定义一个功能remove()。这将需要关键

    • h:= _hash(键)

    • 从arr [h]删除键

    让我们看下面的实现以更好地理解-

    示例

    class Node:
       def __init__(self, key, val):
          self.key = key
          self.val = val
          self.next = None
    class LinkedList:
       def __init__(self):
          self.prehead = Node(None, None)
       def search(self, key):
          p = self.prehead.next
          while p:
             if p.key == key:
                return p
             p = p.next
          return None
       def add(self, key, val):
          p = self.search(key)
          if p:
             p.val = val
          else:
             node = Node(key, val)
             self.prehead.next, node.next = node, self.prehead.next
       def get(self, key):
          p = self.search(key)
          if p:
             return p.val
          else:
             return None
       def remove(self, key):
          prev = self.prehead
          cur = prev.next
          while cur:
             if cur.key == key:
                break
             prev, cur = cur, cur.next
          if cur:
             prev.next = cur.next
       def serialize(self):
          p = self.prehead.next
          ret = []
          while p:
             ret.append([p.key, p.val])
             p = p.next
          return ret
    class MyHashMap:
       def __init__(self):
          self.size = 1033
          self.arr = [LinkedList() for _ in range(self.size)]
       def _hash(self, key):
          return key % self.size
       def put(self, key, value):
          h = self._hash(key)
          self.arr[h].add(key, value)
       def get(self, key):
          h = self._hash(key)
          ret = self.arr[h].get(key)
          if ret is not None:
             return ret
          else:
             return -1
       def remove(self, key):
          h = self._hash(key)
          self.arr[h].remove(key)
    ob = MyHashMap()ob.put(1, 1)
    ob.put(2, 2)
    print(ob.get(1))
    print(ob.get(3))
    ob.put(2, 1)
    print(ob.get(2))
    ob.remove(2)
    print(ob.get(2))

    输入值

    ob = MyHashMap()ob.put(1, 1)
    ob.put(2, 2)
    print(ob.get(1))
    print(ob.get(3))
    ob.put(2, 1)
    print(ob.get(2))
    ob.remove(2)
    print(ob.get(2))

    输出结果

    1
    -1
    1
    -1
     类似资料:
    • 问题内容: 我正在寻找使用Python给出最佳实践,设计模式和SOLID原理示例的任何资源。 问题答案: 这些重叠 Python中级和高级软件木工 像Pythonista一样的代码:惯用的Python Python成语与效率 Google美国开发人员日-Python设计模式 另一个资源是Python食谱中的示例。很多人没有遵循最佳实践,但是您可以在其中找到一些有用的模式

    • 创造模式处理一个对象的创建。创造模式的目的是为了在不按照约定而直接地创建的地方提供可选择的情况。

    • 问题内容: 您是否可以与我(和社区)分享的人对Python状态机的设计技巧? 目前,我将基于以下方面来选择引擎: 但是我敢肯定,在利用Python的动态特性(例如动态调度)的同时,有很多解决方法。 我追求的是针对“引擎”的设计技术,该技术接收与基于机器“状态”的事件和“事件”相对的“事件”和“事件”。 问题答案: 我真的不明白这个问题。该 国设计模式是相当清楚的。。 这是非常常见的样板,可用于Ja

    • 本教程解释了各种类型的设计模式及其在 Python 脚本语言中的实现。本教程将使用 Python 概念通过不同的方法和示例引导您乘坐过山车。

    • 在循环一节,我们已经讨论了 Python 基本的循环语法。这一节,我们将接触更加灵活的循环方式。 range() 在Python中,for循环后的in跟随一个序列的话,循环每次使用的序列元素,而不是序列的下标。 之前我们已经使用过range()来控制for循环。现在,我们继续开发range的功能,以实现下标对循环的控制: S = 'abcdefghijk' for i in range(0,len

    • 常规属性 用户名 定义用户帐号的名。 密码 指定用户的登录密码。 确认密码 重新输入登录密码。 密码摘要 指示服务器或客户端是否摘要密码。 机制 指定用于创建 SCRAM 用户凭据的 SCRAM 机制。 自定义数据 在此选项卡中,你可以输入与此用户关联的任何信息。 内置角色 在列表中,指定此用户成为已选择的内置角色的成员。 用户定义角色 在列表中,指定此用户成为已选择的用户定义角色的成员。 验证限