golang結構圖,golang知識圖譜

本文目錄一覽：

• 1、（十一）golang 內存分析
• 2、手擼golang 基本數據結構與演算法 圖的搜索 深度優先/廣度優先
• 3、golang map源碼淺析
• 4、goland map底層原理

（十一）golang 內存分析

編寫過C語言程序的肯定知道通過malloc()方法動態申請內存，其中內存分配器使用的是glibc提供的ptmalloc2。 除了glibc，業界比較出名的內存分配器有Google的tcmalloc和Facebook的jemalloc。二者在避免內存碎片和性能上均比glic有比較大的優勢，在多線程環境中效果更明顯。

Golang中也實現了內存分配器，原理與tcmalloc類似，簡單的說就是維護一塊大的全局內存，每個線程(Golang中為P)維護一塊小的私有內存，私有內存不足再從全局申請。另外，內存分配與GC（垃圾回收）關係密切，所以了解GC前有必要了解內存分配的原理。

為了方便自主管理內存，做法便是先向系統申請一塊內存，然後將內存切割成小塊，通過一定的內存分配演算法管理內存。 以64位系統為例，Golang程序啟動時會向系統申請的內存如下圖所示：

預申請的內存劃分為spans、bitmap、arena三部分。其中arena即為所謂的堆區，應用中需要的內存從這裡分配。其中spans和bitmap是為了管理arena區而存在的。

arena的大小為512G，為了方便管理把arena區域劃分成一個個的page，每個page為8KB,一共有512GB/8KB個頁；

spans區域存放span的指針，每個指針對應一個page，所以span區域的大小為(512GB/8KB)乘以指針大小8byte = 512M

bitmap區域大小也是通過arena計算出來，不過主要用於GC。

span是用於管理arena頁的關鍵數據結構，每個span中包含1個或多個連續頁，為了滿足小對象分配，span中的一頁會劃分更小的粒度，而對於大對象比如超過頁大小，則通過多頁實現。

根據對象大小，劃分了一系列class，每個class都代表一個固定大小的對象，以及每個span的大小。如下表所示：

上表中每列含義如下：

class： class ID，每個span結構中都有一個class ID, 表示該span可處理的對象類型

bytes/obj：該class代表對象的位元組數

bytes/span：每個span佔用堆的位元組數，也即頁數乘以頁大小

objects: 每個span可分配的對象個數，也即（bytes/spans）/（bytes/obj）waste

bytes: 每個span產生的內存碎片，也即（bytes/spans）%（bytes/obj）上表可見最大的對象是32K大小，超過32K大小的由特殊的class表示，該class ID為0，每個class只包含一個對象。

span是內存管理的基本單位,每個span用於管理特定的class對象, 跟據對象大小，span將一個或多個頁拆分成多個塊進行管理。src/runtime/mheap.go:mspan定義了其數據結構：

以class 10為例，span和管理的內存如下圖所示：

spanclass為10，參照class表可得出npages=1,nelems=56,elemsize為144。其中startAddr是在span初始化時就指定了某個頁的地址。allocBits指向一個點陣圖，每位代表一個塊是否被分配，本例中有兩個塊已經被分配，其allocCount也為2。next和prev用於將多個span鏈接起來，這有利於管理多個span，接下來會進行說明。

有了管理內存的基本單位span，還要有個數據結構來管理span，這個數據結構叫mcentral，各線程需要內存時從mcentral管理的span中申請內存，為了避免多線程申請內存時不斷的加鎖，Golang為每個線程分配了span的緩存，這個緩存即是cache。src/runtime/mcache.go:mcache定義了cache的數據結構

alloc為mspan的指針數組，數組大小為class總數的2倍。數組中每個元素代表了一種class類型的span列表，每種class類型都有兩組span列表，第一組列表中所表示的對象中包含了指針，第二組列表中所表示的對象不含有指針，這麼做是為了提高GC掃描性能，對於不包含指針的span列表，沒必要去掃描。根據對象是否包含指針，將對象分為noscan和scan兩類，其中noscan代表沒有指針，而scan則代表有指針，需要GC進行掃描。mcache和span的對應關係如下圖所示：

mchache在初始化時是沒有任何span的，在使用過程中會動態的從central中獲取並緩存下來，跟據使用情況，每種class的span個數也不相同。上圖所示，class 0的span數比class1的要多，說明本線程中分配的小對象要多一些。

cache作為線程的私有資源為單個線程服務，而central則是全局資源，為多個線程服務，當某個線程內存不足時會向central申請，當某個線程釋放內存時又會回收進central。src/runtime/mcentral.go:mcentral定義了central數據結構：

lock: 線程間互斥鎖，防止多線程讀寫衝突

spanclass : 每個mcentral管理著一組有相同class的span列表

nonempty: 指還有內存可用的span列表

empty: 指沒有內存可用的span列表

nmalloc: 指累計分配的對象個數線程從central獲取span步驟如下：

將span歸還步驟如下：

從mcentral數據結構可見，每個mcentral對象只管理特定的class規格的span。事實上每種class都會對應一個mcentral,這個mcentral的集合存放於mheap數據結構中。src/runtime/mheap.go:mheap定義了heap的數據結構：

lock： 互斥鎖

spans: 指向spans區域，用於映射span和page的關係

bitmap：bitmap的起始地址

arena_start: arena區域首地址

arena_used: 當前arena已使用區域的最大地址

central: 每種class對應的兩個mcentral

從數據結構可見，mheap管理著全部的內存，事實上Golang就是通過一個mheap類型的全局變數進行內存管理的。mheap內存管理示意圖如下：

系統預分配的內存分為spans、bitmap、arean三個區域，通過mheap管理起來。接下來看內存分配過程。

針對待分配對象的大小不同有不同的分配邏輯：

(0, 16B) 且不包含指針的對象： Tiny分配

(0, 16B) 包含指針的對象：正常分配

[16B, 32KB] : 正常分配

(32KB, -) : 大對象分配其中Tiny分配和大對象分配都屬於內存管理的優化範疇，這裡暫時僅關注一般的分配方法。

以申請size為n的內存為例，分配步驟如下：

Golang內存分配是個相當複雜的過程，其中還摻雜了GC的處理，這裡僅僅對其關鍵數據結構進行了說明，了解其原理而又不至於深陷實現細節。1、Golang程序啟動時申請一大塊內存並劃分成spans、bitmap、arena區域

2、arena區域按頁劃分成一個個小塊。

3、span管理一個或多個頁。

4、mcentral管理多個span供線程申請使用

5、mcache作為線程私有資源，資源來源於mcentral。

手擼golang 基本數據結構與演算法 圖的搜索 深度優先/廣度優先

最近閱讀我的第一本演算法書(【日】石田保輝；宮崎修一)

本系列筆記擬採用golang練習之

graph_visit_test.go

頂點介面

圖的遍歷器介面

頂點的實現

候選節點隊列介面. 候選節點的選擇方式不同, 決定了是深度優先還是廣度優先.

LIFO堆棧, 實現INodeQueue介面

FIFO隊列, 實現INodeQueue介面

遍歷器, 實現IGraphVisitor介面

(end)

golang map源碼淺析

golang 中 map的實現結構為： 哈希表 + 鏈表。 其中鏈表，作用是當發生hash衝突時，拉鏈法生成的結點。

可以看到， []bmap 是一個hash table， 每一個 bmap是我們常說的「桶」。 經過hash 函數計算出來相同的hash值， 放到相同的桶中。 一個 bmap中可以存放 8個 元素， 如果多出8個，則生成新的結點，尾接到隊尾。

以上是只是靜態文件 src/runtime/map.go 中的定義。 實際上編譯期間會給它加料 ，動態地創建一個新的結構：

上圖就是 bmap的內存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，並不是 key/value/key/value/… 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 欄位，節省內存空間。

每個 bmap設計成 最多只能放 8 個 key-value 對 ，如果有第 9 個 key-value 落入當前的 bmap，那就需要再構建一個 bmap，通過 overflow 指針連接起來。

map創建方法:

我們實際上是通過調用的 makemap ，來創建map的。實際工作只是初始化了hmap中的各種欄位，如：設置B的大小， 設置hash 種子 hash 0.

注意 :

makemap 返回是*hmap 指針， 即 map 是引用對象， 對map的操作會影響到結構體內部 。

使用方式

對應的是下面兩種方法

map的key的類型，實現了自己的hash 方式。每種類型實現hash函數方式不一樣。

key 經過哈希計算後得到hash值，共 64 個 bit 位。 其中後B 個bit位置， 用來定位當前元素落在哪一個桶里， 高8個bit 為當前 hash 值的top hash。 實際上定位key的過程是一個雙重循環的過程， 外層循環遍歷 所有的overflow， 內層循環遍歷 當前bmap 中的 8個元素 。

舉例說明： 如果當前 B 的值為 5， 那麼buckets 的長度 為 2^5 = 32。假設有個key 經過hash函數計算後，得到的hash結果為：

外層遍歷bucket 中的鏈表

內層循環遍歷 bmap中的8個 cell

建議先不看此部分內容，看完後續 修改 map中元素 – 擴容 操作後 再回頭看此部分內容。

擴容前的數據：

等量擴容後的數據：

等量擴容後，查找方式和原本相同， 不多做贅述。

兩倍擴容後的數據

兩倍擴容後，oldbuckets 的元素，可能被分配成了兩部分。查找順序如下：

此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有興趣可自行看一下。

使用方式：

步驟如下：

擴容條件 ：

擴容的標識 ： h.oldbuckets ！= nil

假設當前定位到了新的buckets的3號桶中，首先會判斷oldbuckets中的對應的桶有沒有被搬遷過。 如果搬遷過了，不需要看原來的桶了，直接遍歷新的buckets的3號桶。

擴容前：

等量擴容結果

雙倍擴容會將old buckets上的元素分配到x， y兩個部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y部分

注意： 當前只對雙倍擴容描述， 等量擴容只是重新填充了一下元素， 相對位置沒有改變。

假設當前map 的B == 5，原本元素經過hash函數計算的 hash 值為：

因為雙倍擴容之後 B = B + 1，此時B == 6。key 1 B == 1, 即 當前元素rehash到高位，新buckets中 y 部分. 否則 key 1 B == 0 則rehash到低位，即x 部分。

使用方式：

可以看到，每一遍歷生成迭代器的時候，會隨機選取一個bucket 以及 一個cell開始。 從前往後遍歷，再次遍歷到起始位置時，遍歷完成。

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置為空。