知识卡片
链式哈希把冲突放入桶链
示例 HashTable 含 Table map[int]*Node 和 Size,Node 含 Value 与 Next。插入先用整数取模选桶,再令新节点 Next 指向旧桶头,最后更新桶头,因此冲突值保留在同一链上。这是作者用 Go map 搭建的教学哈希表,不是 Go 原生 map 的内部实现;本例插入不拒绝重复值。
结构图:
类图
classDiagram
class HashTable {
+Table map[int]*Node
+Size int
}
class Node {
+Value int
+Next *Node
}
HashTable --> Node : 每桶的链头
Node --> Node : Next后继
图中字段来自本章真实Go结构;箭头表示节点引用,不表示类型继承或额外线程安全保证。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.4.1 Go 语言实现哈希表 · 查看原书依据
type HashTable struct { Table map[int]*Node Size int } func hashFunction(i, size int) int { return (i % size) }
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.4.1 Go 语言实现哈希表,spine085(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.4.1.html)。
- 结论依据:按两种真实结构及 insert 的头插步骤推演。
- 原始内容:type HashTable struct { Table map[int]*Node Size int } func hashFunction(i, size int) int { return (i % size) }