用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