跳过正文
  1. 全部/
  2. 笔记/
  3. 面试/
  4. golang/
  5. 原理/

Map

目录

哈希表的原理是将多个k-v键值对散列的存储在buckets中,buckets可以理解为一个连续的数组,所以给定一个key/value键值对,我们要将其存储到合适的位置需要经过两步骤:

  1. 计算hash值:hash = hashFunc(key)
  2. 计算索引位置: index = hash % len(buckets)

哈希冲突
#

解决哈希碰撞一般有两种方式;拉链法和开放寻址法

拉链法
#

image-6-D8yGoIjj.png

开放寻址法
#

image-7-AYSKMRNX.png

Map
#

image-8-Bx2ZiMr4.png

type hmap struct {
    count     int            // 当前存储的键值对数量
    flags     uint8          // 标志位,用于记录 map 的状态(如是否正在扩容等)
    B         uint8          // 桶数组的大小是 2^B,决定了桶的数量
    noverflow uint16         // 记录溢出桶的数量
    hash0     uint32         // 哈希种子,防止哈希冲突攻击
    buckets    unsafe.Pointer // 指向主桶数组的指针
    oldbuckets unsafe.Pointer // 扩容时,指向旧桶数组
    nevacuate  uintptr        // 记录扩容的进度,表示已经迁移的桶的索引
    extra *mapextra // 存储溢出桶和其他额外信息
}
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    overflow uintptr
}
// go 1.20 ~
type bmap struct {
   // bucketCnt = 8
    tophash [bucketCnt]uint8  // 存储每个键的哈希值的高 8 位
    // 不再直接存储 keys 和 values
    // 键和值存储在外部的独立区域
    overflow *bmap
}

查找流程 hash = hash(“name”) bucketIndex = hash % bucketCount 先比较 tophash 如果匹配再比较 key

扩容

  1. 平均每个 bucket ≈ 6.5 个元素
  2. 如果溢出桶过多,也会扩容 负载因子已经超过 6.5: 双倍扩容​ 溢出桶的数量过多:等量扩容(一般认为溢出桶数量接近正常桶数量时)
Reply by Email