Κοινή χρήση τεχνολογίας

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

Λεπτομερής επεξήγηση του χάρτη για να ξεκινήσετε με τη γλώσσα Go

1.Βασικός ορισμός

Ο χάρτης είναι μια μη ταξινομημένη συλλογή ζευγών κλειδιών-τιμών σε μορφή kv

(1) Χαρακτηριστικά

• Χαρακτηριστικά τύπου: ο χάρτης είναι ένας τύπος αναφοράς, επομένως η ενημέρωση της τιμής στη συνάρτηση θα τον αλλάξει οριστικά.
• Διαδοχικά χαρακτηριστικά: Η διέλευση του χάρτη δεν είναι διατεταγμένη, επειδή το κάτω στρώμα είναι ένας πίνακας κατακερματισμού και ο πίνακας κατακερματισμού είναι μη ταξινομημένος.
• Χρήση αρχικοποίησης: Η τιμή 0 ή η μη αρχικοποιημένη τιμή δεν μπορεί να εκχωρηθεί, διαφορετικά θα πανικοβληθεί απευθείας.
• Ζεύγος κλειδιού-τιμής: το κλειδί και η τιμή εμφανίζονται πάντα σε ζεύγη, το κλειδί είναι μοναδικό και μπορεί να είναι οποιουδήποτε συγκρίσιμου τύπου
• Δυναμική: τα ζεύγη κλειδιών-τιμών μπορούν να προστεθούν ή να διαγραφούν δυναμικά κατά το χρόνο εκτέλεσης χωρίς να χρειάζεται να δηλώσετε το μέγεθος εκ των προτέρων
• Γρήγορη αναζήτηση: ο χάρτης παρέχει γρήγορες λειτουργίες αναζήτησης, εισαγωγής και διαγραφής, με μέση χρονική πολυπλοκότητα O(1)
• Ταυτόχρονα: Δεν είναι ασφαλές για το νήμα, απαιτείται κλείδωμα για να διασφαλιστεί η ασφάλεια

(2) Δήλωση ορισμού

var name map[key_type]value_type
1

• όνομα: όνομα μεταβλητής
• key_type: τύπος κλειδιού
• value_type: τύπος τιμής

// 方式一
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.Βασική χρήση

(1) Προσθέστε στοιχεία

• 1. Η πιο συνηθισμένη μέθοδος είναι η προσθήκη του κατά τη δήλωση χάρτη μέσω κυριολεκτικών, όπως φαίνεται στη μέθοδο 2 παραπάνω.
• 2. Το δεύτερο βήμα είναι να ορίσετε απευθείας την αντίστοιχη τιμή για το καθορισμένο κλειδί.

mapName[key] = value

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

(2) Διαγραφή στοιχείων

Διαγράψτε στοιχεία με βάση κλειδιά και δεν θα αναφερθεί κανένα σφάλμα κατά τη διαγραφή ανύπαρκτων κλειδιών.

delete(mapName, key)  

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

(3) Τροποποίηση στοιχείων

Για τροποποίηση, μπορείτε να τροποποιήσετε απευθείας την τιμή που αντιστοιχεί στο καθορισμένο κλειδί.

mapName[key] = newValue 

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

(4) Λάβετε στοιχεία

Λάβετε την τιμή σύμφωνα με το κλειδί, εντάξει είναι το bit σημαίας είτε βρίσκεται, ο τύπος είναι Boolean

Εάν η τιμή δεν βρεθεί, δεν θα αναφερθεί κανένα σφάλμα και θα επιστραφεί μηδενική τιμή του αντίστοιχου τύπου.

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

(5) Διασχίστε όλα τα στοιχεία

Σημείωση: η διέλευση του χάρτη δεν είναι διατεταγμένη

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

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

3. Βασικές αρχές

Η βασική ουσία του χάρτη στη γλώσσα golang είναι η χρήσηhashmapυλοποιείται, οπότε ο χάρτης είναι ουσιαστικά哈希表。

哈希表είναι χρήση哈希函数Οργανώστε τα δεδομένα σε δομές δεδομένων που υποστηρίζουν γρήγορη εισαγωγή και αναζήτηση.

哈希函数 , επίσης γνωστή ως συνάρτηση κατακερματισμού, είναι μια συνάρτηση που μετατρέπει μια είσοδο οποιουδήποτε μήκους (όπως μια συμβολοσειρά) σε μια έξοδο σταθερού μήκους μέσω ενός συγκεκριμένου αλγορίθμου κατακερματισμού. Οι τιμές κατακερματισμού συνήθως αποθηκεύονται σε μια μορφή που μοιάζει με πίνακα για να διασφαλιστεί η απόδοση πρόσβασης των τιμών κατακερματισμού.

Εάν το εύρος της εισόδου υπερβαίνει το εύρος της αντιστοιχισμένης εξόδου, μπορεί να προκαλέσει διαφορετικές εισόδους να λάβουν την ίδια έξοδο哈希冲突。

Υπάρχουν συνήθως δύο τρόποι για να λυθεί αυτό το πρόβλημα:开放地址法και拉链法

(1) Σχέδιο υλοποίησης χάρτη

Μέθοδος ανοιχτής διεύθυνσης:

Οι δομές δεδομένων συνήθως υλοποιούνται χρησιμοποιώντας πίνακες

• 1. Πρώτον, ο πίνακας αποτελείται από διαφορετικές τιμές κατακερματισμού, που ονομάζεται πίνακας κατακερματισμού.
• 2. Στη συνέχεια, εκτελέστε πολλά πλήκτρα και εκτελέστε μια λειτουργία κατακερματισμού για να επιβεβαιώσετε ότι η διεύθυνση έχει τοποθετηθεί στην αντίστοιχη θέση Εάν αυτή η υποδοχή του πίνακα κατακερματισμού είναι ήδη κατειλημμένη, χρησιμοποιήστε μια ακολουθία ανίχνευσης (όπως γραμμική ανίχνευση, δευτερεύουσα ανίχνευση ή διπλό κατακερματισμό. , κ.λπ.) για να βρείτε το επόμενο κλειδί και να αποθηκεύσετε τα κλειδιά σε διένεξη.

έλλειψη:

Αυτή η προσέγγιση απαιτεί περισσότερο χώρο για την επίλυση διενέξεων, επειδή όχι μόνο αποθηκεύονται τα δεδομένα, αλλά απαιτείται επιπλέον χώρος για την επίλυση συγκρούσεων.

Μέθοδος φερμουάρ (ο χάρτης γλώσσας go χρησιμοποιεί αυτήν τη μέθοδο):

Οι πίνακες και οι συνδεδεμένες λίστες χρησιμοποιούνται συνήθως ως υποκείμενες δομές δεδομένων

• 1. Πρώτα απ 'όλα, ο πίνακας αποτελείται από διαφορετικές τιμές κατακερματισμού, που ονομάζεται πίνακας κατακερματισμού Κάθε υποδοχή του πίνακα κατακερματισμού θα αποθηκεύει μια συνδεδεμένη λίστα.
• 2. Στη συνέχεια θα εισέλθουν πολλά κλειδιά. Αφού κατακερματίσετε διαφορετικά κλειδιά, η τιμή κατακερματισμού υπολογίζεται διαμορφωτικά και συνδέεται με τον πίνακα στην περίπτωση της ίδιας τιμής κατακερματισμού (σύγκρουση κατακερματισμού), το νέο κλειδί θα αναρτηθεί στην υπάρχουσα λίστα κλειδιών . αργότερα
• 3. Όταν πρέπει να βρείτε ένα συγκεκριμένο κλειδί, χρησιμοποιήστε πρώτα μια συνάρτηση κατακερματισμού για να προσδιορίσετε τη θέση του και, στη συνέχεια, εκτελέστε μια γραμμική αναζήτηση στη συνδεδεμένη λίστα σε αυτήν τη θέση μέχρι να βρείτε ένα αντίστοιχο κλειδί ή να φτάσετε στο τέλος της συνδεδεμένης λίστας.

Μια συνδεδεμένη λίστα που συνδέεται σε διαφορετικά ευρετήρια ενός πίνακα ονομάζεται επίσης κάδος.

(2) Η υποκείμενη δομή του χάρτη

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

Στον πηγαίο κώδικα, ο τύπος bmap έχει μόνο ένα πεδίο tophash.Αλλά κατά τη διάρκεια της μεταγλώττισης, ο μεταγλωττιστής Go θα εισάγει αυτόματα το αντίστοιχο κλειδί, την τιμή και άλλες δομές σύμφωνα με τον κωδικό χρήστη.

Επιφάνεια 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

πραγματικό 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

Υποκείμενο διάγραμμα χάρτη

Επέκταση χάρτη

Στη γλώσσα Go, η επέκταση χάρτη εκτελείται αυτόματα για να διατηρηθεί η απόδοση του χάρτη.

Πρώτον, όταν γράφετε, περνάει ο χάρτηςruntime.mapassignΠροσδιορίστε εάν χρειάζεται επέκταση

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

Σύμφωνα με τον παραπάνω κώδικα, υπάρχουν δύο προϋποθέσεις για να κριθεί η επέκταση:

• Ο συντελεστής φορτίου υπερβαίνει το όριο 6,5:overLoadFactor(h.count+1, h.B) , συντελεστής φορτίου = αριθμός στοιχείων ÷ αριθμός κάδων
• Χρησιμοποιήθηκαν πάρα πολλοί κάδοι υπερχείλισης (υπέρβαση των 32768):tooManyOverflowBuckets(h.noverflow, h.B))

Μέθοδος επέκτασης:

• Σταδιακή επέκταση:

Όταν ο συντελεστής φορτίου είναι πολύ μεγάλος, δημιουργείται ένας νέος κάδος Το μήκος του νέου κάδου είναι διπλάσιο από το αρχικό μήκος και, στη συνέχεια, τα δεδομένα του παλιού κάδου μετακινούνται στον νέο κάδο.

• Ίση επέκταση χωρητικότητας

Δεν υπάρχουν πολλά δεδομένα, αλλά υπάρχουν πάρα πολλοί κάδοι υπερχείλισης.Κατά τη διάρκεια της επέκτασης, ο αριθμός των κουβάδων παραμένει αμετάβλητος Οι λειτουργίες μετεγκατάστασης παρόμοιες με τη σταδιακή επέκταση εκτελούνται ξανά και τα χαλαρά ζεύγη κλειδιών-τιμών αναδιατάσσονται για να αυξηθεί η χρήση του κάδου και να εξασφαλιστεί ταχύτερη πρόσβαση.

Βήματα επέκτασης:

• 1. Νέα συστοιχία κάδου:Δημιουργήστε ένα νέο με το αρχικό μέγεθοςδιπλόΟ νέος πίνακας κάδου θα επισημανθεί ως διευρυμένος.

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: Χρησιμοποιήστε παλιούς κάδους για να δείξετε τον αρχικό πίνακα κάδου, κουβάδες για να δείχνουν τον νέο πίνακα κάδου, διασχίστε όλα τα ζεύγη κλειδιών-τιμών στον παλιό πίνακα κάδου και χρησιμοποιήστε τη συνάρτηση κατακερματισμού για να υπολογίσετε ξανά τη θέση κάθε κλειδιού και να τα εισαγάγετε στο νέο συστοιχία κάδου.

// 这个是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. Σταδιακή μετανάστευση: Προκειμένου να αποφευχθεί η παύση ολόκληρου του προγράμματος κατά την επέκταση, η εφαρμογή Go's Map μπορεί να επιλέξει渐进式驱逐 Μετεγκατάσταση ζευγών κλειδιού-τιμής. Αυτό σημαίνει ότι κατά την επέκταση, ο παλιός πίνακας κάδου και ο νέος πίνακας κάδου θα υπάρχουν ταυτόχρονα, τα ζεύγη κλειδιού-τιμής που έχουν εισαχθεί πρόσφατα θα τοποθετηθούν απευθείας στον νέο κάδο και η πρόσβαση στον παλιό κάδο θα ενεργοποιήσει μια λειτουργία μετεγκατάστασης.

// 进入后是一个简单的判断，之后的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. Ενημερώστε την εσωτερική κατάσταση: Όταν όλα τα ζεύγη κλειδιών-τιμών στους παλιούς κάδους μεταφερθούν, η εσωτερική κατάσταση του χάρτη θα ενημερωθεί και οι παλιοί κάδοι θα διαγραφούν.

4.Σενάρια χρήσης

• 1.γρήγορη αναζήτηση: Όταν χρειάζεται να αναζητήσετε γρήγορα μια τιμή με βάση ένα κλειδί, ο χάρτης παρέχει απόδοση αναζήτησης με μέση χρονική πολυπλοκότητα O(1).
• 2.Αφαιρέστε τα διπλότυπα: Όταν χρειάζεται να αποθηκευτούν μοναδικά κλειδιά, δεν επιτρέπεται η επανάληψη των πλήκτρων χάρτη και η λειτουργία κατάργησης διπλότυπων μπορεί φυσικά να επιτευχθεί.
• 3.δυναμική συλλογή: Ο χάρτης παρέχει ευέλικτες λειτουργίες όταν πρέπει να προστεθούν ή να διαγραφούν δυναμικά ζεύγη κλειδιών-τιμών.
• 4.Συνδεδεμένα δεδομένα: Ο χάρτης είναι μια καλή επιλογή όταν τα δεδομένα υπάρχουν με τη μορφή ζευγών κλειδιών-τιμών και πρέπει να ενημερώνονται ή να υποβάλλονται συχνά ερωτήματα.

5. Προτάσεις χρήσης

1. προκατανεμηθεί: Δοκιμάστε να χρησιμοποιήσετε τη συνάρτηση make για να εκχωρήσετε χωρητικότητα σε χάρτη γνωστού μεγέθους.
2. Επιλογή τύπου δεδομένων: Χρησιμοποιήστε μεγαλύτερους τύπους δεδομένων, όπως π.χintήint64。
3. Αποθήκευση δείκτη: Για δομές ή μεταβλητές με μεγάλο όγκο δεδομένων, προσπαθήστε να χρησιμοποιήσετε δείκτες για τη μεταφορά και αποθήκευση τιμών.
4. Έλεγχος συγχρονισμού: Για ταυτόχρονη πρόσβαση, χρησιμοποιήστεsync.MapΉ εφαρμόστε τον δικό σας ταυτόχρονα ασφαλή Χάρτη.

6.Υλικά αναφοράς

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