4.map使用以及底层实现

map

和slice类似, map也是引用类型, 当map被复制为一个新的变量时, 他们只想同一个内部数据结构. 因此改变其中一个变量, 另一个也会收到影响.

package main

import "fmt"

func main() {
    personSalary := map[string]int{
        "steve": 12000,
        "jamie": 15000,
    }
    personSalary["mike"] = 9000
    fmt.Println("Original person salary", personSalary)

    newPersonSalary := personSalary
    newPersonSalary["mike"] = 18000
    fmt.Println("Person Salary changed", personSalary)
}

map的相等性

map之间不饿能使用==操作符判断, ==只能用来检查map是否为nil

map底层实现原理

map整体结构图

go中map底层实现是一个散列表, 因此实现map的过程就是实现散列表的过程. 在这个散列表中, 主要出现的结构体有两个, 一个叫hmap, 一个叫bucket

hmap:

hmap结构图

bucket:

bucket结构图

由此可以看出, hmap和bucket的关系是这样的:

hmap和bucket关系

而bucket又是一个链表, 所以, 整体结构应该是这样的:

hmap和bucket整体结构

哈希函数

哈希表的特点是会有一个哈希函数, 对传过来的key进行hash运算, 得到唯一分值, 一般情况下都是一个数值.

在go中, 将求到的hash值一分为二: 高位和低位

key ---> hash函数f(x) ---> 1234567887654321

在上个公式中, 12345678为高位, 87654321为低位. 低位用于寻找当前key属于哪个bucket, 而高位用于寻找bucket中的哪个key

特别指出: 在map中的key/value都是存储到同一个数组中的

7d806b2a30f30d85e3ee65fb25929263.jpg

map的扩容

当以上哈希表持续增长时, Go会将bucket数组的数量扩充一倍, 产生一个新的bucket数组, 并将就数组数据迁移到新数组

加载因子

加载因子是一个阈值, 一般表示为:

加载因子 = 散列包含的元素数 / 位置总数

加载因子越小, 说明空间空置率越高, 空间使用率小, 加载因子越大, 说明空间利用率上去了, 但是产生冲突概率高了

当go的map长度增长到大于加载因子所需的长度时, 就会产生一个新的bucket数组, 然后将旧的bucket数组迁移到一个属性字段oldbucket中

注意: 迁移时并不会立即将旧数组中的元素迁移到新的bucket中, 只有在访问到具体bucket时才会把数据转移到新的bucket中

删除数据

1. 如果key是一个指针类型, 则直接将其置为空, 等待GC清除;
2. 如果是值类型, 则清除相关内存
3. 对value也做同样的操作
4. 最后把key对应的高位值的数组index置为空