《零基础Go语言算法实战》【题目 4-10】在不使用任何内置散列表库的情况下设计一个 HashMap
《零基础Go语言算法实战》
【题目 4-10】在不使用任何内置散列表库的情况下设计一个 HashMap
请实现一个 HashMap 类，该类的方法如下。
● HashMap() ：使用空映射初始化对象。
● void Put(int key, int value) ：将键值对插入到 HashMap 中。如果键已经存在于映射中，
则更新相应的值。
● int Get(int key) ：返回指定键映射到的值，如果此映射不包含键的映射，则返回 -1。
● void Remove(key) ：如果映射包含键的映射，则删除键及其对应的值。
【解答】
① 思路。
根据题意，通过散列表思想编写 HashMap 对象即可。
② Go 语言实现。
package main
import "fmt"
const (
mod = 1024
)
type HashMap struct {
set [mod]*listNode
}
type listNode struct {
key int
val int
next *listNode
}
// 初始化数据结构
func Constructor() HashMap {
arr := [mod]*listNode{}
return HashMap{set: arr}
}
func (hm *HashMap) Put(key int, value int) {
i := key % mod
ptr := hm.set[i]
for ptr != nil {
if ptr.key == key {
ptr.val = value
return
} else {
ptr = ptr.next
}
}
node := &listNode{key: key, val: value, next: hm.set[i]}
hm.set[i] = node
}
// 返回指定键映射到的值，如果不包含键的映射，则返回 -1
func (hm *HashMap) Get(key int) int {
ptr := hm.set[key%mod]
for ptr != nil {
if ptr.key == key {
return ptr.val
} else {
ptr = ptr.next
}
}
return -1
}
// 如果 HashMap 映射包含键的映射，则删除键及其对应的值
func (hm *HashMap) Remove(key int) {
i := key % mod
ptr := hm.set[i]
prev := &listNode{next: ptr}
head := prev
for ptr != nil {
if ptr.key == key {
prev.next = ptr.next
break
} else {
prev = prev.next
ptr = ptr.next
}
}
hm.set[i] = head.next
}
func main() {
obj := Constructor()
obj.Put(1, 1)
obj.Put(2, 2)
res1 := obj.Get(1)
fmt.Println(res1)
res2 := obj.Get(2)
fmt.Println(res2)
obj.Remove(2)
}
//$ go run interview4-10.go
//1
//2