英文:
How to retrieve values from hashtable after resolving collision using linear probing?
问题
我正在尝试在Go语言中实现一个哈希程序，我使用线性探测法进行插入和解决冲突。当我尝试检索值时，由于我使用了线性探测法来修复冲突，所以得到的值可能会不同。
这是我的程序：https://play.golang.org/p/7Pmqu6A313
英文:
I am trying to implement a hash program in go, I did insertion and resolved collisions using linear probing. When I'm trying to retrieve values back, i'm getting different values as I used linear probing to fix collisions.
This is my program : https://play.golang.org/p/7Pmqu6A313
答案1
得分: 6
你的解决方案中存在的问题是，你在插入操作中使用了"线性探测"，但在检索操作中没有使用相同的方法。
首先，我会更改你的底层存储方式，将整个结构体作为值存储起来：
var hasharray [15]Item
其次，我会更改检索方法，通过计算哈希索引来检查项目的值，然后逐个迭代项目以找到实际的项目（如果存在冲突）：
func retrieve(key string) {
index := hashmethod(key)
found := false
for !found {
item := hasharray[index]
if key == item.key {
found = true
fmt.Println(index, item)
} else if index != size-1 {
index++
} else {
index = 0
}
}
}
请参考这里的代码：https://play.golang.org/p/8JfTpbJcWx
英文:
The problem in your solution is that you are using "linear probing" for insert operation, but you are not using the same approach for retrieving it.
First of all - I would change your underlining storage to keep whole struct instead of value:
var hasharray [15]Item
Second, I would change the retrieve method to check value of the item with calculated hash index, and after that iterate items one by one to find actual item if there was a collision:
func retrieve(key string) {
index := hashmethod(key)
found := false
for !found {
item:= hasharray[index];
if key == item.key {
found = true;
fmt.Println(index, item)
} else if index != size-1 {
index++
} else {
index = 0
}
}
}
See here: https://play.golang.org/p/8JfTpbJcWx
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论