golang hashmap的使用及实现

基本语法

定义hashmap变量

由于go语言是一个强类型的语言,因此hashmap也是有类型的,具体体现在key和value都必须指定类型,比如声明一个key为string,value也是string的map,
需要这样做

大部分类型都能做key,某些类型是不能的,共同的特点是:不能使用==来比较,包括: slice, map, function

get,set,delete

迭代器

在迭代的过程中是可以对map进行删除和更新操作的,规则如下:

  • 迭代是无序的,跟插入是的顺序无关
  • 迭代的过程中删除一个key,无论遍历还是没有遍历过都不会再遍历到
  • 迭代的过程中添加一个key,不确定是否能遍历到
  • 未初始化的map也可以迭代

其他

  • map的value是不可取地址的,意味着 &m[“a”]这样的语法是非法的
  • len和cap分别可以获取当前map的kv个数和总容量

内部结构

hashmap结构

golang的map是hash结构的,意味着平均访问时间是O(1)的。同传统的hashmap一样,由一个个bucket组成:0

bucket内部

0 (1)

根据一个key得到value

  • *maptype为map的类型信息,是编译器在编译期静态生成的,里面包含了map的一些元信息,比如key和value的类型信息等等
  • *hmap为map的header,即map的引用
  • key是一个通用的指针,代表了key的引用
  • 返回值为一个指针,指向对应的value引用

    hash计算找到bucket

    那我们怎么访问到对应的bucket呢,我们需要得到对应key的hash值

    0 (2)

根据tophash和key定位到具体的bucket

  • tophash可以快速试错,如果tophash不相等直接跳过
  • tophash相等的话,根据key的比较来判断是否相等,如果相等则找到
  • 如果当前bucket都试玩还没有找到,则调到下一个bucket

扩容

捕获

各个参数的意思:

  • %overflow 溢出率,平均一个bucket有多少个kv的时候会溢出
  • bytes/entry 平均存一个kv需要额外存储多少字节的数据
  • hitprobe 找到一个存在的key平均需要找几下
  • missprobe 找到一个不存在的key平均需要找几下

目前采用的是这一行:

 

文章分类 go

发表评论

电子邮件地址不会被公开。

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

在线交流

数百位业内高手和同行在等你交流
Reboot运维开发分享