go语言遍历字典树 go 遍历

Go语言list（列表）

2021-11-10

创新互联建站专注于长安网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供长安营销型网站建设，长安网站制作、长安网页设计、长安网站官网定制、微信小程序定制开发服务，打造长安网络公司原创品牌,更为您提供长安网站排名全网营销落地服务。

列表是一种非连续的存储容器，有多个节点组成，节点通过一些变量记录彼此之间的关系

单链表和双链表就是列表的两种方法。

原理：A、B、C三个人，B懂A的电话，C懂B的电话只是单方知道号码，这样就形成了一个单链表结构。

如果C把自己的号码给B，B把自己的号码给A，因为是双方都知道对方的号码，这样就形成了一个双链表结构

如果B换号码了，他需要通知AC，把自己的号码删了，这个过程就是列表的删除操作。

在Go语言中，列表使用 container/list 包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置的元素插入和删除操作。

列表初始化的两种办法

列表没有给出具体的元素类型的限制，所以列表的元素可以是任意类型的，

例如给列表中放入了一个 interface{} 类型的值，取出值后，如果要将 interface{} 转换为其他类型将会发生宕机。

双链表支持从队列前方或后方插入元素，分别对应的方法是 PushFront 和 PushBack。

列表插入函数的返回值会提供一个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从列表中删除元素时，需要用到这个结构进行快速删除。

遍历完也能看到最后的结果

学习地址：

详谈树结构（传统树、字典树、hash 树、Merkle Patricia Tree）

本文参考： 树结构参考文献

[图片上传失败...(image-83b557-1539180310707)]

[图片上传失败...(image-d6bf01-1539180310707)]

性质1. 节点是红色或黑色，根是黑色，所有叶子都是黑色

性质2. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点，即红黑相间)，从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)。

[图片上传失败...(image-52c714-1539180310707)]

B+树是B树的变体，也是一种多路搜索树：

[图片上传失败...(image-c2ce8e-1539180310707)]

B+ 树的性质：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4. 更适合文件索引系统。

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

Tire树称为字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Tire树的三个基本性质：

Tire树的应用：

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。

[图片上传失败...(image-f00bd3-1539180310707)]

[图片上传失败...(image-d70c23-1539180310707)]

[图片上传失败...(image-8a3963-1539180310707)]

[图片上传失败...(image-69461e-1539180310707)]

[图片上传失败...(image-987993-1539180310707)]

[图片上传失败...(image-58f33c-1539180310707)]

参考文献：

1、

2、

3、

4、

Go语言使用 map 时尽量不要在 big map 中保存指针

不知道你有没有听过这么一句：在使用 map 时尽量不要在 big map 中保存指针。好吧，你现在已经听过了：）为什么呢？原因在于 Go 语言的垃圾回收器会扫描标记 map 中的所有元素，GC 开销相当大，直接GG。

这两天在《Mastering Go》中看到 GC 这一章节里面对比 map 和 slice 在垃圾回收中的效率对比，书中只给出结论没有说明理由，这我是不能忍的，于是有了这篇学习笔记。扯那么多，Show Your Code

这是一个简单的测试程序，保存字符串的 map 和 保存整形的 map GC 的效率相差几十倍，是不是有同学会说明明保存的是 string 哪有指针？这个要说到 Go 语言中 string 的底层实现了，源码在 src/runtime/string.go里，可以看到 string 其实包含一个指向数据的指针和一个长度字段。注意这里的是否包含指针，包括底层的实现。

Go 语言的 GC 会递归遍历并标记所有可触达的对象，标记完成之后将所有没有引用的对象进行清理。扫描到指针就会往下接着寻找，一直到结束。

Go 语言中 map 是基于 数组和链表 的数据结构实现的，通过 优化的拉链法 解决哈希冲突，每个 bucket 可以保存 8 对键值，在 8 个键值对数据后面有一个 overflow 指针，因为桶中最多只能装 8 个键值对，如果有多余的键值对落到了当前桶，那么就需要再构建一个桶（称为溢出桶），通过 overflow 指针链接起来。

因为 overflow 指针的缘故，所以无论 map 保存的是什么，GC 的时候就会把所有的 bmap 扫描一遍，带来巨大的 GC 开销。官方 issues 就有关于这个问题的讨论， runtime: Large maps cause significant GC pauses #9477

无脑机翻如下：

如果我们有一个map [k] v，其中k和v都不包含指针，并且我们想提高扫描性能，则可以执行以下操作。

将“ allOverflow [] unsafe.Pointer”添加到 hmap 并将所有溢出存储桶存储在其中。 然后将 bmap 标记为noScan。 这将使扫描非常快，因为我们不会扫描任何用户数据。

实际上，它将有些复杂，因为我们需要从allOverflow中删除旧的溢出桶。 而且它还会增加 hmap 的大小，因此也可能需要重新整理数据。

最终官方在 hmap 中增加了 overflow 相关字段完成了上面的优化，这是具体的 commit 地址。

下面看下具体是如何实现的，源码基于 go1.15，src/cmd/compile/internal/gc/reflect.go 中

通过注释可以看出，如果 map 中保存的键值都不包含指针（通过 Haspointers 判断），就使用一个 uintptr 类型代替 bucket 的指针用于溢出桶 overflow 字段，uintptr 类型在 GO 语言中就是个大小可以保存得下指针的整数，不是指针，就相当于实现了 将 bmap 标记为 noScan， GC 的时候就不会遍历完整个 map 了。随着不断的学习，愈发感慨 GO 语言中很多模块设计得太精妙了。

差不多说清楚了，能力有限，有不对的地方欢迎留言讨论，源码位置还是问的群里大佬 _

Go语言实践模式 - 函数选项模式(Functional Options Pattern)

大家好，我是小白，有点黑的那个白。

最近遇到一个问题，因为业务需求，需要对接第三方平台.

而三方平台提供的一些HTTP(S)接口都有统一的密钥生成规则要求.

为此我们封装了一个独立的包 xxx-go-sdk 以便维护和对接使用.

其中核心的部分是自定义HTTP Client,如下:

一些平台会要求appKey/appSecret等信息，所以Client结构体就变成了这样，这时参数还比较少, 而且是必填的参数，我们可以提供构造函数来明确指定。

看起来很满足，但是当我们需要增加一个 Timeout 参数来控制超时呢?

或许你会说这还不简单，像下面一样再加一个参数呗

那再加些其他的参数呢？那构造函数的参数是不是又长又串，而且每个参数不一定是必须的，有些参数我们又会考虑默认值的问题。

为此，勤劳但尚未致富的 gophers 们使用了总结一种实践模式

首先提取所有需要的参数到一个独立的结构体 Options，当然你也可以用 Configs 啥的.

然后为每个参数提供设置函数

这样我们就为每个参数设置了独立的设置函数。返回值 func(*Options) 看着有点不友好，我们提取下定义为单个 Option 调整一下代码

当我们需要添加更多的参数时，只需要在 Options 添加新的参数并添加新参数的设置函数即可。

比如现在要添加新的参数 Timeout

这样后续不管新增多少参数，只需要新增配置项并添加独立的设置函数即可轻松扩展，并且不会影响原有函数的参数顺序和个数位置等。

至此，每个选项是区分开来了，那么怎么作用到我们的 Client 结构体上呢?

首先，配置选项都被提取到了 Options 结构体重，所以我们需要调整一下 Client 结构体的参数

其次，每一个选项函数返回 Option,那么任意多个就是 ...Option，我们调整一下构造函数 NewClient 的参数形式，改为可变参数，不再局限于固定顺序的几个参数。

然后循环遍历每个选项函数，来生成Client结构体的完整配置选项。

那么怎么调用呢？对于调用方而已，直接在调用构造函数NewClient()的参数内添加自己需要的设置函数(WithXXX)即可

当需要设置超时参数，直接添加 WithTimeout即可,比如设置3秒的超时

配置选项的位置可以任意设置，不需要受常规的固定参数顺序约束。

可以看到，这种实践模式主要作用于配置选项，利用函数支持的特性来实现的，为此得名 Functional Options Pattern，优美的中国话叫做「函数选项模式」。

最后, 我们总结回顾一下在Go语言中函数选项模式的优缺点