goland map底层原理

map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？

城区网站建设公司创新互联,城区网站设计制作，有大型网站制作公司丰富经验。已为城区数千家提供企业网站建设服务。企业网站搭建\外贸网站建设要多少钱，请找那个售后服务好的城区做网站的公司定做！

总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。

golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的[8]uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。

Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map)，一个叫 bmap (a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：

hmap :

图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段： buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？

bucket ：

相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：

由此看出hmap和bucket的关系是这样的：

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

哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。

Golang把求得的值按照用途一分为二：高位和低位。

如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:

并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费 。

现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)

map的扩容

当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。

加载因子

判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。

加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。

每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。

Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。

当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。

如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组

上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。

扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：

注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。

map中数据的删除

如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。

值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：

1

2

3

4

1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；

2、如果是值类型的，则清除相关内存。

3、同理，对``value``做相同的操作。

4、最后把key对应的高位值对应的数组index置为空。

【原创】树莓派3B开发Go语言（四）-自写库实现pwm输出

在前一小节中介绍了点亮第一个LED灯，这里我们准备进阶尝试下，输出第一段PWM波形。（PWM也就是脉宽调制，一种可调占空比的技术，得到的效果就是：如果用示波器测量引脚会发现有方波输出，而且高电平、低电平的时间是可调的。）

这里爪爪熊准备写成一个golang的库，并开源到github上，后续更新将直接更新到github中，如果你有兴趣可以和我联系。 github.com/dpawsbear/bear_rpi_go

我在很多的教程中都看到说树莓派的PWM（硬件）只有一个GPIO能够输出，就是 GPIO1 。这可是不小的打击，因为我想使用至少四个 PWM ，还是不死心，想通过硬件手册上找寻蛛丝马迹，看看究竟怎么回事。

手册上找寻东西稍等下讲述，这里先提供一种方法测试 树莓派3B 的 PWM 方法：用指令控制硬件PWM。

这里通过指令的方式掌握了基本的pwm设置技巧，决定去翻一下手册看看到底PWM怎么回事，这里因为没有 BCM2837 的手册，根据之前文章引用官网所说， BCM2835 和 BCM2837 应该是一样的。这里我们直接翻阅 BCM2835 的手册，直接找到 PWM 章节。找到了如下图：

图中可以看到在博通的命名规则中 GPIO 12、13、18、19、40、41、45、52、53 均可以作为PWM输出。但是只有两路PWM0 PWM1。根据我之前所学知识，不出意外应该是PWM0 和 PWM1可以输出不一样的占空比，但是频率应该是一样的。因为没有示波器，暂时不好测试。先找到下面对应图：

根据以上两个图对比可以发现如下规律：

对照上面的表可以看出从 BCM2837 中印出来的能够使用在PWM上的就这几个了。

为了验证个人猜想是否正确，这里先直接使用指令的模式，模拟配置下是否能够正常输出。

通过上面一系列指令模拟发现，（GPIO1、GPIO26）、（GPIO23、GPIO24）是绑定在一起的，调节任意一个，另外一个也会发生变化。也即是PWM0、PWM1虽然输出了两路，可以理解成两路其实都是连在一个输出口上。这里由于没有示波器或者逻辑分析仪这类设备（仅有一个LED灯），所以测试很简陋，下一步是使用示波器这类东西对频率以及信号稳定性进行下测试。

小节：树莓派具有四路硬件输出PWM能力，但是四路中只能输出两个独立（占空比独立）的PWM，同时四路输出的频率均是恒定的。

上面大概了解清楚了树莓派3B的PWM结构，接下来就是探究如何使用Go语言进行设置。

因为拿到了手册，这里我想直接操作寄存器的方式进行设置，也是顺便学习下Go语言处理寄存器的过程。首先需要拿到pwm 系列寄存器的基地址，但是翻了一圈手册，发现只有偏移，没有找到基地址。

经过了一段时间的努力后，决定写一个 树莓派3B golang包开源放在github上，只需要写相关程序进行调用就可以了，以下是相关demo（pwm）（在GPIO.12 上输出PWM波，放上LED灯会有呼吸灯的效果，具体多少频率还没有进行测试）

以下是demo(pwm) 源码

讲讲go语言的结构体

作为C语言家族的一员，go和c一样也支持结构体。可以类比于java的一个POJO。

在学习定义结构体之前，先学习下定义一个新类型。

新类型 T1 是基于 Go 原生类型 int 定义的新自定义类型，而新类型 T2 则是 基于刚刚定义的类型 T1，定义的新类型。

这里要引入一个底层类型的概念。

如果一个新类型是基于某个 Go 原生类型定义的， 那么我们就叫 Go 原生类型为新类型的底层类型

在上面的例子中，int就是T1的底层类型。

但是T1不是T2的底层类型，只有原生类型才可以作为底层类型，所以T2的底层类型还是int

底层类型是很重要的，因为对两个变量进行显式的类型转换，只有底层类型相同的变量间才能相互转换。底层类型是判断两个类型本质上是否相同的根本。

这种类型定义方式通常用在 项目的渐进式重构，还有对已有包的二次封装方面

类型别名表示新类型和原类型完全等价，实际上就是同一种类型。只不过名字不同而已。

一般我们都是定义一个有名的结构体。

字段名的大小写决定了字段是否包外可用。只有大写的字段可以被包外引用。

还有一个点提一下

如果换行来写

Age: 66,后面这个都好不能省略

还有一个点，观察e3的赋值

new返回的是一个指针。然后指针可以直接点号赋值。这说明go默认进行了取值操作

e3.Age 等价于 (*e3).Age

如上定义了一个空的结构体Empty。打印了元素e的内存大小是0。

有什么用呢？

基于空结构体类型内存零开销这样的特性，我们在日常 Go 开发中会经常使用空 结构体类型元素，作为一种“事件”信息进行 Goroutine 之间的通信

这种以空结构体为元素类建立的 channel，是目前能实现的、内存占用最小的 Goroutine 间通信方式。

这种形式需要说的是几个语法糖。

语法糖1：

对于结构体字段，可以省略字段名，只写结构体名。默认字段名就是结构体名

这种方式称为 嵌入字段

语法糖2：

如果是以嵌入字段形式写的结构体

可以省略嵌入的Reader字段，而直接访问ReaderName

此时book是一个各个属性全是对应类型零值的一个实例。不是nil。这种情况在Go中称为零值可用。不像java会导致npe

结构体定义时可以在字段后面追加标签说明。

tag的格式为反单引号

tag的作用是可以使用[反射]来检视字段的标签信息。

具体的作用还要看使用的场景。

比如这里的tag是为了帮助 encoding/json 标准包在解析对象时可以利用的规则。比如omitempty表示该字段没有值就不打印出来。

go语言的reflect（反射）

1、反射可以在运行时 动态获取变量的各种信息 ，比如变量的类型、类别；

2、如果是结构体变量，还可以获取到结构体本身的信息（包括结构体的字段、方法）；

3、通过反射，可以修改 变量的值 ，可以调用关联的方法；

4、使用反射，需要import " reflect ".

5、示意图：

1、不知道接口调用哪个函数，根据传入参数在运行时确定调用的具体接口，这种需要对函数或方法反射。

例如以下这种桥接模式：

示例第一个参数funcPtr以接口的形式传入函数指针，函数参数args以可变参数的形式传入，bridge函数中可以用反射来动态执行funcPtr函数。

1、reflect.TypeOf(变量名)，获取变量的类型，返回reflect.Type类型。

2、reflect.ValueOf(变量名)，获取变量的值，返回reflect.Value类型reflect.Value是一个结构体类型。

3、变量、interface{}和reflect.Value是可以互相转换的，这点在实际开发中，会经常使用到。

1、reflect.Value.Kind，获取变量的 类别（Kind） ，返回的是一个 常量 。在go语言文档中：

示例如下所示：

输出如下：

Kind的范畴要比Type大。比如有Student和Consumer两个结构体，他们的 Type 分别是 Student 和 Consumer ，但是它们的 Kind 都是 struct 。

2、Type是类型，Kind是类别，Type和Kind可能是相同的，也可能是不同的。

3、通过反射可以在让 变量 在 interface{} 和 Reflect.Value 之间相互转换，这点在前面画过示意图。

4、使用反射的方式来获取变量的值（并返回对应的类型），要求数据类型匹配，比如x是int，那么久应该使用reflect.Value(x).Int()，而不能使用其它的，否则报panic。

如果是x是float类型的话，也是要用reflect.Value(x).Float()。但是如果是struct类型的话，由于type并不确定，所以没有相应的方法，只能 断言。

5、通过反射的来修改变量，注意当使用SetXxx方法来设置需要通过对应的指针类型来完成，这样才能改变传入的变量的值，同时需要使用到reflect.Value.Elem()方法。

输出num=20，即成功使用反射来修改传进来变量的值。

6、reflect.Value.Elem()应该如何理解？

GO语言学习系列八——GO函数(func)的声明与使用

GO是编译性语言，所以函数的顺序是无关紧要的，为了方便阅读，建议入口函数 main 写在最前面，其余函数按照功能需要进行排列

GO的函数 不支持嵌套，重载和默认参数

GO的函数 支持 无需声明变量，可变长度，多返回值，匿名，闭包等

GO的函数用 func 来声明，且左大括号 { 不能另起一行

一个简单的示例：

输出为：

参数：可以传0个或多个值来供自己用

返回：通过用 return 来进行返回

输出为：

上面就是一个典型的多参数传递与多返回值

对例子的说明：

按值传递：是对某个变量进行复制，不能更改原变量的值

引用传递：相当于按指针传递，可以同时改变原来的值，并且消耗的内存会更少，只有4或8个字节的消耗

在上例中，返回值 (d int, e int, f int) { 是进行了命名，如果不想命名可以写成 (int,int,int){ ,返回的结果都是一样的，但要注意:

当返回了多个值，我们某些变量不想要，或实际用不到，我们可以使用 _ 来补位，例如上例的返回我们可以写成 d,_,f := test(a,b,c) ，我们不想要中间的返回值，可以以这种形式来舍弃掉

在参数后面以 变量 ... type 这种形式的，我们就要以判断出这是一个可变长度的参数

输出为：

在上例中， strs ...string 中， strs 的实际值是b,c,d,e,这就是一个最简单的传递可变长度的参数的例子，更多一些演变的形式，都非常类似

在GO中 defer 关键字非常重要，相当于面相对像中的析构函数，也就是在某个函数执行完成后，GO会自动这个；

如果在多层循环中函数里，都定义了 defer ,那么它的执行顺序是先进后出；

当某个函数出现严重错误时， defer 也会被调用

输出为

这是一个最简单的测试了，当然还有更复杂的调用，比如调试程序时，判断是哪个函数出了问题，完全可以根据 defer 打印出来的内容来进行判断，非常快速，这种留给你们去实现

一个函数在函数体内自己调用自己我们称之为递归函数，在做递归调用时，经常会将内存给占满，这是非常要注意的，常用的比如，快速排序就是用的递归调用

本篇重点介绍了GO函数(func)的声明与使用，下一篇将介绍GO的结构 struct

分享文章：go语言结构图,go语言的框架
URL标题：http://scyanting.com/article/phsegc.html