【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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.3节栈布局之局部变量

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

911
来自专栏Java技术分享圈

杨老师课堂之Excel VBA 程序开发第六讲根据部门列创建工作表

方式1:本节课件下载地址:链接: https://pan.baidu.com/s/1rf5pRmZ95fjVbz70KYi6Aw 密码: q9yk

914
来自专栏C/C++基础

web前端开发初学者十问集锦(4)

利用JS来控制页面控件的显示和隐藏有两种方法,两种方法分别利用HTML的style中的两个属性,两种方法的不同之处在于控件隐藏后是否还在页面上占空位。

1762
来自专栏峰会SaaS大佬云集

C#学习---基础入门(四)C#中的字符与字符串

字符 char(单个字符) 用单引号 ,例如char a=‘a’;可以通过调用char类下的方法进行一些操作,具体通过help查看其相关方法

1274
来自专栏偏前端工程师的驿站

JS魔法堂:那些困扰你的DOM集合类型

一、前言                                     大家先看看下面的js,猜猜结果会怎样吧!   可选答案:   ①. 获取id属...

2419
来自专栏盛国存的专栏

A Bite of GoLang(上)

A bite of GoLang(浅尝GoLang),本文只是Go语言的冰山一角,本文包含作者学习Go语言期间积累的一些小的经验,同时为了方便让读者了解到Go语...

55810
来自专栏我的小碗汤

go语言正则表达式

我们前两节课爬取珍爱网的时候,用到了很多正则表达式去匹配城市列表、城市、用户信息,其实除了正则表达式去匹配,还可以利用goquery和xpath第三方库匹配有用...

1324
来自专栏Golang语言社区

Go 语言简介(上)— 语法

Hello World package main //声明本文件的package名 import "fmt" //import语言的fmt库——用于输出 f...

4048
来自专栏IMWeb前端团队

20个例子入门Q.js

本文希望通过20个简单的例子让没用过Q.js的同学快速掌握其基本用法 1. 新建实例 html代码: <div id="demo" q-text="msg"><...

2617
来自专栏吴伟祥

YAML 语言入门教程 转

YAML 仍然是一门标记性语言,但为了强调这门语言以数据为中心,而不是以标记语言为中心。采用反向缩略语重新命名。

753

扫码关注云+社区

领取腾讯云代金券