用 Python 设计 HashMap
pythonserver side programmingprogramming更新于 2023/11/10 0:30:00
假设我们想设计一个 HashMap，而不使用任何内置哈希表库。将有以下不同的函数 −
- put(key, value) − 这会将与 key 关联的值插入到 HashMap 中。如果该值已存在于 HashMap 中，则更新该值。
- get(key) − 这会返回指定 key 映射到的值，否则当此映射不包含 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 的新数据结构，并初始化它，将有一些字段 like(key, val, next) ，next 最初为 null
- 定义一个链表，有以下几个方法 −
- 定义一个初始化器，它将按如下方式工作 −
- prehead := 一个新节点 Node，其中 key = null 且 val = null
- 定义一个函数 search()。这将获取 key
- p := prehead.next
- 当 p 不为 null 时，执行
- 如果 p.key 与 key 相同，则
- 返回 p
- p := p.next
- 如果 p.key 与 key 相同，则
- 返回 None
- 定义一个函数 add()。这将采用 key, val
- p := search(key)
- 如果 p 不为空，则
- p.val := val
- 否则，
- node := new Node with (key, val)
- prehead.next := node, node.next := prehead.next
- 定义一个函数 get()。这将获取 key
- p := search(key)
- 如果 p 不为空，则
- 返回 p.val
- 否则，
- 返回 null
- 定义一个函数 remove。这将获取 key
- prev := prehead
- cur := prev.next
- 当 cur 不为空时，执行
- 如果 cur.key 与 key 相同，则
- 退出循环
- prev := curr, cur := cur.next
- 如果 cur 不为空，则
- prev.next := cur.next
- 如果 cur.key 与 key 相同，则
- 定义一个函数 serialize()。
- p := prehead.next
- ret := a new list
- 当 p 不为空时，执行
- 插入[p.key, p.val] 最终放入 ret 中
- p := p.next
- 返回 ret
- 从自定义哈希图中，定义如下方法 −
- 定义一个初始化器。
- size := 1033
- arr := 一个 LinkedList() 数组，其长度与 size 相同
- 定义一个函数 _hash()。这将采用 key
- 返回 key mod size
- 定义一个函数 put()。这将采用 key、value
- h := _hash(key)
- add(key, value) of arr[h]
- 定义一个函数 get()。这将获取 key
- h := _hash(key)
- ret := get(key) of arr[h]
- 如果 ret 不为空，则
- 返回 ret
- 否则，
- 返回 -1
- 定义一个函数 remove()。这将获取 key
- h := _hash(key)
- 从 arr[h] 中删除 key
让我们看看下面的实现以便更好地理解 −
示例
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
