隊列的概念在 順序隊列 中，而使用循環(huán)隊列的目的主要是規(guī)避假溢出造成的空間浪費，在使用循環(huán)隊列處理假溢出時，主要有三種解決方案
創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站制作、成都網(wǎng)站設(shè)計、外貿(mào)營銷網(wǎng)站建設(shè)與策劃設(shè)計,彭山網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:彭山等地區(qū)。彭山做網(wǎng)站價格咨詢:028-86922220
本文提供后兩種解決方案。
順序隊和循環(huán)隊列是一種特殊的線性表，與順序棧類似，都是使用一組地址連續(xù)的存儲單元依次存放自隊頭到隊尾的數(shù)據(jù)元素，同時附設(shè)隊頭(front)和隊尾(rear)兩個指針，但我們要明白一點，這個指針并不是指針變量，而是用來表示數(shù)組當中元素下標的位置。
本文使用切片來完成的循環(huán)隊列，由于一開始使用三個參數(shù)的make關(guān)鍵字創(chuàng)建切片，在輸出的結(jié)果中不包含nil值(看起來很舒服)，而且在驗證的過程中發(fā)現(xiàn)使用append()函數(shù)時切片內(nèi)置的cap會發(fā)生變化，在消除了種種障礙后得到了一個四不像的循環(huán)隊列，即設(shè)置的指針是順序隊列的指針，但實際上進行的操作是順序隊列的操作。最后是對make()函數(shù)和append()函數(shù)的一些使用體驗和小結(jié)，隊列的應(yīng)用放在鏈隊好了。
官方描述(片段)
即切片是一個抽象層，底層是對數(shù)組的引用。
當我們使用
構(gòu)建出來的切片的每個位置的值都被賦為interface類型的初始值nil，但是nil值也是有大小的。
而使用
來進行初始化時，雖然生成的切片中不包含nil值，但是無法通過設(shè)置的指針變量來完成入隊和出隊的操作，只能使用append()函數(shù)來進行操作
在go語言中，切片是一片連續(xù)的內(nèi)存空間加上長度與容量的標識，比數(shù)組更為常用。使用 append 關(guān)鍵字向切片中追加元素也是常見的切片操作
正是基于此，在使用go語言完成循環(huán)隊列時，首先想到的就是使用make(type, len, cap)關(guān)鍵字方式完成切片初始化，然后使用append()函數(shù)來操作該切片，但這一方式出現(xiàn)了很多問題。在使用append()函數(shù)時，切片的cap可能會發(fā)生變化，用不好就會發(fā)生擴容或收縮。最終造成的結(jié)果是一個四不像的結(jié)果，入隊和出隊操作變得與指針變量無關(guān)，失去了作為循環(huán)隊列的意義，用在順序隊列還算合適。
參考博客：
Go語言中的Nil
Golang之nil
Go 語言設(shè)計與實現(xiàn)
本教程介紹了 Go 中模糊測試的基礎(chǔ)知識。通過模糊測試，隨機數(shù)據(jù)會針對您的測試運行，以嘗試找出漏洞或?qū)е卤罎⒌妮斎??？梢酝ㄟ^模糊測試發(fā)現(xiàn)的一些漏洞示例包括 SQL 注入、緩沖區(qū)溢出、拒絕服務(wù)和跨站點腳本攻擊。
在本教程中，您將為一個簡單的函數(shù)編寫一個模糊測試，運行 go 命令，并調(diào)試和修復(fù)代碼中的問題。
首先，為您要編寫的代碼創(chuàng)建一個文件夾。
1、打開命令提示符并切換到您的主目錄。
在 Linux 或 Mac 上：
在 Windows 上：
2、在命令提示符下，為您的代碼創(chuàng)建一個名為 fuzz 的目錄。
3、創(chuàng)建一個模塊來保存您的代碼。
運行g(shù)o mod init命令，為其提供新代碼的模塊路徑。
接下來，您將添加一些簡單的代碼來反轉(zhuǎn)字符串，稍后我們將對其進行模糊測試。
在此步驟中，您將添加一個函數(shù)來反轉(zhuǎn)字符串。
a.使用您的文本編輯器，在 fuzz 目錄中創(chuàng)建一個名為 main.go 的文件。
獨立程序（與庫相反）始終位于 package 中main。
此函數(shù)將接受string，使用byte進行循環(huán) ，并在最后返回反轉(zhuǎn)的字符串。
此函數(shù)將運行一些Reverse操作，然后將輸出打印到命令行。這有助于查看運行中的代碼，并可能有助于調(diào)試。
e.該main函數(shù)使用 fmt 包，因此您需要導(dǎo)入它。
第一行代碼應(yīng)如下所示：
從包含 main.go 的目錄中的命令行，運行代碼。
可以看到原來的字符串，反轉(zhuǎn)它的結(jié)果，然后再反轉(zhuǎn)它的結(jié)果，就相當于原來的了。
現(xiàn)在代碼正在運行，是時候測試它了。
在這一步中，您將為Reverse函數(shù)編寫一個基本的單元測試。
a.使用您的文本編輯器，在 fuzz 目錄中創(chuàng)建一個名為 reverse_test.go 的文件。
b.將以下代碼粘貼到 reverse_test.go 中。
這個簡單的測試將斷言列出的輸入字符串將被正確反轉(zhuǎn)。
使用運行單元測試go test
接下來，您將單元測試更改為模糊測試。
單元測試有局限性，即每個輸入都必須由開發(fā)人員添加到測試中。模糊測試的一個好處是它可以為您的代碼提供輸入，并且可以識別您提出的測試用例沒有達到的邊緣用例。
在本節(jié)中，您將單元測試轉(zhuǎn)換為模糊測試，這樣您就可以用更少的工作生成更多的輸入！
請注意，您可以將單元測試、基準測試和模糊測試保存在同一個 *_test.go 文件中，但對于本示例，您將單元測試轉(zhuǎn)換為模糊測試。
在您的文本編輯器中，將 reverse_test.go 中的單元測試替換為以下模糊測試。
Fuzzing 也有一些限制。在您的單元測試中，您可以預(yù)測Reverse函數(shù)的預(yù)期輸出，并驗證實際輸出是否滿足這些預(yù)期。
例如，在測試用例Reverse("Hello, world")中，單元測試將返回指定為"dlrow ,olleH".
模糊測試時，您無法預(yù)測預(yù)期輸出，因為您無法控制輸入。
但是，Reverse您可以在模糊測試中驗證函數(shù)的一些屬性。在這個模糊測試中檢查的兩個屬性是：
（1）將字符串反轉(zhuǎn)兩次保留原始值
（2）反轉(zhuǎn)的字符串將其狀態(tài)保留為有效的 UTF-8。
注意單元測試和模糊測試之間的語法差異：
（3）確保新包unicode/utf8已導(dǎo)入。
隨著單元測試轉(zhuǎn)換為模糊測試，是時候再次運行測試了。
a.在不進行模糊測試的情況下運行模糊測試，以確保種子輸入通過。
如果您在該文件中有其他測試，您也可以運行g(shù)o test -run=FuzzReverse，并且您只想運行模糊測試。
b.運行FuzzReverse模糊測試，查看是否有任何隨機生成的字符串輸入會導(dǎo)致失敗。這是使用go test新標志-fuzz執(zhí)行的。
模糊測試時發(fā)生故障，導(dǎo)致問題的輸入被寫入將在下次運行的種子語料庫文件中g(shù)o test，即使沒有-fuzz標志也是如此。要查看導(dǎo)致失敗的輸入，請在文本編輯器中打開寫入 testdata/fuzz/FuzzReverse 目錄的語料庫文件。您的種子語料庫文件可能包含不同的字符串，但格式相同。
語料庫文件的第一行表示編碼版本。以下每一行代表構(gòu)成語料庫條目的每種類型的值。由于 fuzz target 只需要 1 個輸入，因此版本之后只有 1 個值。
c.運行沒有-fuzz標志的go test； 新的失敗種子語料庫條目將被使用：
由于我們的測試失敗，是時候調(diào)試了。
不知道你有沒有聽過這么一句：在使用 map 時盡量不要在 big map 中保存指針。好吧，你現(xiàn)在已經(jīng)聽過了：）為什么呢？原因在于 Go 語言的垃圾回收器會掃描標記 map 中的所有元素，GC 開銷相當大，直接GG。
這兩天在《Mastering Go》中看到 GC 這一章節(jié)里面對比 map 和 slice 在垃圾回收中的效率對比，書中只給出結(jié)論沒有說明理由，這我是不能忍的，于是有了這篇學(xué)習(xí)筆記。扯那么多，Show Your Code
這是一個簡單的測試程序，保存字符串的 map 和 保存整形的 map GC 的效率相差幾十倍，是不是有同學(xué)會說明明保存的是 string 哪有指針？這個要說到 Go 語言中 string 的底層實現(xiàn)了，源碼在 src/runtime/string.go里，可以看到 string 其實包含一個指向數(shù)據(jù)的指針和一個長度字段。注意這里的是否包含指針，包括底層的實現(xiàn)。
Go 語言的 GC 會遞歸遍歷并標記所有可觸達的對象，標記完成之后將所有沒有引用的對象進行清理。掃描到指針就會往下接著尋找，一直到結(jié)束。
Go 語言中 map 是基于 數(shù)組和鏈表 的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，通過 優(yōu)化的拉鏈法 解決哈希沖突，每個 bucket 可以保存 8 對鍵值，在 8 個鍵值對數(shù)據(jù)后面有一個 overflow 指針，因為桶中最多只能裝 8 個鍵值對，如果有多余的鍵值對落到了當前桶，那么就需要再構(gòu)建一個桶（稱為溢出桶），通過 overflow 指針鏈接起來。
因為 overflow 指針的緣故，所以無論 map 保存的是什么，GC 的時候就會把所有的 bmap 掃描一遍，帶來巨大的 GC 開銷。官方 issues 就有關(guān)于這個問題的討論， runtime: Large maps cause significant GC pauses #9477
無腦機翻如下：
如果我們有一個map [k] v，其中k和v都不包含指針，并且我們想提高掃描性能，則可以執(zhí)行以下操作。
將“ allOverflow [] unsafe.Pointer”添加到 hmap 并將所有溢出存儲桶存儲在其中。 然后將 bmap 標記為noScan。 這將使掃描非?？?，因為我們不會掃描任何用戶數(shù)據(jù)。
實際上，它將有些復(fù)雜，因為我們需要從allOverflow中刪除舊的溢出桶。 而且它還會增加 hmap 的大小，因此也可能需要重新整理數(shù)據(jù)。
最終官方在 hmap 中增加了 overflow 相關(guān)字段完成了上面的優(yōu)化，這是具體的 commit 地址。
下面看下具體是如何實現(xiàn)的，源碼基于 go1.15，src/cmd/compile/internal/gc/reflect.go 中
通過注釋可以看出，如果 map 中保存的鍵值都不包含指針（通過 Haspointers 判斷），就使用一個 uintptr 類型代替 bucket 的指針用于溢出桶 overflow 字段，uintptr 類型在 GO 語言中就是個大小可以保存得下指針的整數(shù)，不是指針，就相當于實現(xiàn)了 將 bmap 標記為 noScan， GC 的時候就不會遍歷完整個 map 了。隨著不斷的學(xué)習(xí)，愈發(fā)感慨 GO 語言中很多模塊設(shè)計得太精妙了。
差不多說清楚了，能力有限，有不對的地方歡迎留言討論，源碼位置還是問的群里大佬 _
在本節(jié)中，您將添加通用函數(shù)調(diào)用的修改版本，進行小的更改以簡化調(diào)用代碼。您將刪除在這種情況下不需要的類型參數(shù)。
當 Go 編譯器可以推斷您要使用的類型時，您可以在調(diào)用代碼中省略類型參數(shù)。編譯器從函數(shù)參數(shù)的類型推斷類型參數(shù)。
請注意，這并不總是可能的。例如，如果您需要調(diào)用沒有參數(shù)的泛型函數(shù)，則需要在函數(shù)調(diào)用中包含類型參數(shù)。
在 main.go 中，在您已有的代碼下方，粘貼以下代碼。
在此代碼中：
（1）調(diào)用泛型函數(shù)，省略類型參數(shù)。
從包含 main.go 的目錄中的命令行，運行代碼。
接下來，您將通過將整數(shù)和浮點數(shù)的并集捕獲到您可以重用的類型約束（例如從其他代碼中）來進一步簡化函數(shù)。
正如您將在本節(jié)中看到的，約束接口也可以引用特定類型。
1、編寫代碼
在此代碼中：
b.在您已有的函數(shù)下方，粘貼以下通用 SumNumbers函數(shù)。
在此代碼中：
c.在 main.go 中，在您已有的代碼下方，粘貼以下代碼。
在此代碼中：
（1）調(diào)用SumNumbers打印每個map的總和。
與上一節(jié)一樣，在調(diào)用泛型函數(shù)時省略了類型參數(shù)（方括號中的類型名稱）。Go 編譯器可以從其他參數(shù)推斷類型參數(shù)。
從包含 main.go 的目錄中的命令行，運行代碼。
做得很好！您剛剛學(xué)習(xí)了 Go 中的泛型。
重慶分公司
重慶分公司
