知识卡片
Map桶化存储
内容
Go map 用哈希把键值分散到桶中,桶内再处理碰撞。哈希质量、负载因子和桶溢出共同决定访问成本;平均 O(1) 是统计承诺,不是每次访问的保证。
参考来源
- 位置:《Go语言底层原理剖析》第8章《哈希表与Go语言实现机制》开篇 与 8.1节《哈希碰撞与解决方法》
- 结论依据:原文定义"哈希表的原理是将多个键/值(key/value)对分散存储在buckets(桶)中……哈希(Hash)算法会计算出键值对存储的位置",并说明哈希碰撞不可避免(如2450个键随机分配到一百万个桶,至少两个键同桶的概率高达95%),Go 采用开放寻址法中的线性探测策略解决碰撞,因此可以推出"map 用哈希把键值分散到桶中、桶内/桶间再处理碰撞"的结论。
- 原始内容:Go语言中的map又被称为哈希表,是使用频率极高的一种数据结构。哈希表的原理是将多个键/值(key/value)对分散存储在buckets(桶)中。给定一个键(key),哈希(Hash)算法会计算出键值对存储的位置……哈希函数在实际中遇到的最常见问题是哈希碰撞(Hash Collision),即不同的键通过哈希函数可能产生相同的哈希值……Go语言中的哈希表采用的是开放寻址法中的线性探测(Linear Probing)策略。