go语言循环队列的实现

队列的概念在 顺序队列 中，而使用循环队列的目的主要是规避假溢出造成的空间浪费，在使用循环队列处理假溢出时，主要有三种解决方案

创新互联是一家专注于成都网站制作、成都网站设计、外贸营销网站建设与策划设计,彭山网站建设哪家好?创新互联做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:彭山等地区。彭山做网站价格咨询:028-86922220

本文提供后两种解决方案。

顺序队和循环队列是一种特殊的线性表，与顺序栈类似，都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素，同时附设队头(front)和队尾(rear)两个指针，但我们要明白一点，这个指针并不是指针变量，而是用来表示数组当中元素下标的位置。

本文使用切片来完成的循环队列，由于一开始使用三个参数的make关键字创建切片，在输出的结果中不包含nil值(看起来很舒服)，而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化，在消除了种种障碍后得到了一个四不像的循环队列，即设置的指针是顺序队列的指针，但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结，队列的应用放在链队好了。

官方描述(片段)

即切片是一个抽象层，底层是对数组的引用。

当我们使用

构建出来的切片的每个位置的值都被赋为interface类型的初始值nil，但是nil值也是有大小的。

而使用

来进行初始化时，虽然生成的切片中不包含nil值，但是无法通过设置的指针变量来完成入队和出队的操作，只能使用append()函数来进行操作

在go语言中，切片是一片连续的内存空间加上长度与容量的标识，比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作

正是基于此，在使用go语言完成循环队列时，首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化，然后使用append()函数来操作该切片，但这一方式出现了很多问题。在使用append()函数时，切片的cap可能会发生变化，用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果，入队和出队操作变得与指针变量无关，失去了作为循环队列的意义，用在顺序队列还算合适。

参考博客：

Go语言中的Nil

Golang之nil

Go 语言设计与实现

GO语言（十六）：模糊测试入门（上）

本教程介绍了 Go 中模糊测试的基础知识。通过模糊测试，随机数据会针对您的测试运行，以尝试找出漏洞或导致崩溃的输入。可以通过模糊测试发现的一些漏洞示例包括 SQL 注入、缓冲区溢出、拒绝服务和跨站点脚本攻击。

在本教程中，您将为一个简单的函数编写一个模糊测试，运行 go 命令，并调试和修复代码中的问题。

首先，为您要编写的代码创建一个文件夹。

1、打开命令提示符并切换到您的主目录。

在 Linux 或 Mac 上：

在 Windows 上：

2、在命令提示符下，为您的代码创建一个名为 fuzz 的目录。

3、创建一个模块来保存您的代码。

运行go mod init命令，为其提供新代码的模块路径。

接下来，您将添加一些简单的代码来反转字符串，稍后我们将对其进行模糊测试。

在此步骤中，您将添加一个函数来反转字符串。

a.使用您的文本编辑器，在 fuzz 目录中创建一个名为 main.go 的文件。

独立程序（与库相反）始终位于 package 中main。

此函数将接受string，使用byte进行循环 ，并在最后返回反转的字符串。

此函数将运行一些Reverse操作，然后将输出打印到命令行。这有助于查看运行中的代码，并可能有助于调试。

e.该main函数使用 fmt 包，因此您需要导入它。

第一行代码应如下所示：

从包含 main.go 的目录中的命令行，运行代码。

可以看到原来的字符串，反转它的结果，然后再反转它的结果，就相当于原来的了。

现在代码正在运行，是时候测试它了。

在这一步中，您将为Reverse函数编写一个基本的单元测试。

a.使用您的文本编辑器，在 fuzz 目录中创建一个名为 reverse_test.go 的文件。

b.将以下代码粘贴到 reverse_test.go 中。

这个简单的测试将断言列出的输入字符串将被正确反转。

使用运行单元测试go test

接下来，您将单元测试更改为模糊测试。

单元测试有局限性，即每个输入都必须由开发人员添加到测试中。模糊测试的一个好处是它可以为您的代码提供输入，并且可以识别您提出的测试用例没有达到的边缘用例。

在本节中，您将单元测试转换为模糊测试，这样您就可以用更少的工作生成更多的输入！

请注意，您可以将单元测试、基准测试和模糊测试保存在同一个 *_test.go 文件中，但对于本示例，您将单元测试转换为模糊测试。

在您的文本编辑器中，将 reverse_test.go 中的单元测试替换为以下模糊测试。

Fuzzing 也有一些限制。在您的单元测试中，您可以预测Reverse函数的预期输出，并验证实际输出是否满足这些预期。

例如，在测试用例Reverse("Hello, world")中，单元测试将返回指定为"dlrow ,olleH".

模糊测试时，您无法预测预期输出，因为您无法控制输入。

但是，Reverse您可以在模糊测试中验证函数的一些属性。在这个模糊测试中检查的两个属性是：

（1）将字符串反转两次保留原始值

（2）反转的字符串将其状态保留为有效的 UTF-8。

注意单元测试和模糊测试之间的语法差异：

（3）确保新包unicode/utf8已导入。

随着单元测试转换为模糊测试，是时候再次运行测试了。

a.在不进行模糊测试的情况下运行模糊测试，以确保种子输入通过。

如果您在该文件中有其他测试，您也可以运行go test -run=FuzzReverse，并且您只想运行模糊测试。

b.运行FuzzReverse模糊测试，查看是否有任何随机生成的字符串输入会导致失败。这是使用go test新标志-fuzz执行的。

模糊测试时发生故障，导致问题的输入被写入将在下次运行的种子语料库文件中go test，即使没有-fuzz标志也是如此。要查看导致失败的输入，请在文本编辑器中打开写入 testdata/fuzz/FuzzReverse 目录的语料库文件。您的种子语料库文件可能包含不同的字符串，但格式相同。

语料库文件的第一行表示编码版本。以下每一行代表构成语料库条目的每种类型的值。由于 fuzz target 只需要 1 个输入，因此版本之后只有 1 个值。

c.运行没有-fuzz标志的go test； 新的失败种子语料库条目将被使用：

由于我们的测试失败，是时候调试了。

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语言（十五）：泛型入门（下）-

在本节中，您将添加通用函数调用的修改版本，进行小的更改以简化调用代码。您将删除在这种情况下不需要的类型参数。

当 Go 编译器可以推断您要使用的类型时，您可以在调用代码中省略类型参数。编译器从函数参数的类型推断类型参数。

请注意，这并不总是可能的。例如，如果您需要调用没有参数的泛型函数，则需要在函数调用中包含类型参数。

在 main.go 中，在您已有的代码下方，粘贴以下代码。

在此代码中：

（1）调用泛型函数，省略类型参数。

从包含 main.go 的目录中的命令行，运行代码。

接下来，您将通过将整数和浮点数的并集捕获到您可以重用的类型约束（例如从其他代码中）来进一步简化函数。

正如您将在本节中看到的，约束接口也可以引用特定类型。

1、编写代码

在此代码中：

b.在您已有的函数下方，粘贴以下通用 SumNumbers函数。

在此代码中：

c.在 main.go 中，在您已有的代码下方，粘贴以下代码。

在此代码中：

（1）调用SumNumbers打印每个map的总和。

与上一节一样，在调用泛型函数时省略了类型参数（方括号中的类型名称）。Go 编译器可以从其他参数推断类型参数。

从包含 main.go 的目录中的命令行，运行代码。

做得很好！您刚刚学习了 Go 中的泛型。

文章名称：go语言整数溢出检测 js整数溢出
文章转载：http://scyanting.com/article/dogpoed.html