专栏首页Golang语言社区【Go 语言社区】Golang源码解读之map

【Go 语言社区】Golang源码解读之map

golang的map实现并不是像c++一样使用红黑树,而是使用了hashmap,用数组来实现。

详细的实现后续补充,这里先做个备忘。

在iterate整个map的时候,使用delete是安全的。这跟c++是不一样的,c++在delete的时候,会导致整棵树发生变化,所以不能在迭代的时候删除元素。

那为什么golang的map是安全的呢,从源码来看,golang的map使用了桶的概念,元素是被hash到桶存储,每个桶预设是存储八个kv,而且在头部有一个uint8 tophash[8]的结构,存储每个key的高八位(即hash(key) » (64 - 8)),如果该位置未被放置元素,则有一个特殊的标志Empty。在插入删除的时候,首先会比较该uint8跟hash(key)是否相等。当然,桶还利用了overflow指针,可以无限的增长,类似链表。

所以,for循环其实是对每个桶进行迭代,判断每个uint8位置,删除操作也并不是实际的memset,而是把对应的tophash的位置置为Empty.因此,在迭代golang的map过程中,使用delete是安全的。

struct Hmap
{
        uintgo  count;        // # live cells == size of map.  Must be first (used by len() builtin)
        uint32  flags;
        uint32  hash0;        // hash seed
        uint8   B;            // log_2 of # of buckets (can hold up to LOAD * 2^B items)
        uint8   keysize;      // key size in bytes
        uint8   valuesize;    // value size in bytes
        uint16  bucketsize;   // bucket size in bytes
        byte    *buckets;     // array of 2^B Buckets. may be nil if count==0.
        byte    *oldbuckets;  // previous bucket array of half the size, non-nil only when growing
        uintptr nevacuate;    // progress counter for evacuation (buckets less than this have been evacuated)
};
typedef struct Bucket Bucket;
struct Bucket
{
        uint8  tophash[BUCKETSIZE]; // top 8 bits of hash of each entry (0 = empty)
        Bucket *overflow;           // overflow bucket, if any
        byte   data[1];             // BUCKETSIZE keys followed by BUCKETSIZE values
};

本文分享自微信公众号 - Golang语言社区(Golangweb)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-01-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Golang语言社区】源码篇--sync包map

    早晨看到知乎上一篇介绍Go1.9X版本部分功能,特产关注了一下;把源码想给大家呈现下,实际测试请看下一篇文章:Go语言sync.map 实际测...

    李海彬
  • Golang 语言中 map 的键值类型选择,它是并发安全的吗?

    关于 golang 语言的 map,已经在「Go 基础」系列文章中介绍过,文末会附上文章链接,建议还没有阅读的读者阅读。我们知道 map 的键必须支持判等操作,...

    frank.
  • Go 问答汇总篇 二

    继上篇 Go 问答汇总,已经过去了一个多月。今天汇总下近一个多月我关于 Go 的回答。

    波罗学
  • 论golang是世界上最好的语言

    概述 golang is a better C and a simple C++ golang主要特性 1、语法简单 舍弃语法糖,严格控制关键字 C++语法糖之...

    李海彬
  • Golang面试题集锦

    谷歌开发的一种系统编程语言。它具有内置的垃圾收集机制并支持并发。代码可以编译成单个可执行二进制文件,不需要添加库或运行时环境即可在服务器上执行。

    李昂君
  • Golang学习资料大全

    咻咻ing
  • Python和Go语言都这么火,哪个更适合你?

    在本文中,我们探讨了 Python 和 Go 这两种世界上最流行的编程语言的差异、相似之处和用例。 从对两者的快速比较开始,然后看看它们在可读性、速度、易学性等...

    TSINGSEE青犀视频
  • Python和Go都很火,我要怎么选?

    互联网上有大量优秀的代码,它们构成了多种基础架构的基石。甚至本文所在网站的创建初衷也是创建优秀代码。虽然普通用户并没有注意到这一点,但优秀的开发者总是致力于优化...

    OpenCV学堂
  • Python和Go都很火,我要怎么选?

    互联网上有大量优秀的代码,它们构成了多种基础架构的基石。甚至本文所在网站的创建初衷也是创建优秀代码。虽然普通用户并没有注意到这一点,但优秀的开发者总是致力于优化...

    Python数据科学
  • 灵魂拷问:Python和Go都很火,我要怎么选?

    互联网上有大量优秀的代码,它们构成了多种基础架构的基石。甚至本文所在网站的创建初衷也是创建优秀代码。虽然普通用户并没有注意到这一点,但优秀的开发者总是致力于优化...

    CDA数据分析师
  • 第四节 Go语言数据类型

    干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

    李海彬
  • Go语言基础、进阶、提高课程--第一节:环境安装

    干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

    李海彬
  • Python和Go都很火,我要怎么选?

    互联网上有大量优秀的代码,它们构成了多种基础架构的基石。甚至本文所在网站的创建初衷也是创建优秀代码。虽然普通用户并没有注意到这一点,但优秀的开发者总是致力于优化...

    机器之心
  • 编程语言性能实测,Go比Python更胜一筹?

    互联网上有非常多的精彩代码,它们成了构建各种基础设施的基础。你正在阅读的这个平台同样也在致力于创建出色的代码。尽管普通用户一般不会注意到这一点,但另一方面,优秀...

    AI科技大本营
  • 牛客网_Go语言相关练习_判断&选择题(4)

    错误指的是可能出现问题的地方出现了问题,比如打开一个文件时失败,这种情况在人们的意料之中;而异常指的是不应该出现问题的地方出现了问题,比如引用了空指针,这种情况...

    Zoctopus
  • dubbo-go 的开发、设计与功能介绍

    dubbo-go 是目前 Dubbo 多语言生态最火热的项目。dubbo-go 最早的版本应该要追溯到 2016 年,由社区于雨同学编写 dubbo-go 的初...

    Java帮帮
  • dubbo-go介绍

    dubbo-go 是目前 Dubbo 多语言生态最火热的项目。dubbo-go 最早的版本应该要追溯到 2016 年,由社区于雨同学编写 dubbo-go 的初...

    heidsoft
  • Golang语言社区--Go语言基础第四节类型

    大家好,我是Golang语言社区主编彬哥,这节给大家讲解Go语言中的类型。

    李海彬
  • Python和Go都很火,我要怎么选?

    互联网上有大量优秀的代码,它们构成了多种基础架构的基石。甚至本文所在网站的创建初衷也是创建优秀代码。虽然普通用户并没有注意到这一点,但优秀的开发者总是致力于优化...

    CV君

扫码关注云+社区

领取腾讯云代金券