写一个hashmap伪代码
时间: 2023-10-14 17:13:20 浏览: 39
```
class HashMap:
# 初始化HashMap
def __init__(self):
self.capacity = 16 #HashMap的初始容量
self.size = 0 #HashMap中元素的数量
self.buckets = [None] * self.capacity #HashMap的桶,初始值为None
# 插入元素
def put(self, key, value):
# 计算key的哈希值
hash_value = hash(key) % self.capacity
node = self.buckets[hash_value]
# 如果桶中已经有元素,则遍历链表
while node is not None:
if node.key == key:
# 如果key已经存在,则更新value
node.value = value
return
node = node.next
# 如果桶中没有元素,则在链表头插入新节点
new_node = Node(key, value)
new_node.next = self.buckets[hash_value]
self.buckets[hash_value] = new_node
self.size += 1
# 判断是否需要扩容
if self.size / self.capacity >= 0.75:
self._resize()
# 获取元素
def get(self, key):
# 计算key的哈希值
hash_value = hash(key) % self.capacity
node = self.buckets[hash_value]
# 遍历链表查找元素
while node is not None:
if node.key == key:
return node.value
node = node.next
# 如果没有找到,则返回None
return None
# 删除元素
def remove(self, key):
# 计算key的哈希值
hash_value = hash(key) % self.capacity
node = self.buckets[hash_value]
prev_node = None
# 遍历链表查找元素
while node is not None:
if node.key == key:
# 如果找到元素,则删除节点
if prev_node is None:
self.buckets[hash_value] = node.next
else:
prev_node.next = node.next
self.size -= 1
return
prev_node = node
node = node.next
# 扩容
def _resize(self):
self.capacity *= 2 #容量翻倍
new_buckets = [None] * self.capacity #新桶
# 将旧桶中的元素重新哈希到新桶中
for i in range(len(self.buckets)):
node = self.buckets[i]
while node is not None:
hash_value = hash(node.key) % self.capacity
new_node = Node(node.key, node.value)
new_node.next = new_buckets[hash_value]
new_buckets[hash_value] = new_node
node = node.next
self.buckets = new_buckets
```
注:Node为链表节点,包含key和value两个属性,以及next指针指向下一个节点。