假设我们要设计一个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