知识卡片
Map桶化存储
哈希表用哈希值把键映射到存储位置,遇到碰撞还要继续定位并比较具体键。哈希质量、装载程度和碰撞处理方式共同影响访问成本;平均 O(1) 不是每次访问的保证。Go map 的具体分组与扩容结构会随运行时版本变化。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 哈希表与Go语言实现机制 · 查看原书依据
Go语言中的map又被称为哈希表,是使用频率极高的一种数据结构。哈希表的原理是将多个键/值(key/value)对分散存储在buckets(桶)中。给定一个键(key),哈希(Hash)算法会计算出键值对存储的位置
参考来源
- 位置:《Go语言底层原理剖析》第8章《哈希表与Go语言实现机制》开篇 与 8.1节《哈希碰撞与解决方法》
- 结论依据:原文定义哈希表把键值对分散存储、按键的哈希值定位,并说明不同键可能碰撞,因此支持“一次哈希定位并不等于找到唯一键”的通用结论。原书对 Go 具体碰撞实现的说明与后文溢出桶描述相冲突,且 Go 1.24 已采用新 map 实现;本卡不据其线性探测叙述推导实现细节。
- 原始内容:Go语言中的map又被称为哈希表,是使用频率极高的一种数据结构。哈希表的原理是将多个键/值(key/value)对分散存储在buckets(桶)中。给定一个键(key),哈希(Hash)算法会计算出键值对存储的位置……哈希函数在实际中遇到的最常见问题是哈希碰撞(Hash Collision),即不同的键通过哈希函数可能产生相同的哈希值。