Python 中设计 HashMap

假设我们想在不使用任何内置哈希表库的情况下设计一个 HashMap。将包含以下不同的函数：

• put(key, value) - 这会将与键关联的值插入到 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 := 一个新的节点 Node，其中 key = null，val = null
• 定义一个函数 search()。这将采用键。
• p := prehead.next
• 当 p 不为 null 时，执行以下操作：
  • 如果 p.key 与 key 相同，则
    • 返回 p
  • p := p.next
• 返回 None
• 定义一个函数 add()。这将采用键和值。
• p := search(key)
• 如果 p 不为 null，则
  • p.val := val
• 否则，
  • node := 一个新的节点，包含 (key, val)
  • prehead.next := node，node.next := prehead.next
• 定义一个函数 get()。这将采用键。
• p := search(key)
• 如果 p 不为 null，则
  • 返回 p.val
• 否则，
  • 返回 null
• 定义一个函数 remove。这将采用键。
• prev := prehead
• cur := prev.next
• 当 cur 不为 null 时，执行以下操作：
  • 如果 cur.key 与 key 相同，则
    • 退出循环
  • prev := curr，cur := cur.next
  • 如果 cur 不为 null，则
    • prev.next := cur.next
• 定义一个函数 serialize()。
• p := prehead.next
• ret := 一个新的列表
• 当 p 不为 null 时，执行以下操作：
  • 将 [p.key, p.val] 插入到 ret 的末尾
  • p := p.next
• 返回 ret
• 从自定义哈希映射中，定义以下方法：
• 定义一个初始化器。
• size := 1033
• arr := 一个 LinkedList 数组，其长度与 size 相同
• 定义一个函数 _hash()。这将采用键。
• 返回 key mod size
• 定义一个函数 put()。这将采用键和值。
• h := _hash(key)
• arr[h] 的 add(key, value)
• 定义一个函数 get()。这将采用键。
• h := _hash(key)
• ret := arr[h] 的 get(key)
• 如果 ret 不为 null，则
  • 返回 ret
• 否则，
  • 返回 -1
• 定义一个函数 remove()。这将采用键。
• h := _hash(key)
• 从 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

Arnab Chakraborty

更新于：2020年7月4日

2K+ 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始