用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]ofarr[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