go語(yǔ)言map持久化 go 定義map

go語(yǔ)言怎樣處理 map 的值

// 先聲明map

你所需要的網(wǎng)站建設(shè)服務(wù)，我們均能行業(yè)靠前的水平為你提供.標(biāo)準(zhǔn)是產(chǎn)品質(zhì)量的保證，主要從事做網(wǎng)站、成都網(wǎng)站建設(shè)、企業(yè)網(wǎng)站建設(shè)、手機(jī)網(wǎng)站制作、網(wǎng)頁(yè)設(shè)計(jì)、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)制作、做網(wǎng)站、建網(wǎng)站。創(chuàng)新互聯(lián)擁有實(shí)力堅(jiān)強(qiáng)的技術(shù)研發(fā)團(tuán)隊(duì)及素養(yǎng)的視覺(jué)設(shè)計(jì)專才。

var m1 map[string]string

// 再使用make函數(shù)創(chuàng)建一個(gè)非nil的map，nil map不能賦值

m1 = make(map[string]string)

// 最后給已聲明的map賦值

m1["a"] = "aa"

m1["b"] = "bb"

// 直接創(chuàng)建

m2 := make(map[string]string)

// 然后賦值

m2["a"] = "aa"

m2["b"] = "bb"

// 初始化 + 賦值一體化

m3 := map[string]string{

"a": "aa",

"b": "bb",

}

望采納。。

// ==========================================

// 查找鍵值是否存在

if v, ok := m1["a"]; ok {

fmt.Println(v)

} else {

fmt.Println("Key Not Found")

}

// 遍歷map

for k, v := range m1 {

fmt.Println(k, v)

}

goland map底層原理

map 是Go語(yǔ)言中基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，在日常的使用中經(jīng)常被用到。但是它底層是如何實(shí)現(xiàn)的呢？

總體來(lái)說(shuō)golang的map是hashmap，是使用數(shù)組+鏈表的形式實(shí)現(xiàn)的，使用拉鏈法消除hash沖突。

golang的map由兩種重要的結(jié)構(gòu)，hmap和bmap(下文中都有解釋)，主要就是hmap中包含一個(gè)指向bmap數(shù)組的指針，key經(jīng)過(guò)hash函數(shù)之后得到一個(gè)數(shù)，這個(gè)數(shù)低位用于選擇bmap(當(dāng)作bmap數(shù)組指針的下表)，高位用于放在bmap的[8]uint8數(shù)組中，用于快速試錯(cuò)。然后一個(gè)bmap可以指向下一個(gè)bmap(拉鏈)。

Golang中map的底層實(shí)現(xiàn)是一個(gè)散列表，因此實(shí)現(xiàn)map的過(guò)程實(shí)際上就是實(shí)現(xiàn)散表的過(guò)程。在這個(gè)散列表中，主要出現(xiàn)的結(jié)構(gòu)體有兩個(gè)，一個(gè)叫 hmap (a header for a go map)，一個(gè)叫 bmap (a bucket for a Go map，通常叫其bucket)。這兩種結(jié)構(gòu)的樣子分別如下所示：

hmap :

圖中有很多字段，但是便于理解map的架構(gòu)，你只需要關(guān)心的只有一個(gè)，就是標(biāo)紅的字段： buckets數(shù)組 。Golang的map中用于存儲(chǔ)的結(jié)構(gòu)是bucket數(shù)組。而bucket(即bmap)的結(jié)構(gòu)是怎樣的呢？

bucket ：

相比于hmap，bucket的結(jié)構(gòu)顯得簡(jiǎn)單一些，標(biāo)紅的字段依然是“核心”，我們使用的map中的key和value就存儲(chǔ)在這里?！案呶还Ｖ怠睌?shù)組記錄的是當(dāng)前bucket中key相關(guān)的“索引”，稍后會(huì)詳細(xì)敘述。還有一個(gè)字段是一個(gè)指向擴(kuò)容后的bucket的指針，使得bucket會(huì)形成一個(gè)鏈表結(jié)構(gòu)。例如下圖：

由此看出hmap和bucket的關(guān)系是這樣的：

而bucket又是一個(gè)鏈表，所以，整體的結(jié)構(gòu)應(yīng)該是這樣的：

哈希表的特點(diǎn)是會(huì)有一個(gè)哈希函數(shù)，對(duì)你傳來(lái)的key進(jìn)行哈希運(yùn)算，得到唯一的值，一般情況下都是一個(gè)數(shù)值。Golang的map中也有這么一個(gè)哈希函數(shù)，也會(huì)算出唯一的值，對(duì)于這個(gè)值的使用，Golang也是很有意思。

Golang把求得的值按照用途一分為二：高位和低位。

如圖所示，藍(lán)色為高位，紅色為低位。 然后低位用于尋找當(dāng)前key屬于hmap中的哪個(gè)bucket，而高位用于尋找bucket中的哪個(gè)key。上文中提到：bucket中有個(gè)屬性字段是“高位哈希值”數(shù)組，這里存的就是藍(lán)色的高位值，用來(lái)聲明當(dāng)前bucket中有哪些“key”，便于搜索查找。 需要特別指出的一點(diǎn)是：我們map中的key/value值都是存到同一個(gè)數(shù)組中的。數(shù)組中的順序是這樣的:

并不是key0/value0/key1/value1的形式，這樣做的好處是：在key和value的長(zhǎng)度不同的時(shí)候，可 以消除padding(內(nèi)存對(duì)齊)帶來(lái)的空間浪費(fèi) 。

現(xiàn)在，我們可以得到Go語(yǔ)言map的整個(gè)的結(jié)構(gòu)圖了：(hash結(jié)果的低位用于選擇把KV放在bmap數(shù)組中的哪一個(gè)bmap中，高位用于key的快速預(yù)覽，用于快速試錯(cuò))

map的擴(kuò)容

當(dāng)以上的哈希表增長(zhǎng)的時(shí)候，Go語(yǔ)言會(huì)將bucket數(shù)組的數(shù)量擴(kuò)充一倍，產(chǎn)生一個(gè)新的bucket數(shù)組，并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。

加載因子

判斷擴(kuò)充的條件，就是哈希表中的加載因子(即loadFactor)。

加載因子是一個(gè)閾值，一般表示為：散列包含的元素?cái)?shù) 除以 位置總數(shù)。是一種“產(chǎn)生沖突機(jī)會(huì)”和“空間使用”的平衡與折中：加載因子越小，說(shuō)明空間空置率高，空間使用率小，但是加載因子越大，說(shuō)明空間利用率上去了，但是“產(chǎn)生沖突機(jī)會(huì)”高了。

每種哈希表的都會(huì)有一個(gè)加載因子，數(shù)值超過(guò)加載因子就會(huì)為哈希表擴(kuò)容。

Golang的map的加載因子的公式是：map長(zhǎng)度 / 2^B(這是代表bmap數(shù)組的長(zhǎng)度，B是取的低位的位數(shù))閾值是6.5。其中B可以理解為已擴(kuò)容的次數(shù)。

當(dāng)Go的map長(zhǎng)度增長(zhǎng)到大于加載因子所需的map長(zhǎng)度時(shí)，Go語(yǔ)言就會(huì)將產(chǎn)生一個(gè)新的bucket數(shù)組，然后把舊的bucket數(shù)組移到一個(gè)屬性字段oldbucket中。注意：并不是立刻把舊的數(shù)組中的元素轉(zhuǎn)義到新的bucket當(dāng)中，而是，只有當(dāng)訪問(wèn)到具體的某個(gè)bucket的時(shí)候，會(huì)把bucket中的數(shù)據(jù)轉(zhuǎn)移到新的bucket中。

如下圖所示：當(dāng)擴(kuò)容的時(shí)候，Go的map結(jié)構(gòu)體中，會(huì)保存舊的數(shù)據(jù)，和新生成的數(shù)組

上面部分代表舊的有數(shù)據(jù)的bucket，下面部分代表新生成的新的bucket。藍(lán)色代表存有數(shù)據(jù)的bucket，橘黃色代表空的bucket。

擴(kuò)容時(shí)map并不會(huì)立即把新數(shù)據(jù)做遷移，而是當(dāng)訪問(wèn)原來(lái)舊bucket的數(shù)據(jù)的時(shí)候，才把舊數(shù)據(jù)做遷移，如下圖：

注意：這里并不會(huì)直接刪除舊的bucket，而是把原來(lái)的引用去掉，利用GC清除內(nèi)存。

map中數(shù)據(jù)的刪除

如果理解了map的整體結(jié)構(gòu)，那么查找、更新、刪除的基本步驟應(yīng)該都很清楚了。這里不再贅述。

值得注意的是，找到了map中的數(shù)據(jù)之后，針對(duì)key和value分別做如下操作：

1

2

3

4

1、如果``key``是一個(gè)指針類型的，則直接將其置為空，等待GC清除；

2、如果是值類型的，則清除相關(guān)內(nèi)存。

3、同理，對(duì)``value``做相同的操作。

4、最后把key對(duì)應(yīng)的高位值對(duì)應(yīng)的數(shù)組index置為空。

可持久化數(shù)據(jù)結(jié)構(gòu)

最近在刷MIT 6.851，記錄下筆記。

可持久化數(shù)據(jù)結(jié)構(gòu)就是能存儲(chǔ)、查詢數(shù)據(jù)的歷史版本的數(shù)據(jù)結(jié)構(gòu)。

可持久化數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

MIT 6.854j-advanced-algorithms

很贊?。】上](méi)video。

Making Data Structures Persistent

太長(zhǎng)沒(méi)看

總結(jié)了下大致包括如下領(lǐng)域應(yīng)用：

并發(fā)事務(wù)的原子性（便于Rollback）、隔離性。

同上。

便于實(shí)現(xiàn)diff,rollback

可持久化數(shù)據(jù)結(jié)構(gòu)最初設(shè)計(jì)出來(lái)的目的是為了在高維查詢中降維，把其中一個(gè)維度當(dāng)做時(shí)間，用可持久化數(shù)據(jù)結(jié)構(gòu)處理效率更高

可以看下MIT 6.851老師的介紹。

這種思想在高維處理中很常見(jiàn)，比如求二維range sum query時(shí)候，把其中一個(gè)維度當(dāng)時(shí)間、拿來(lái)做掃描線也是這種降維思路（見(jiàn)《算法競(jìng)賽進(jìn)階指南》）：

可持久化數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

自己輪一個(gè).net可持久化庫(kù) Persistent Data Structures 下面有討論use case

中文翻譯見(jiàn) 可持久化數(shù)據(jù)結(jié)構(gòu)

Functional Go: 持久化數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

這部分可以看6.851視頻

6.851把鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的模型叫pointer machine model。對(duì)于基于pointer machine model的數(shù)據(jù)結(jié)構(gòu)，有沒(méi)有通用的方法將他們改造成persistent？

note see

video see

O(1)寫，讀時(shí)對(duì)于每個(gè)點(diǎn)都要執(zhí)行O(logm)的查詢。假設(shè)一次查詢要讀v個(gè)點(diǎn)，時(shí)間復(fù)雜度O(vlogm)

所以對(duì)寫友好，對(duì)讀不友好

看到這里有個(gè)問(wèn)題：每個(gè)點(diǎn)的history放hashmap里不就行了？讀時(shí)也只需要O(1)的查找

但這樣做的話，hashmap不支持ceil操作，因此要支持ceil沒(méi)辦法只能用有序結(jié)構(gòu)、log級(jí)別查詢

（這里的假設(shè)是有個(gè)全局時(shí)間戳，而不是每個(gè)key對(duì)應(yīng)一個(gè)自己的自增時(shí)間戳）

個(gè)人理解，想做可持久化key/value Map的話即可按這種方法，每個(gè)key對(duì)應(yīng)的entry存放所有歷史值，這也可以看成是鄰接表。

說(shuō)白了就是寫時(shí)分裂節(jié)點(diǎn)，從root開始分裂到要寫的點(diǎn)。將所有version的root存到字典里

上面兩個(gè)要么對(duì)寫不好，要么對(duì)讀不好，能否兼得？

難以置信，說(shuō)白了就是給path copying方法中每個(gè)node加一個(gè)log cache，最后算出來(lái)的寫時(shí)amortized time complexity就是O(1)了。

What about non-tree data structures？

平衡樹怎么處理？

平衡樹要旋轉(zhuǎn)，想想就感覺(jué)很難改造成持久化。6.854課件講的很粗沒(méi)懂。 算法競(jìng)賽中常用的可持久化平衡樹一般就是 可持久化無(wú)旋轉(zhuǎn) Treap ，省去了旋轉(zhuǎn)可持久化的復(fù)雜。

a. fat nodes

每個(gè)點(diǎn)存的log從version queue變成version tree,查詢每個(gè)點(diǎn)時(shí)要從樹中找到最近祖先

b. path copying

沒(méi)區(qū)別

c. modification box

怎么找根節(jié)點(diǎn)？

i. pointer per version，可能多個(gè)pointer指向一個(gè)root

ii.存root tree,查詢時(shí)先找最近祖先

怎么修改old version

i. 修改時(shí)放box,滿了就分裂出來(lái)一個(gè)新節(jié)點(diǎn)

但這樣有問(wèn)題：分裂出來(lái)的還是滿的，如果整條鏈都是滿的，每次修改復(fù)制全部，下次修改還得復(fù)制全部。而且這樣還不好存root，比如最右邊圖，代表0的root有倆

ii. 修改時(shí)放box,滿了就分裂出來(lái)一個(gè)新節(jié)點(diǎn)，但分裂時(shí)自動(dòng)apply有用的log、丟棄沒(méi)用的log

What about non-tree data structures？

6.851有講，分裂成兩個(gè)節(jié)點(diǎn)，log分成兩部分，新節(jié)點(diǎn)拿一個(gè)子樹的log，新節(jié)點(diǎn)apply log直到自己的子樹，每部分丟棄自己用不到的。

6.851講了 太復(fù)雜沒(méi)聽懂。

網(wǎng)上關(guān)于可持久化數(shù)據(jù)結(jié)構(gòu)的優(yōu)質(zhì)資料都是算法競(jìng)賽的，因此收集總結(jié)了下競(jìng)賽常用的?？戳讼禄径际莗artial persistent,有的是fully persistent,都沒(méi)用到modification box技術(shù)。

和可持久化線段樹類似的方法，基于path copy實(shí)現(xiàn)partial persistence。

問(wèn)題是每個(gè)點(diǎn)在拷貝時(shí)都要復(fù)制O(R)個(gè)指針，插入的時(shí)間復(fù)雜度為O(len*R)

查詢時(shí)先從字典（數(shù)組/哈希表）里找到指定version的root，然后訪問(wèn)，O(len)

在競(jìng)賽中常用的是可持久化01字典樹，比如xor問(wèn)題，見(jiàn) ，沒(méi)看懂

算法競(jìng)賽中常用的可持久化平衡樹一般就是 可持久化無(wú)旋轉(zhuǎn) Treap ，省去了旋轉(zhuǎn)可持久化的復(fù)雜。

【AgOHの數(shù)據(jù)結(jié)構(gòu)】可持久化數(shù)組

方案：

a. fat nodes

每個(gè)節(jié)點(diǎn)放所有歷史，查詢時(shí)在所有歷史版本中找最近祖先版本

b. path copying

存到可持久化線段樹里。

為什么好好的線性結(jié)構(gòu)要樹化？直覺(jué)上理解，是為了分裂新版本時(shí)減少指針復(fù)制。

如果是稀疏數(shù)組，樸素方法太浪費(fèi)空間了，可以基于動(dòng)態(tài)開點(diǎn)來(lái)優(yōu)化空間存儲(chǔ)，見(jiàn)

【AgOHの數(shù)據(jù)結(jié)構(gòu)】可持久化并查集

并查集基于數(shù)組，可持久化并查集就基于可持久化數(shù)組?？沙志没瘮?shù)組用可持久化線段樹實(shí)現(xiàn)，因此可持久化并查集用可持久化線段樹實(shí)現(xiàn)

《 可持久化數(shù)據(jù)結(jié)構(gòu)研究 》

不過(guò)文中寫的太簡(jiǎn)略了，個(gè)人推測(cè)的維護(hù)方法為：

討論支持如下操作的抽象數(shù)據(jù)結(jié)構(gòu)(ADT)如何可持久化：

a. 基于普通數(shù)組

只能copy on write

b. 基于可持久化數(shù)組/可持久化線段樹

問(wèn)題是怎么處理新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)？得想辦法魔改線段樹

c. 可持久化鏈表

d. 可持久化塊狀鏈表

e. 可持久化平衡樹

f. 文中提到的vector trie

名字挺騷的沒(méi)反應(yīng)過(guò)來(lái)，看了一會(huì)發(fā)現(xiàn)：這玩意就是可持久化數(shù)組（可持久化線段樹），只不過(guò)是多叉樹，叫“可持久化多叉線段樹”比較形象。文章也沒(méi)提怎么處理新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)。

persistent-hash-table-implementation

a. 可持久化平衡樹

b. 還用hashmap，但是每個(gè)entry改造成fat node（存放所有l(wèi)og)，查詢時(shí)先找到entry，再在所有l(wèi)og 中找最近祖先版本

c. 可持久化數(shù)組。

考慮到HashMap本來(lái)就能只用一個(gè)數(shù)組實(shí)現(xiàn)（解決沖突時(shí)用open addressing方法，不用Chaining），那么實(shí)現(xiàn)了可持久化數(shù)組就相當(dāng)于實(shí)現(xiàn)了可持久化HashMap

d. Hash_trie

hash(key)的值存在trie里,value放到trie的葉子節(jié)點(diǎn)。優(yōu)化版本包括 Hash array mapped tries and Ctries

HAMT這名字起的很奇怪。原理就是塊狀hash trie（所謂塊狀是我自己起的名，指每個(gè)節(jié)點(diǎn)區(qū)分兒子時(shí)不是單純的比較某1位，而是比較某2位甚至多位）（或者理解成hash trie+動(dòng)態(tài)開點(diǎn)多叉線段樹也行）（反正就是bitwise hash trie加上一堆優(yōu)化，懶得記就記hash trie就行了，真要自己實(shí)現(xiàn)的時(shí)候這些優(yōu)化trick也能想到）

文中講hamt的碰撞處理有點(diǎn)扯，個(gè)人理解可以chaining，可以open addressing。細(xì)節(jié)沒(méi)深究，可以看 論文 和 討論 。按作者的意思AMT是之前他提出的一種Trie的優(yōu)化，比Tenary search trie要好。

// TOOD

Planar Point Location問(wèn)題見(jiàn)

樸素的方法是線段樹套線段樹，以便支持二維RMQ，時(shí)間復(fù)雜度O(logN*logN）。

個(gè)人理解，最優(yōu)的二維RMQ數(shù)據(jù)結(jié)構(gòu)應(yīng)該是用modification box實(shí)現(xiàn)的可持久化值域線段樹，O(N)的構(gòu)造時(shí)間、空間，O(logN)的查詢。

如果統(tǒng)計(jì)操作具有“區(qū)間可加性”、“區(qū)間可減性”，那么該操作二維統(tǒng)計(jì)問(wèn)題可以使用可持久化線段樹。

range minimum query中的min()操作其實(shí)不具有區(qū)間可減性，但是range minimum query問(wèn)題可以歸約成range select query問(wèn)題，進(jìn)而可以歸約成range count query問(wèn)題，而count()操作具有區(qū)間可加減性，因此也能用可持久化線段樹。

所以我們得到了一類二維統(tǒng)計(jì)問(wèn)題的通用數(shù)據(jù)結(jié)構(gòu)：對(duì)于可歸約成具有“區(qū)間可加性”、“區(qū)間可減性”統(tǒng)計(jì)操作的二維統(tǒng)計(jì)問(wèn)題，可以使用可持久化線段樹存儲(chǔ)，以便支持快速查詢（統(tǒng)計(jì)）。

能否找到一類高維統(tǒng)計(jì)問(wèn)題，具有通用的logN級(jí)別解？個(gè)人理解可以借鑒代數(shù)的思想，只要有區(qū)間可加減性的都能歸約成K維RMQ問(wèn)題，用modification box實(shí)現(xiàn)的可持久化值域線段樹解決。

// TOOD 只是個(gè)人暢想，沒(méi)細(xì)想。

bigtable(hbase)可以看成外存模型下的可持久化map：

但需要注意的是刪除操作會(huì)真的刪掉之前的老版本數(shù)據(jù)：

其實(shí)任何支持前綴匹配的db都能作為可持久化map，你只需要把rowkey設(shè)計(jì)成"key@@timestamp"即可

網(wǎng)頁(yè)題目：go語(yǔ)言map持久化 go 定義map
文章位置：http://muchs.cn/article32/hjdjsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、品牌網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站制作、小程序開發(fā)、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)