map 是Go語言中基礎的數(shù)據(jù)結構，在日常的使用中經(jīng)常被用到。但是它底層是如何實現(xiàn)的呢？
城區(qū)網(wǎng)站建設公司創(chuàng)新互聯(lián),城區(qū)網(wǎng)站設計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為城區(qū)數(shù)千家提供企業(yè)網(wǎng)站建設服務。企業(yè)網(wǎng)站搭建\外貿網(wǎng)站建設要多少錢，請找那個售后服務好的城區(qū)做網(wǎng)站的公司定做！
總體來說golang的map是hashmap，是使用數(shù)組+鏈表的形式實現(xiàn)的，使用拉鏈法消除hash沖突。
golang的map由兩種重要的結構，hmap和bmap(下文中都有解釋)，主要就是hmap中包含一個指向bmap數(shù)組的指針，key經(jīng)過hash函數(shù)之后得到一個數(shù)，這個數(shù)低位用于選擇bmap(當作bmap數(shù)組指針的下表)，高位用于放在bmap的[8]uint8數(shù)組中，用于快速試錯。然后一個bmap可以指向下一個bmap(拉鏈)。
Golang中map的底層實現(xiàn)是一個散列表，因此實現(xiàn)map的過程實際上就是實現(xiàn)散表的過程。在這個散列表中，主要出現(xiàn)的結構體有兩個，一個叫 hmap (a header for a go map)，一個叫 bmap (a bucket for a Go map，通常叫其bucket)。這兩種結構的樣子分別如下所示：
hmap :
圖中有很多字段，但是便于理解map的架構，你只需要關心的只有一個，就是標紅的字段： buckets數(shù)組 。Golang的map中用于存儲的結構是bucket數(shù)組。而bucket(即bmap)的結構是怎樣的呢？
bucket ：
相比于hmap，bucket的結構顯得簡單一些，標紅的字段依然是“核心”，我們使用的map中的key和value就存儲在這里?！案呶还Ｖ怠睌?shù)組記錄的是當前bucket中key相關的“索引”，稍后會詳細敘述。還有一個字段是一個指向擴容后的bucket的指針，使得bucket會形成一個鏈表結構。例如下圖：
由此看出hmap和bucket的關系是這樣的：
而bucket又是一個鏈表，所以，整體的結構應該是這樣的：
哈希表的特點是會有一個哈希函數(shù)，對你傳來的key進行哈希運算，得到唯一的值，一般情況下都是一個數(shù)值。Golang的map中也有這么一個哈希函數(shù)，也會算出唯一的值，對于這個值的使用，Golang也是很有意思。
Golang把求得的值按照用途一分為二：高位和低位。
如圖所示，藍色為高位，紅色為低位。 然后低位用于尋找當前key屬于hmap中的哪個bucket，而高位用于尋找bucket中的哪個key。上文中提到：bucket中有個屬性字段是“高位哈希值”數(shù)組，這里存的就是藍色的高位值，用來聲明當前bucket中有哪些“key”，便于搜索查找。 需要特別指出的一點是：我們map中的key/value值都是存到同一個數(shù)組中的。數(shù)組中的順序是這樣的:
并不是key0/value0/key1/value1的形式，這樣做的好處是：在key和value的長度不同的時候，可 以消除padding(內存對齊)帶來的空間浪費 。
現(xiàn)在，我們可以得到Go語言map的整個的結構圖了：(hash結果的低位用于選擇把KV放在bmap數(shù)組中的哪一個bmap中，高位用于key的快速預覽，用于快速試錯)
map的擴容
當以上的哈希表增長的時候，Go語言會將bucket數(shù)組的數(shù)量擴充一倍，產(chǎn)生一個新的bucket數(shù)組，并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。
加載因子
判斷擴充的條件，就是哈希表中的加載因子(即loadFactor)。
加載因子是一個閾值，一般表示為：散列包含的元素數(shù) 除以 位置總數(shù)。是一種“產(chǎn)生沖突機會”和“空間使用”的平衡與折中：加載因子越小，說明空間空置率高，空間使用率小，但是加載因子越大，說明空間利用率上去了，但是“產(chǎn)生沖突機會”高了。
每種哈希表的都會有一個加載因子，數(shù)值超過加載因子就會為哈希表擴容。
Golang的map的加載因子的公式是：map長度 / 2^B(這是代表bmap數(shù)組的長度，B是取的低位的位數(shù))閾值是6.5。其中B可以理解為已擴容的次數(shù)。
當Go的map長度增長到大于加載因子所需的map長度時，Go語言就會將產(chǎn)生一個新的bucket數(shù)組，然后把舊的bucket數(shù)組移到一個屬性字段oldbucket中。注意：并不是立刻把舊的數(shù)組中的元素轉義到新的bucket當中，而是，只有當訪問到具體的某個bucket的時候，會把bucket中的數(shù)據(jù)轉移到新的bucket中。
如下圖所示：當擴容的時候，Go的map結構體中，會保存舊的數(shù)據(jù)，和新生成的數(shù)組
上面部分代表舊的有數(shù)據(jù)的bucket，下面部分代表新生成的新的bucket。藍色代表存有數(shù)據(jù)的bucket，橘黃色代表空的bucket。
擴容時map并不會立即把新數(shù)據(jù)做遷移，而是當訪問原來舊bucket的數(shù)據(jù)的時候，才把舊數(shù)據(jù)做遷移，如下圖：
注意：這里并不會直接刪除舊的bucket，而是把原來的引用去掉，利用GC清除內存。
map中數(shù)據(jù)的刪除
如果理解了map的整體結構，那么查找、更新、刪除的基本步驟應該都很清楚了。這里不再贅述。
值得注意的是，找到了map中的數(shù)據(jù)之后，針對key和value分別做如下操作：
1
2
3
4
1、如果``key``是一個指針類型的，則直接將其置為空，等待GC清除；
2、如果是值類型的，則清除相關內存。
3、同理，對``value``做相同的操作。
4、最后把key對應的高位值對應的數(shù)組index置為空。
在前一小節(jié)中介紹了點亮第一個LED燈，這里我們準備進階嘗試下，輸出第一段PWM波形。（PWM也就是脈寬調制，一種可調占空比的技術，得到的效果就是：如果用示波器測量引腳會發(fā)現(xiàn)有方波輸出，而且高電平、低電平的時間是可調的。）
這里爪爪熊準備寫成一個golang的庫，并開源到github上，后續(xù)更新將直接更新到github中，如果你有興趣可以和我聯(lián)系。 github.com/dpawsbear/bear_rpi_go
我在很多的教程中都看到說樹莓派的PWM（硬件）只有一個GPIO能夠輸出，就是 GPIO1 。這可是不小的打擊，因為我想使用至少四個 PWM ，還是不死心，想通過硬件手冊上找尋蛛絲馬跡，看看究竟怎么回事。
手冊上找尋東西稍等下講述，這里先提供一種方法測試 樹莓派3B 的 PWM 方法：用指令控制硬件PWM。
這里通過指令的方式掌握了基本的pwm設置技巧，決定去翻一下手冊看看到底PWM怎么回事，這里因為沒有 BCM2837 的手冊，根據(jù)之前文章引用官網(wǎng)所說， BCM2835 和 BCM2837 應該是一樣的。這里我們直接翻閱 BCM2835 的手冊，直接找到 PWM 章節(jié)。找到了如下圖：
圖中可以看到在博通的命名規(guī)則中 GPIO 12、13、18、19、40、41、45、52、53 均可以作為PWM輸出。但是只有兩路PWM0 PWM1。根據(jù)我之前所學知識，不出意外應該是PWM0 和 PWM1可以輸出不一樣的占空比，但是頻率應該是一樣的。因為沒有示波器，暫時不好測試。先找到下面對應圖：
根據(jù)以上兩個圖對比可以發(fā)現(xiàn)如下規(guī)律：
對照上面的表可以看出從 BCM2837 中印出來的能夠使用在PWM上的就這幾個了。
為了驗證個人猜想是否正確，這里先直接使用指令的模式，模擬配置下是否能夠正常輸出。
通過上面一系列指令模擬發(fā)現(xiàn)，（GPIO1、GPIO26）、（GPIO23、GPIO24）是綁定在一起的，調節(jié)任意一個，另外一個也會發(fā)生變化。也即是PWM0、PWM1雖然輸出了兩路，可以理解成兩路其實都是連在一個輸出口上。這里由于沒有示波器或者邏輯分析儀這類設備（僅有一個LED燈），所以測試很簡陋，下一步是使用示波器這類東西對頻率以及信號穩(wěn)定性進行下測試。
小節(jié)：樹莓派具有四路硬件輸出PWM能力，但是四路中只能輸出兩個獨立（占空比獨立）的PWM，同時四路輸出的頻率均是恒定的。
上面大概了解清楚了樹莓派3B的PWM結構，接下來就是探究如何使用Go語言進行設置。
因為拿到了手冊，這里我想直接操作寄存器的方式進行設置，也是順便學習下Go語言處理寄存器的過程。首先需要拿到pwm 系列寄存器的基地址，但是翻了一圈手冊，發(fā)現(xiàn)只有偏移，沒有找到基地址。
經(jīng)過了一段時間的努力后，決定寫一個 樹莓派3B golang包開源放在github上，只需要寫相關程序進行調用就可以了，以下是相關demo（pwm）（在GPIO.12 上輸出PWM波，放上LED燈會有呼吸燈的效果，具體多少頻率還沒有進行測試）
以下是demo(pwm) 源碼
作為C語言家族的一員，go和c一樣也支持結構體?？梢灶惐扔趈ava的一個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 開發(fā)中會經(jīng)常使用空 結構體類型元素，作為一種“事件”信息進行 Goroutine 之間的通信
這種以空結構體為元素類建立的 channel，是目前能實現(xiàn)的、內存占用最小的 Goroutine 間通信方式。
這種形式需要說的是幾個語法糖。
語法糖1：
對于結構體字段，可以省略字段名，只寫結構體名。默認字段名就是結構體名
這種方式稱為 嵌入字段
語法糖2：
如果是以嵌入字段形式寫的結構體
可以省略嵌入的Reader字段，而直接訪問ReaderName
此時book是一個各個屬性全是對應類型零值的一個實例。不是nil。這種情況在Go中稱為零值可用。不像java會導致npe
結構體定義時可以在字段后面追加標簽說明。
tag的格式為反單引號
tag的作用是可以使用[反射]來檢視字段的標簽信息。
具體的作用還要看使用的場景。
比如這里的tag是為了幫助 encoding/json 標準包在解析對象時可以利用的規(guī)則。比如omitempty表示該字段沒有值就不打印出來。
1、反射可以在運行時 動態(tài)獲取變量的各種信息 ，比如變量的類型、類別；
2、如果是結構體變量，還可以獲取到結構體本身的信息（包括結構體的字段、方法）；
3、通過反射，可以修改 變量的值 ，可以調用關聯(lián)的方法；
4、使用反射，需要import " reflect ".
5、示意圖：
1、不知道接口調用哪個函數(shù)，根據(jù)傳入?yún)?shù)在運行時確定調用的具體接口，這種需要對函數(shù)或方法反射。
例如以下這種橋接模式：
示例第一個參數(shù)funcPtr以接口的形式傳入函數(shù)指針，函數(shù)參數(shù)args以可變參數(shù)的形式傳入，bridge函數(shù)中可以用反射來動態(tài)執(zhí)行funcPtr函數(shù)。
1、reflect.TypeOf(變量名)，獲取變量的類型，返回reflect.Type類型。
2、reflect.ValueOf(變量名)，獲取變量的值，返回reflect.Value類型reflect.Value是一個結構體類型。
3、變量、interface{}和reflect.Value是可以互相轉換的，這點在實際開發(fā)中，會經(jīng)常使用到。
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、使用反射的方式來獲取變量的值（并返回對應的類型），要求數(shù)據(jù)類型匹配，比如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是編譯性語言，所以函數(shù)的順序是無關緊要的，為了方便閱讀，建議入口函數(shù) main 寫在最前面，其余函數(shù)按照功能需要進行排列
GO的函數(shù) 不支持嵌套，重載和默認參數(shù)
GO的函數(shù) 支持 無需聲明變量，可變長度，多返回值，匿名，閉包等
GO的函數(shù)用 func 來聲明，且左大括號 { 不能另起一行
一個簡單的示例：
輸出為：
參數(shù)：可以傳0個或多個值來供自己用
返回：通過用 return 來進行返回
輸出為：
上面就是一個典型的多參數(shù)傳遞與多返回值
對例子的說明：
按值傳遞：是對某個變量進行復制，不能更改原變量的值
引用傳遞：相當于按指針傳遞，可以同時改變原來的值，并且消耗的內存會更少，只有4或8個字節(jié)的消耗
在上例中，返回值 (d int, e int, f int) { 是進行了命名，如果不想命名可以寫成 (int,int,int){ ,返回的結果都是一樣的，但要注意:
當返回了多個值，我們某些變量不想要，或實際用不到，我們可以使用 _ 來補位，例如上例的返回我們可以寫成 d,_,f := test(a,b,c) ，我們不想要中間的返回值，可以以這種形式來舍棄掉
在參數(shù)后面以 變量 ... type 這種形式的，我們就要以判斷出這是一個可變長度的參數(shù)
輸出為：
在上例中， strs ...string 中， strs 的實際值是b,c,d,e,這就是一個最簡單的傳遞可變長度的參數(shù)的例子，更多一些演變的形式，都非常類似
在GO中 defer 關鍵字非常重要，相當于面相對像中的析構函數(shù)，也就是在某個函數(shù)執(zhí)行完成后，GO會自動這個；
如果在多層循環(huán)中函數(shù)里，都定義了 defer ,那么它的執(zhí)行順序是先進后出；
當某個函數(shù)出現(xiàn)嚴重錯誤時， defer 也會被調用
輸出為
這是一個最簡單的測試了，當然還有更復雜的調用，比如調試程序時，判斷是哪個函數(shù)出了問題，完全可以根據(jù) defer 打印出來的內容來進行判斷，非?？焖伲@種留給你們去實現(xiàn)
一個函數(shù)在函數(shù)體內自己調用自己我們稱之為遞歸函數(shù)，在做遞歸調用時，經(jīng)常會將內存給占滿，這是非常要注意的，常用的比如，快速排序就是用的遞歸調用
本篇重點介紹了GO函數(shù)(func)的聲明與使用，下一篇將介紹GO的結構 struct
重慶分公司
重慶分公司
