wordpress如何安装,优化大师怎么样,做网站内页图片尺寸,国家企业信用系统官网✍个人博客#xff1a;Pandaconda-CSDN博客 #x1f4e3;专栏地址#xff1a;http://t.csdnimg.cn/UWz06 #x1f4da;专栏简介#xff1a;在这个专栏中#xff0c;我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话#xff0c;欢迎点赞#x1f44d;收藏… ✍个人博客Pandaconda-CSDN博客 专栏地址http://t.csdnimg.cn/UWz06 专栏简介在这个专栏中我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话欢迎点赞收藏您的支持就是我创作的最大动力 31. Go Map 查找
在 Go 语言中使用 map 查找一个键值对的过程可以通过 map[key] 来完成返回值是对应的值和一个表示是否存在的布尔值。
具体来说如果 map 中存在该键则返回对应的值和布尔值 true如果不存在该键则返回值类型的零值和布尔值 false。例如
m : make(map[string]int)
m[apple] 1
value, ok : m[apple]
if ok {fmt.Println(value) // 输出 1
}
另外也可以直接使用一个值来获取键值对中的值但是如果键值对中不存在该键会返回该值类型的零值。例如
m : make(map[string]int)
m[apple] 1
value : m[banana]
fmt.Println(value) // 输出 0 需要注意的是map 的键类型必须支持相等运算例如数字、字符串、指针、通道、接口类型、结构体类型等都是支持的但是数组、切片、函数类型等不支持。 底层实现
在 Golang 中Map 的查找是通过哈希表实现的。当程序执行 map 查找操作时会先根据哈希函数将 key 转换成一个哈希值然后在哈希表中查找该哈希值对应的桶 (bucket)再在桶中查找对应的键值对。
具体来说当 Map 中的键值对数量超过一定阈值时会触发自动扩容操作。扩容操作会重新分配更大的桶数组并将原有的键值对重新哈希分布到新的桶中。
在查找时Golang 的 Map 会先通过哈希值定位到对应的桶 (bucket)然后在桶中遍历链表每个桶可能对应多个键值对查找对应的键值对。在遍历链表的过程中如果发现某个键值对的 key 与要查找的 key 相等则返回该键值对的 value。 需要注意的是如果 Map 中的键值对过多桶中的链表会很长查找时效率会降低因此需要根据实际情况合理设置 Map 的容量和哈希函数以充分利用哈希表的优势。同时当 Map 中的键值对类型为复杂类型如结构体时需要重载对应的哈希函数和比较函数以确保哈希表的正确性。 32. Go Ma p 如何查找
Go 语言中读取 map 有两种语法带 comma 和 不带 comma。当要查询的 key 不在 map 里带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0如果 value 是 string 类型就会返回空字符串。
// 不带 comma 用法
value : m[name]
fmt.Printf(value:%s, value)// 带 comma 用法
value, ok : m[name]
if ok {fmt.Printf(value:%s, value)
}
map 的查找通过生成汇编码可以知道根据 key 的不同类型/返回参数编译器会将查找函数用更具体的函数替换以优化效率 key 类型查找uint32mapaccess1_fast32(t maptype, h hmap, key uint32) unsafe.Pointeruint32mapaccess2_fast32(t maptype, h hmap, key uint32) (unsafe.Pointer, bool)uint64mapaccess1_fast64(t maptype, h hmap, key uint64) unsafe.Pointeruint64mapaccess2_fast64(t maptype, h hmap, key uint64) (unsafe.Pointer, bool)stringmapaccess1_faststr(t maptype, h hmap, ky string) unsafe.Pointerstringmapaccess2_faststr(t maptype, h hmap, ky string) (unsafe.Pointer, bool) 查找流程 1. 写保护监测
函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了说明有其他协程在执行“写”操作进而导致程序 panic这也说明了 map 不是线程安全的。
if h.flagshashWriting ! 0 {throw(concurrent map read and map write)
}
2. 计 算 hash 值
hash : t.hasher(key, uintptr(h.hash0))
key 经过哈希函数计算后得到的哈希值如下主流 64 位机下共 64 个 bit 位不同类型的 key 会有不同的 hash 函数。 10010111 | 000011110110110010001111001010100010010110010101010 │ 01010
3. 找 到 hash 对应的 bucket
bucket 定位哈希值的低 B 个 bit 位用来定位 key 所存放的 bucket。
如果当前正在扩容中并且定位到的旧 bucket 数据还未完成迁移则使用旧的 bucket扩容前的 bucket。
hash : t.hasher(key, uintptr(h.hash0))
// 桶的个数m-1即 1B-1,B5时则有0~31号桶
m : bucketMask(h.B)
// 计算哈希值对应的bucket
// t.bucketsize为一个bmap的大小通过对哈希值和桶个数取模得到桶编号通过对桶编号和buckets起始地址进行运算获取哈希值对应的bucket
b : (*bmap)(add(h.buckets, (hashm)*uintptr(t.bucketsize)))
// 是否在扩容
if c : h.oldbuckets; c ! nil {// 桶个数已经发生增长一倍则旧bucket的桶个数为当前桶个数的一半if !h.sameSizeGrow() {// There used to be half as many buckets; mask down one more power of two.m 1}// 计算哈希值对应的旧bucketoldb : (*bmap)(add(c, (hashm)*uintptr(t.bucketsize)))// 如果旧bucket的数据没有完成迁移则使用旧bucket查找if !evacuated(oldb) {b oldb}
}
4. 遍 历 bucket 查找
tophash 值定位哈希值的高 8 个 bit 位用来快速判断 key 是否已在当前 bucket 中如果不在的话需要去 bucket 的 overflow 中查找。
用步骤 2 中的 hash 值得到高 8 个 bit 位也就是 10010111转化为十进制也就是 151。
top : tophash(hash)
func tophash(hash uintptr) uint8 {top : uint8(hash (goarch.PtrSize*8 - 8))if top minTopHash {top minTopHash}return top
}
上面函数中 hash 是 64 位的sys.PtrSize 值是 8所以 top : uint8(hash (sys.PtrSize*8 - 8)) 等效 top uint8(hash 56)最后 top 取出来的值就是 hash 的高 8 位值。
在 bucket 及 bucket 的 overflow 中寻找 tophash 值HOB hash为 151* 的 槽位即为 key 所在位置找到了空槽位或者 2 号槽位这样整个查找过程就结束了其中找到空槽位代表没找到。
for ; b ! nil; b b.overflow(t) {for i : uintptr(0); i bucketCnt; i {if b.tophash[i] ! top {// 未被使用的槽位插入if b.tophash[i] emptyRest {break bucketloop}continue}// 找到tophash值对应的的keyk : add(unsafe.Pointer(b), dataOffseti*uintptr(t.keysize))if t.key.equal(key, k) {e : add(unsafe.Pointer(b), dataOffsetbucketCnt*uintptr(t.keysize)i*uintptr(t.elemsize))return e}}} 5. 返回 key 对应的指针
如果通过上面的步骤找到了 key 对应的槽位下标 i我们再详细分析下 key/value 值是如何获取的
// keys的偏移量
dataOffset unsafe.Offsetof(struct{b bmapv int64
}{}.v)// 一个bucket的元素个数
bucketCnt 8// key 定位公式
k :add(unsafe.Pointer(b),dataOffseti*uintptr(t.keysize))// value 定位公式
v: add(unsafe.Pointer(b),dataOffsetbucketCnt*uintptr(t.keysize)i*uintptr(t.valuesize))
bucket 里 keys 的起始地址就是 unsafe.Pointer(b)dataOffset。
第 i 个下标 key 的地址就要在此基础上跨过 i 个 key 的大小
而我们又知道value 的地址是在所有 key 之后因此第 i 个下标 value 的地址还需要加上所有 key 的偏移。
33. Go Map 冲突的解决方式
比较常用的 Hash 冲突解决方案有链地址法和开放寻址法
1. 链地址法
当哈希冲突发生时创建新单元并将新单元添加到冲突单元所在链表的尾部。
2. 开放寻址法
当哈希冲突发生时从发生冲突的那个单元起按照一定的次序从哈希表中寻找一个空闲的单元然后把发生冲突的元素存入到该单元。开放寻址法需要的表长度要大于等于所需要存放的元素数量。
开放寻址法有多种方式线性探测法、平方探测法、随机探测法和双重哈希法。这里以线性探测法来帮助读者理解开放寻址法思想。
线性探测法
设 Hash(key) 表示关键字 key 的哈希值 表示哈希表的槽位数哈希表的大小。
线性探测法则可以表示为
如果 Hash(x) % M 已经有数据则尝试 (Hash(x) 1) % M ;
如果 (Hash(x) 1) % M 也有数据了则尝试 (Hash(x) 2) % M ;
如果 (Hash(x) 2) % M 也有数据了则尝试 (Hash(x) 3) % M ;
两种解决方案比较
对于链地址法基于数组 链表进行存储链表节点可以在需要时再创建不必像开放寻址法那样事先申请好足够内存因此链地址法对于内存的利用率会比开方寻址法高。链地址法对装载因子的容忍度会更高并且适合存储大对象、大数据量的哈希表。而且相较于开放寻址法它更加灵活支持更多的优化策略比如可采用红黑树代替链表。但是链地址法需要额外的空间来存储指针。
对于开放寻址法它只有数组一种数据结构就可完成存储继承了数组的优点对 CPU 缓存友好易于序列化操作。但是它对内存的利用率不如链地址法且发生冲突时代价更高。当数据量明确、装载因子小适合采用开放寻址法。
总结
在发生哈希冲突时Python 中 dict 采用的开放寻址法Java 的 HashMap 采用的是链地址法而 Go map 也采用链地址法解决冲突具体就是插入 key 到 map 中时当 key 定位的桶填满 8 个元素后这里的单元就是桶不是元素将会创建一个溢出桶并且将溢出桶插入当前桶所在链表尾部。
if inserti nil {// all current buckets are full, allocate a new one.newb : h.newoverflow(t, b)// 创建一个新的溢出桶inserti newb.tophash[0]insertk add(unsafe.Pointer(newb), dataOffset)elem add(insertk, bucketCnt*uintptr(t.keysize))
}
34. Go Map 的负载因子为什么是 6.5
什么是负载因子?
负载因子load factor用于衡量当前哈希表中空间占用率的核心指标也就是每个 bucket 桶存储的平均元素个数。
负载因子 哈希表存储的元素个数/桶个数
另外负载因子与扩容、迁移等重新散列rehash行为有直接关系 在程序运行时会不断地进行插入、删除等会导致 bucket 不均内存利用率低需要迁移。 在程序运行时出现负载因子过大需要做扩容解决 bucket 过大的问题。
负载因子是哈希表中的一个重要指标在各种版本的哈希表实现中都有类似的东西主要目的是为了平衡 buckets 的存储空间大小和查找元素时的性能高低。
在接触各种哈希表时都可以关注一下做不同的对比看看各家的考量。
为什么是 6.5?
为什么 Go 语言中哈希表的负载因子是 6.5为什么不是 8 也不是 1。这里面有可靠的数据支撑吗
测试报告
实际上这是 Go 官方的经过认真的测试得出的数字一起来看看官方的这份测试报告。
报告中共包含 4 个关键指标如下 loadFactor%overflowbytes/entryhitprobemissprobe42.1320.77344.54.0517.33.254.556.8514.773.555.510.5512.943.755.5615.2711.67466.520.910.794.256.5727.1410.154.577.534.039.734.757.5841.19.458 loadFactor负载因子也有叫装载因子。 %overflow溢出率有溢出 bukcet 的百分比。 bytes/entry平均每对 key/value 的开销字节数. hitprobe查找一个存在的 key 时要查找的平均个数。 missprobe查找一个不存在的 key 时要查找的平均个数。
选择数值
Go 官方发现装载因子越大填入的元素越多空间利用率就越高但发生哈希冲突的几率就变大。反之装载因子越小填入的元素越少冲突发生的几率减小但空间浪费也会变得更多而且还会提高扩容操作的次数。
根据这份测试结果和讨论Go 官方取了一个相对适中的值把 Go 中的 map 的负载因子硬编码为 6.5这就是 6.5 的选择缘由。
这意味着在 Go 语言中当 map存储的元素个数大于或等于 6.5 * 桶个数 时就会触发扩容行为。
35. Go Map 的底层实现原理
Go 中的 map 是一个指针占用 8 个字节指向 hmap 结构体。
源码包中 src/runtime/map.go 定义了 hmap 的数据结构
hmap 包含若干个结构为 bmap 的数组每个 bmap 底层都采用链表结构bmap 通常叫其 bucket。 hmap 结构体
// A header for a Go map.
type hmap struct {count int // 代表哈希表中的元素个数调用len(map)时返回的就是该字段值。flags uint8 // 状态标志是否处于正在写入的状态等B uint8 // buckets桶的对数// 如果B5则buckets数组的长度 2^B32意味着有32个桶noverflow uint16 // 溢出桶的数量hash0 uint32 // 生成hash的随机数种子buckets unsafe.Pointer // 指向buckets数组的指针数组大小为2^B如果元素个数为0它为nil。oldbuckets unsafe.Pointer // 如果发生扩容oldbuckets是指向老的buckets数组的指针老的buckets数组大小是新的buckets的1/2;非扩容状态下它为nil。nevacuate uintptr // 表示扩容进度小于此地址的buckets代表已搬迁完成。extra *mapextra // 存储溢出桶这个字段是为了优化GC扫描而设计的下面详细介绍}
bmap 结构体
bmap 就是我们常说的 “桶”一个桶里面会最多装 8 个 key这些 key 之所以会落入同一个桶是因为它们经过哈希计算后哈希结果的低 B 位是相同的关于 key 的定位我们在 map 的查询中详细说明。在桶内又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置一个桶内最多有 8 个位置)。
// A bucket for a Go map.
type bmap struct {tophash [bucketCnt]uint8 // len为8的数组// 用来快速定位key是否在这个bmap中// 一个桶最多8个槽位如果key所在的tophash值在tophash中则代表该key在这个桶中
}
上面 bmap 结构是静态结构在编译过程中 runtime.bmap 会拓展成以下结构体
type bmap struct{tophash [8]uint8keys [8]keytype // keytype 由编译器编译时候确定values [8]elemtype // elemtype 由编译器编译时候确定overflow uintptr // overflow指向下一个bmapoverflow是uintptr而不是*bmap类型保证bmap完全不含指针是为了减少gc溢出桶存储到extra字段中
}
tophash 就是用于实现快速定位 key 的位置在实现过程中会使用 key 的 hash 值的高 8 位作为 tophash 值存放在 bmap 的 tophash 字段中。
tophash 字段不仅存储 key 哈希值的高 8 位还会存储一些状态值用来表明当前桶单元状态这些状态值都是小于 minTopHash 的。
为了避免 key 哈希值的高 8 位值和这些状态值相等产生混淆情况所以当 key 哈希值高 8 位若小于 minTopHash 时候自动将其值加上 minTopHash 作为该 key 的 tophash。桶单元的状态值如下
emptyRest 0 // 表明此桶单元为空且更高索引的单元也是空
emptyOne 1 // 表明此桶单元为空
evacuatedX 2 // 用于表示扩容迁移到新桶前半段区间
evacuatedY 3 // 用于表示扩容迁移到新桶后半段区间
evacuatedEmpty 4 // 用于表示此单元已迁移
minTopHash 5 // key的tophash值与桶状态值分割线值小于此值的一定代表着桶单元的状态大于此值的一定是key对应的tophash值func tophash(hash uintptr) uint8 {top : uint8(hash (goarch.PtrSize*8 - 8))if top minTopHash {top minTopHash}return top
}
mapextra 结构体
当 map 的 key 和 value 都不是指针类型时候bmap 将完全不包含指针那么 gc 时候就不用扫描 bmap。bmap 指向溢出桶的字段 overflow 是 uintptr 类型为了防止这些 overflow 桶被 gc 掉所以需要 mapextra.overflow 将它保存起来。如果 bmap 的 overflow 是 *bmap 类型那么 gc 扫描的是一个个拉链表效率明显不如直接扫描一段内存 (hmap.mapextra.overflow)。
type mapextra struct {overflow *[]*bmap// overflow 包含的是 hmap.buckets 的 overflow 的 bucketsoldoverflow *[]*bma// oldoverflow 包含扩容时 hmap.oldbuckets 的 overflow 的 bucketnextOverflow *bmap // 指向空闲的 overflow bucket 的指针
}
总结
bmapbucket内存数据结构可视化如下:
注意到 key 和 value 是各自放在一起的并不是 key/value/key/value/... 这样的形式当 key 和 value 类型不一样的时候key 和 value 占用字节大小不一样使用 key/value 这种形式可能会因为内存对齐导致内存空间浪费所以 Go 采用 key 和 value 分开存储的设计更节省内存空间。
