Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Yksityiskohtainen kuvaus kartasta Go-kielen käytön aloittamiseksi

1.Perusmääritelmä

map on järjestämätön kokoelma avainarvopareja kv-muodossa

(1) Ominaisuudet

• Tyypin ominaisuudet: kartta on viitetyyppi, joten funktion arvon päivittäminen muuttaa sen pysyvästi.
• Peräkkäiset ominaisuudet: Kartan läpikulku on järjestämätöntä, koska alin kerros on hash-taulukko ja hash-taulukko on järjestämätön.
• Alustuskäyttö: 0-arvo tai alustamaton arvo on nolla. Alustamatonta arvoa ei voi määrittää, muuten se panikoi suoraan.
• Avainarvopari: avain ja arvo näkyvät aina pareittain, avain on ainutlaatuinen ja voi olla mitä tahansa vertailukelpoista tyyppiä
• Dynaaminen: avainarvo-pareja voidaan lisätä tai poistaa dynaamisesti ajon aikana ilman, että kokoa tarvitsee ilmoittaa etukäteen
• Nopea haku: kartta tarjoaa nopeat haku-, lisäys- ja poistotoiminnot keskimääräisellä aikamonimutkauksella O(1)
• Samanaikaisuus: Ei kierreturvallinen, lukitus vaaditaan turvallisuuden takaamiseksi

(2) Määritelmälausunto

var name map[key_type]value_type
1

• nimi: muuttujan nimi
• key_type: avaimen tyyppi
• value_type: arvon tyyppi

// 方式一
var m map[int]string = map[int]string{}

// 方式二
m := map[int]string{
    1 : "老一",
    2 : "老二",
    3 : "老三",
}

// 方式三：5代表容量，也就是在内存中占用多大的空间，可以省略
m := make(map[int]string,5)
1
2
3
4
5
6
7
8
9
10
11
12

2. Peruskäyttö

(1) Lisää elementtejä

• 1. Yleisin tapa on lisätä se, kun kartoitetaan literaaleja, kuten yllä olevassa menetelmässä 2 on esitetty.
• 2. Toinen vaihe on määrittää suoraan vastaava arvo määritetylle avaimelle.

mapName[key] = value

// 假设map名为m，key为int，value为string
m[5] = "老五"
1
2
3
4

(2) Poista elementit

Poista elementit avainten perusteella, eikä olemattomia avaimia poistettaessa ilmoiteta virheestä.

delete(mapName, key)  

// 假设map名为m，key为int，value为string
delete(m, 5)
1
2
3
4

(3) Muokkaa elementtejä

Voit muokata suoraan määritettyä avainta vastaavaa arvoa.

mapName[key] = newValue 

// 假设map名为m，key为int，value为string
m[5] = "五"
1
2
3
4

(4) Hanki elementtejä

Hae arvo avaimen mukaan, ok on lippubitti löytyykö se, tyyppi on Boolen

Jos arvoa ei löydy, virhettä ei raportoida ja vastaavaa tyyppiä oleva nolla-arvo palautetaan.

value, ok := mapName[key]
if !ok {
		fmt.Println(ok)
	}
1
2
3
4

(5) Läpi kaikki elementit

Huomaa: kartan läpikulku on järjestämätön

for key, value := range myMap {
   // 处理每对键值
}

// 例子
for i, s := range m {
		fmt.Println(i, s)
	}
1
2
3
4
5
6
7
8

3. Taustalla olevat periaatteet

Golangin kielen kartan perusolemus on käyttäähashmaptoteutettu, joten kartta on pohjimmiltaan哈希表。

哈希表on käyttöä哈希函数Järjestä tiedot tietorakenteiksi, jotka tukevat nopeaa lisäystä ja hakua.

哈希函数 , joka tunnetaan myös nimellä hash-funktio, on funktio, joka muuntaa minkä tahansa pituisen syötteen (kuten merkkijonon) kiinteän pituiseksi ulostuloksi tietyn hajautusalgoritmin avulla. Hash-arvot tallennetaan yleensä taulukon kaltaiseen muotoon, jotta varmistetaan hajautusarvojen käyttösuorituskyky.

Jos tulon alue ylittää yhdistetyn lähdön alueen, eri tulot voivat saada saman lähdön哈希冲突。

On yleensä kaksi tapaa ratkaista tämä ongelma:开放地址法ja拉链法

(1) Kartan toteutussuunnitelma

Avaa osoitemenetelmä:

Tietorakenteet toteutetaan yleensä taulukoiden avulla

• 1. Ensinnäkin taulukko koostuu erilaisista hash-arvoista, jota kutsutaan hash-taulukoksi.
• 2. Suorita sitten useita näppäimiä ja suorita hajautustoiminto varmistaaksesi, että osoite on sijoitettu vastaavaan paikkaan. Jos tämä tiivistetaulukon paikka on jo varattu, käytä tunnistussekvenssiä (kuten lineaarista tunnistusta, toissijaista tunnistusta tai kaksoishajautus). jne.) löytääksesi seuraavan avaimen ja tallentaaksesi ristiriitaiset avaimet.

puute:

Tämä lähestymistapa vaatii enemmän tilaa konfliktien ratkaisemiseen, koska tietoja ei vain tallenneta, vaan törmäysten ratkaiseminen vaatii lisätilaa.

Vetoketjumenetelmä (go Language Map käyttää tätä menetelmää):

Taustalla olevina tietorakenteina käytetään yleensä taulukoita ja linkitettyjä listoja

• 1. Ensinnäkin taulukko koostuu erilaisista hash-arvoista, joita kutsutaan hash-taulukoksi. Jokainen hash-taulukon paikka tallentaa linkitetyn luettelon.
• 2. Sitten tulee useita avaimia. Eri avainten hajautusarvon jälkeen lasketaan tiivistearvo ja se linkitetään taulukkoon myöhemmin
• 3. Kun haluat löytää tietyn avaimen, määritä ensin sen sijainti hash-funktiolla ja suorita sitten lineaarinen haku linkitetystä luettelosta kyseisessä paikassa, kunnes löydät vastaavan avaimen tai saavutat linkitetyn luettelon loppuun.

Matriisin eri indekseihin linkitettyä listaa kutsutaan myös ämpäriksi.

(2) Kartan taustalla oleva rakenne

hmap

type hmap struct {
 count     int // 当前哈希表中的元素数量，即键值对数量，可用内置函数len()获取
 flags     uint8  // 标志位，标记map状态和属性的字段，如正在迭代等状态
 B         uint8  // 表示哈希表桶（buckets）的数量为2的B次方
 noverflow uint16 // 溢出桶的大致数量，扩容时会用到
 hash0     uint32 // 哈希种子，对key做哈希是加入种子计算哈希值，确保map安全性

 buckets    unsafe.Pointer // 存储桶数组的指针
 oldbuckets unsafe.Pointer // 扩容时用于保存旧桶数组的指针 , 大小为新桶数组的一半
 nevacuate  uintptr        // 扩容时的迁移进度器，迁移桶下标小于此值说明完成迁移

 extra *mapextra // 溢出桶的指针，指向mapextra结构体，用于存储一些额外的字段和信息
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// mapextra 处理桶溢出的结构体
type mapextra struct {
 overflow    *[]*bmap    // 溢出桶数组指针，仅当key和elem非指针时才使用
 oldoverflow *[]*bmap    // 旧的溢出桶数组指针，仅当key和elem非指针时才使用

 nextOverflow *bmap      // 下一个可用的溢出桶地址
}

1
2
3
4
5
6
7
8

bmap

Lähdekoodissa bmap-tyypissä on vain yksi tophash-kenttä.Mutta kääntämisen aikana Go-kääntäjä syöttää automaattisesti vastaavat avaimet, arvot ja muut rakenteet käyttäjäkoodin mukaan.

Pinta bmap

type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

1
2
3
4
5
6
7
8
9
10
11
12

todellinen bmap

// 编译期间会动态地创建一个新的结构：
type bmap struct {
   topbits  [8]uint8   // 这里存储哈希值的高八位，用于在确定key的时候快速试错，加快增删改查寻址效率,有时候也叫tophash
   keys     [8]keytype   // 存储key的数组，这里bmap最多存储8个键值对
   elems   [8]valuetype    // 存储value的数组，这里bmap也最多存储8个键值对
   ...
   overflow uintptr     // 溢出桶指针
}

1
2
3
4
5
6
7
8
9

Kartta alla oleva kaavio

Kartan laajennus

Go-kielellä kartan laajennus suoritetaan automaattisesti kartan suorituskyvyn ylläpitämiseksi.

Ensinnäkin kirjoitettaessa kartta kulkeeruntime.mapassignSelvitä, tarvitaanko laajennusta

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 // If we hit the max load factor or we have too many overflow buckets,
 // and we're not already in the middle of growing, start growing.
 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again // Growing the table invalidates everything, so try again
 }
...
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
 if B > 15 {
  B = 15
 }
 return noverflow >= uint16(1)<<(B&15)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Yllä olevan koodin mukaan laajentumisen arvioinnissa on kaksi ehtoa:

• Kuormituskerroin ylittää kynnyksen 6,5:overLoadFactor(h.count+1, h.B) , kuormituskerroin = elementtien lukumäärä ÷ kauhojen lukumäärä
• Liian monta ylivuotokauhaa käytetty (yli 32768):tooManyOverflowBuckets(h.noverflow, h.B))

Laajennusmenetelmä:

• Inkrementaalinen laajennus:

Kun kuormituskerroin on liian suuri, luodaan uusi kauhan pituus, joka on kaksinkertainen alkuperäiseen pituuteen, ja sitten vanhat säiliötiedot siirretään uuteen.

• Tasainen kapasiteetin laajennus

Tietoa ei ole paljon, mutta ylivuotoryhmiä on liikaa.Laajennuksen aikana ryhmien määrä pysyy ennallaan Inkrementaalista laajennusta muistuttavat siirtotoiminnot ja löysät avainarvoparit järjestetään uudelleen segmentin käytön lisäämiseksi ja nopeamman käytön varmistamiseksi.

Laajennusvaiheet:

• 1. Uusi kauhamatriisi:Luo uusi alkuperäisellä koossakaksinkertainenUusi ämpäriryhmä merkitään laajennetuksi.

func hashGrow(t *maptype, h *hmap) {
 ...
 // 原有桶设置给oldbuckets
 oldbuckets := h.buckets   
 // 创建新桶
 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

 flags := h.flags &^ (iterator | oldIterator)
 if h.flags&iterator != 0 {
  flags |= oldIterator
 }
 // commit the grow (atomic wrt gc)
 h.B += bigger
 h.flags = flags
 h.oldbuckets = oldbuckets
 h.buckets = newbuckets
 h.nevacuate = 0
 h.noverflow = 0

 ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 2. Rehash: Käytä oldbuckets-komentoa osoittamaan alkuperäiseen segmenttitaulukkoon, kauhoja osoittamaan uuteen segmenttitaulukkoon, käy läpi kaikki avainarvoparit vanhassa ryhmätaulukossa ja käytä hash-funktiota laskeaksesi uudelleen kunkin avaimen sijainnin ja lisäämällä ne uuteen. ämpäriryhmä.

// 这个是mapdelete函数中的处理迁移的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 if h.growing() {
  // 
  growWork(t, h, bucket)
 }
...
}

1
2
3
4
5
6
7
8
9
10

• 3. Asteittainen muuttoliike: Jotta koko ohjelmaa ei keskeytettäisi laajennuksen aikana, Go's Map -toteutus voi valita渐进式驱逐 Siirrä avainarvoparit. Tämä tarkoittaa, että laajennuksen aikana vanha ja uusi segmenttiryhmä ovat olemassa samaan aikaan, äskettäin lisätyt avainarvoparit sijoitetaan suoraan uuteen säilöyn ja pääsy vanhaan ryhmään käynnistää siirtotoiminnon.

// 进入后是一个简单的判断，之后的evacuate是核心逻辑处理，特别多，感兴趣自己看源码
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

• 4. Päivitä sisäinen tila: Kun kaikki vanhojen ryhmien avainarvoparit siirretään, kartan sisäinen tila päivitetään ja vanhat kauhat poistetaan.

4. Käyttöskenaariot

• 1.Pikahaku: Kun haluat etsiä nopeasti arvoa avaimen perusteella, Map tarjoaa hakusuorituskyvyn keskimääräisellä aikakompleksisuudella O(1).
• 2.Poista kaksoiskappaleet: Kun yksilöllisiä avaimia on tallennettava, karttaavaimia ei sallita toistaa, ja kopiointitoiminto voidaan luonnollisesti saavuttaa.
• 3.dynaaminen kokoelma: Kartta tarjoaa joustavia toimintoja, kun avain-arvo-pareja on lisättävä tai poistettava dynaamisesti.
• 4.Linkitetyt tiedot: Kartta on hyvä valinta, kun tiedot ovat avain-arvo-parien muodossa ja niitä on päivitettävä tai tiedusteltava usein.

5. Käyttöehdotuksia

1. ennalta määrätty: Yritä käyttää make-toimintoa varaamaan kapasiteetti tunnetun kokoiselle kartalle.
2. Tietotyypin valinta: Käytä suurempia tietotyyppejä, kuteninttaiint64。
3. Osoittimen tallennustila: Jos rakenteet tai muuttujat sisältävät suuria tietomääriä, yritä käyttää osoittimia arvojen siirtämiseen ja tallentamiseen.
4. Samanaikaisuuden valvonta: Käytä samanaikaista käyttöä vartensync.MapTai ota käyttöön oma samanaikaisesti turvallinen karttasi.

6. Viitemateriaalit

• https://cloud.tencent.com/developer/article/2400014
• https://blog.csdn.net/qq_35289736/article/details/137480760/
• https://zhuanlan.zhihu.com/p/675715169/