用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