目录题目描述思路分析AC 代码题目描述 706. 设计哈希映射 不使用任何内建的哈希表库设计一个哈希映射(HashMap)。 实现 MyHashMap 类: MyHashMap(
706. 设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射(HashMap)。
实现 MyHashMap 类:
示例:
输入:
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出:
[null, null, null, 1, -1, null, 1, null, -1]
解释:
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ,myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1(未找到),myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]](更新已有的值)
myHashMap.get(2); // 返回 1 ,myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据,myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1(未找到),myHashMap 现在为 [[1,1]]
提示:
type MyHashMap struct {
data []*node // 切片+链表构成散列表
cap int // 容量
}
// 链表节点
type Node struct {
k int
v int
next *Node
}
func Constructor() MyHashMap {
return MyHashMap{
data: make([]*Node, 1000),
cap: 1000,
}
}
func (this *MyHashMap) Put(key int, value int) {
index := key % this.cap
// put时有三种Case:
// 1.槽不存在,直接新创建一个槽添加该元素
// 2.槽存在且已经包含该元素,修改元素值,由于元素是值拷贝方式,需要重新赋值回去才能生效
// 3.槽存在但不包含该元素,追加元素
node := this.data[index]
if node == nil {
this.data[index] = &Node{key, value, nil}
return
}
for {
if node.k == key {
node.v = value
return
}
if node.next == nil {
node.next = &Node{key, value, nil}
return
}
node = node.next
}
}
func (this *MyHashMap) Get(key int) int {
node := this.data[key % this.cap]
for node != nil {
if node.k == key {
return node.v
}
node = node.next
}
return -1
}
func (this *MyHashMap) Remove(key int) {
node := this.data[key % this.cap]
var pre *Node
for node != nil {
if node.k == key {
break
}
pre, node = node, node.next
}
// 未找到待删除元素
if node == nil {
return
}
// 如果找到元素,有两种情况:
// 1.待删除元素是头节点,需要将新的头节点更新到散列表中
// 2.待删除元素是普通节点,则直接让前驱节点指向下一个节点
if pre == nil {
this.data[key % this.cap] = node.next
}else {
pre.next = node.next
}
}
以上就是Go语言LeetCode题解706设计哈希映射的详细内容,更多关于Go语言设计哈希映射的资料请关注编程网其它相关文章!
--结束END--
本文标题: Go语言LeetCode题解706设计哈希映射
本文链接: https://www.lsjlt.com/news/176122.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0