面试题答案
一键面试Go语言map底层数据结构
- 主要组成部分
- hmap:这是map的整体结构。它包含了一些关键信息,如元素个数(count)、用于哈希计算的种子(hash0)、桶数组(buckets)等。
- bucket:用于实际存储键值对。每个bucket可以存储多个键值对。
- 各部分作用
- hmap的count:记录map中当前存储的键值对数量。
- hmap的hash0:作为哈希函数的种子,用于计算键的哈希值,增加哈希的随机性和分布均匀性。
- hmap的buckets:是一个指向bucket数组的指针。在map初始化时,buckets为空,随着键值对的插入,会动态分配bucket空间。
- 桶(bucket)的设计
- bucket结构:一个bucket结构体包含多个槽位(一般为8个),每个槽位可以存储一个键值对。
- 键值对存储:键和值在bucket中是分开存储的,先存储键,然后存储对应的值。这样设计可以更高效地利用内存,因为不同类型的键和值可以按照自己的对齐方式存储。
- 溢出桶:当一个bucket的8个槽位都被占用时,如果再有新的键值对要插入,就会使用溢出桶(overflow bucket)。溢出桶和普通bucket结构相同,通过链表的形式连接到已满的bucket,从而允许map存储更多的键值对。
- 键值对存储方式
- 哈希计算:当插入一个键值对时,先根据键计算其哈希值(使用hash0作为种子)。
- 定位bucket:哈希值的低位用于定位到具体的bucket。
- 查找槽位:在bucket内,通过哈希值的高位在槽位中查找合适的位置存储键值对。如果槽位已被占用且键不相等,就会寻找下一个可用槽位或使用溢出桶。在查找键值对时,同样通过哈希值计算来快速定位到可能存储该键的bucket,然后在bucket及其溢出桶中遍历查找键,找到后返回对应的值。