Berbagi teknologi

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

Penjelasan mendetail tentang Peta untuk memulai bahasa Go

1.Definisi dasar

map adalah kumpulan pasangan nilai kunci yang tidak berurutan dalam format kv

(1) Fitur

• Karakteristik tipe: peta adalah tipe referensi, jadi memperbarui nilai dalam fungsi akan mengubahnya secara permanen.
• Karakteristik berurutan: Penjelajahan peta tidak berurutan, karena lapisan terbawah adalah tabel hash, dan tabel hash tidak berurutan.
• Penggunaan inisialisasi: Nilai 0 atau nilai yang tidak diinisialisasi adalah nihil. Nilai yang tidak diinisialisasi tidak dapat diberikan, jika tidak maka akan langsung panik.
• Pasangan kunci-nilai: kunci dan nilai selalu muncul berpasangan, kunci bersifat unik dan dapat berupa jenis apa pun yang sebanding
• Dinamis: pasangan nilai kunci dapat ditambahkan atau dihapus secara dinamis saat runtime tanpa perlu mendeklarasikan ukurannya terlebih dahulu
• Pencarian cepat: peta menyediakan operasi pencarian, penyisipan, dan penghapusan cepat, dengan kompleksitas waktu rata-rata O(1)
• Konkurensi: Tidak aman untuk thread, penguncian diperlukan untuk memastikan keamanan

(2) Pernyataan definisi

var name map[key_type]value_type
1

• nama: nama variabel
• key_type: jenis kunci
• value_type: jenis nilai

// 方式一
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. Penggunaan dasar

(1) Tambahkan elemen

• 1. Metode yang paling umum adalah menambahkannya ketika mendeklarasikan peta melalui literal, seperti yang ditunjukkan pada metode 2 di atas.
• 2. Langkah kedua adalah menetapkan langsung nilai yang sesuai untuk kunci yang ditentukan.

mapName[key] = value

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

(2) Hapus elemen

Hapus elemen berdasarkan kunci, dan tidak ada kesalahan yang akan dilaporkan saat menghapus kunci yang tidak ada.

delete(mapName, key)  

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

(3) Ubah elemen

Untuk memodifikasi, Anda dapat langsung mengubah nilai yang sesuai dengan kunci yang ditentukan.

mapName[key] = newValue 

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

(4) Dapatkan elemen

Dapatkan value sesuai keynya, ok flag bitnya apakah ketemu, typenya Boolean

Jika nilai tidak ditemukan, tidak ada kesalahan yang akan dilaporkan dan nilai null dari tipe yang sesuai akan dikembalikan.

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

(5) Lintasi semua elemen

Catatan: penjelajahan peta tidak berurutan

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

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

3. Prinsip-prinsip yang mendasari

Intisari peta dalam bahasa golang adalah penggunaanhashmapdiimplementasikan, jadi peta pada dasarnya哈希表。

哈希表adalah kegunaan哈希函数Atur data ke dalam struktur data yang mendukung penyisipan dan pencarian cepat.

哈希函数 , juga dikenal sebagai fungsi hash, adalah fungsi yang mengubah masukan dengan panjang berapa pun (seperti string) menjadi keluaran dengan panjang tetap melalui algoritma hash tertentu. Nilai hash biasanya disimpan dalam bentuk seperti array untuk memastikan kinerja akses nilai hash.

Jika rentang masukan melebihi rentang keluaran yang dipetakan, hal ini dapat menyebabkan masukan yang berbeda mendapatkan keluaran yang sama哈希冲突。

Biasanya ada dua cara untuk mengatasi masalah ini:开放地址法Dan拉链法

(1) Peta rencana pelaksanaan

Metode alamat terbuka:

Struktur data biasanya diimplementasikan menggunakan array

• 1. Pertama, array terdiri dari nilai hash yang berbeda, yang disebut tabel hash.
• 2. Kemudian jalankan banyak kunci dan lakukan fungsi hash untuk mengonfirmasi bahwa alamat ditempatkan pada posisi yang sesuai. Jika slot tabel hash ini sudah terisi, gunakan urutan deteksi (seperti deteksi linier, deteksi sekunder, atau hashing ganda , dll.) untuk menemukan kunci berikutnya. Slot yang tersedia dan simpan kunci yang bertentangan di sana.

kekurangan:

Pendekatan ini memerlukan lebih banyak ruang untuk menyelesaikan konflik karena tidak hanya data yang disimpan, namun ruang tambahan juga diperlukan untuk menyelesaikan konflik.

Metode ritsleting (peta bahasa go menggunakan metode ini):

Array dan daftar tertaut biasanya digunakan sebagai struktur data yang mendasarinya

• 1. Pertama-tama, array terdiri dari nilai hash yang berbeda, yang disebut tabel hash. Setiap slot tabel hash akan menyimpan daftar tertaut.
• 2. Kemudian banyak kunci yang masuk. Setelah melakukan hashing pada kunci yang berbeda, nilai hash dihitung secara moduloly dan dihubungkan ke array. Dalam kasus nilai hash yang sama (tabrakan hash), kunci baru akan digantung di daftar kunci yang ada . Nanti
• 3. Saat Anda perlu menemukan kunci tertentu, pertama-tama gunakan fungsi hash untuk menentukan lokasinya, lalu lakukan pencarian linier pada daftar tertaut di lokasi tersebut hingga Anda menemukan kunci yang cocok atau mencapai akhir daftar tertaut.

Daftar tertaut yang ditautkan pada indeks array yang berbeda juga disebut keranjang.

(2) Struktur yang mendasari peta

peta 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

peta b

Dalam kode sumber, tipe bmap hanya memiliki satu field tophash.Namun selama kompilasi, kompiler Go akan secara otomatis memasukkan kunci, nilai, dan struktur lain yang sesuai sesuai dengan kode pengguna.

Peta permukaan

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 sebenarnya

// 编译期间会动态地创建一个新的结构：
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

Petakan diagram yang mendasarinya

Perluasan peta

Dalam bahasa Go, perluasan peta dilakukan secara otomatis untuk menjaga performa peta.

Pertama, saat menulis, peta dilewatiruntime.mapassignTentukan apakah perluasan diperlukan

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

Berdasarkan kode di atas, ada dua kondisi untuk menilai perluasan:

• Faktor beban melebihi ambang batas 6,5:overLoadFactor(h.count+1, h.B) , faktor beban = jumlah elemen jumlah bucket
• Terlalu banyak ember luapan yang digunakan (melebihi 32768):tooManyOverflowBuckets(h.noverflow, h.B))

Metode ekspansi:

• Ekspansi tambahan:

Jika faktor beban terlalu besar, maka bucket baru akan dibuat dengan panjang bucket baru dua kali panjang aslinya, lalu data bucket lama akan dipindahkan ke bucket baru.

• Ekspansi kapasitas yang sama

Datanya tidak banyak, tetapi ada terlalu banyak wadah yang meluap.Selama perluasan, jumlah bucket tetap tidak berubah. Operasi relokasi serupa dengan perluasan tambahan dilakukan lagi, dan pasangan nilai kunci yang longgar disusun ulang untuk meningkatkan penggunaan bucket dan memastikan akses yang lebih cepat.

Langkah-langkah perluasan:

• 1. Susunan ember baru:Buat yang baru dengan ukuran aslinyadobelArray bucket baru akan ditandai sebagai diperluas.

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. Pengulangan: Gunakan oldbuckets untuk menunjuk ke array bucket asli, bucket untuk menunjuk ke array bucket baru, lintasi semua pasangan nilai kunci dalam array bucket lama, dan gunakan fungsi hash untuk menghitung ulang posisi setiap kunci dan memasukkannya ke dalam yang baru susunan ember.

// 这个是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. Migrasi bertahap: Untuk menghindari jeda seluruh program selama perluasan, implementasi Go's Map dapat memilih渐进式驱逐 Migrasikan pasangan nilai kunci. Artinya selama perluasan, susunan keranjang lama dan susunan keranjang baru akan ada pada saat yang sama, pasangan nilai kunci yang baru disisipkan akan ditempatkan langsung ke dalam keranjang baru, dan akses ke keranjang lama akan memicu operasi migrasi.

// 进入后是一个简单的判断，之后的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. Perbarui status internal: Ketika semua pasangan nilai kunci di oldbuckets dipindahkan, keadaan internal Peta akan diperbarui dan oldbuckets akan dihapus.

4. Skenario penggunaan

• 1.pencarian Cepat: Saat Anda perlu mencari nilai berdasarkan kunci dengan cepat, Map memberikan performa pencarian dengan kompleksitas waktu rata-rata O(1).
• 2.Hapus duplikat: Ketika kunci unik perlu disimpan, kunci Peta tidak boleh diulang, dan fungsi deduplikasi secara alami dapat dicapai.
• 3.koleksi dinamis: Peta menyediakan operasi yang fleksibel ketika pasangan nilai kunci perlu ditambahkan atau dihapus secara dinamis.
• 4.Data tertaut: Peta adalah pilihan yang baik ketika data ada dalam bentuk pasangan nilai kunci dan perlu sering diperbarui atau ditanyakan.

5. Saran penggunaan

1. dialokasikan sebelumnya: Coba gunakan fungsi make untuk mengalokasikan kapasitas ke peta dengan ukuran yang diketahui.
2. Pemilihan tipe data: Gunakan tipe data yang lebih besar, sepertiintatauint64。
3. Penyimpanan penunjuk: Untuk struktur atau variabel dengan data dalam jumlah besar, coba gunakan pointer untuk mentransfer dan menyimpan nilai.
4. Kontrol konkurensi: Untuk akses bersamaan, gunakansync.MapAtau terapkan Peta Anda sendiri yang aman secara bersamaan.

6. Bahan referensi

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