Penerangan pelaksanaan peta golang

Golang ialah bahasa pengaturcaraan yang baru muncul, dan petanya dilaksanakan berdasarkan jadual cincang. Dalam artikel ini, kita akan membincangkan bagaimana peta dilaksanakan di Golang. Secara khusus, kami akan memperkenalkan konsep jadual cincang, struktur dan pengoptimuman prestasi peta Golang.

Konsep jadual cincang

Jadual cincang ialah struktur data yang menyimpan data dalam pasangan nilai kunci. Ia memetakan kunci kepada indeks tatasusunan melalui fungsi cincang, menjadikan akses kepada data dalam jadual cincang lebih cekap.

Fungsi cincang mengira nilai yang dihantar kepadanya menjadi nilai panjang tetap kecil yang mengenal pasti kunci secara unik (ini dipanggil kod cincang). Kod cincang ini digunakan sebagai indeks tatasusunan.

Terdapat beberapa masalah dengan fungsi cincang. Satu ialah perlanggaran cincang, iaitu kunci yang berbeza dipetakan kepada indeks tatasusunan yang sama, yang perlu diselesaikan dengan menyelesaikan perlanggaran cincang. Satu lagi jenis masalah ialah ketidakcukupan fungsi cincang, yang mungkin tidak mengira kod cincang nilai dengan tepat, mengakibatkan pengagihan data yang tidak sekata dalam jadual cincang.

Struktur peta Golang

Di Golang, peta ialah struktur dan struktur data asasnya ialah jadual cincang. Khususnya, peta terdiri daripada tiga medan berikut:

type hmap struct {
    count int                                 
    flags uint32                              
    B     uint8                               
    hash0 uint32                              
    buckets unsafe.Pointer // 指向一个桶数组
    oldbuckets unsafe.Pointer // 用于扩容时的桶数组
    nevacuate uintptr // 当前将要被载入到oldbuckets的指针位置
    extra *mapextra
}

Antaranya, kiraan mewakili bilangan elemen dalam peta digunakan untuk merekodkan status peta, termasuk sama ada untuk memadam, mengulang, dsb.; B mewakili baldi Panjang tatasusunan, iaitu, 2 dinaikkan kepada kuasa Bth0 merekodkan benih cincang, yang digunakan untuk pengiraan fungsi cincang.

baldi ialah penunjuk yang menghala ke susunan baldi. Format tatasusunan baldi adalah seperti berikut:

type bmap struct {
    tophash [bucketCnt]uint8
    data    [1]struct{ key, value interface{} }
}

Antaranya, tophash ialah tatasusunan dengan panjang bucketCnt Setiap elemen mewakili elemen dalam bmap, dan nilainya ialah integer yang digunakan untuk mencari kunci dalam pasangan nilai. data ialah tatasusunan panjang 1 yang mengandungi pasangan nilai kunci. Format pasangan nilai kunci adalah seperti berikut:

type iface struct {
    tab  *itab
    data unsafe.Pointer
}

type itab struct {
    inter  *interfacetype
    _type  *_type
    link   *itab
    bad    int32
    inhash int32 // 是否在哈希表中
    funcbucket uintptr
    __hash uintptr // 哈希函数（方法）
    __eq   uintptr // 判断是否相等的函数（方法）
}

Antaranya, medan data adalah penunjuk kepada struktur iface Struktur iface mengandungi penunjuk kepada pasangan nilai kunci yang disimpan dan a penunjuk kepada maklumat jenis.

Pengoptimuman prestasi peta Golang

Pengoptimuman prestasi yang dilaksanakan oleh peta Golang terbahagi terutamanya kepada dua aspek berikut:

1. Peluasan tatasusunan baldi

Apabila bilangan elemen dalam peta melebihi kapasiti tatasusunan baldi, tatasusunan baldi perlu dikembangkan. Cara untuk mengembangkan adalah dengan menambah tatasusunan baldi baharu. Pada kali berikutnya peta diakses, semua pasangan nilai kunci akan dikira semula dan dipindahkan ke tatasusunan baldi baharu satu demi satu. Proses ini dipanggil rehash.

Semasa proses pengembangan tatasusunan baldi, Golang menggunakan teknologi yang dipanggil pencincangan rawak. Teknologi ini melaraskan benih cincang supaya pasangan nilai kunci boleh diagihkan dengan lebih sekata dalam tatasusunan baldi baharu semasa cincangan semula, sekali gus mengurangkan perlanggaran cincang.

2. Kunci pincang terbina dalam

Golang menggunakan mekanisme penguncian yang dipanggil kunci pincang dalam peta. Penguncian berat sebelah ialah teknik pengoptimuman Apabila kunci hanya diakses dengan rutin sekali sahaja, ia akan menggunakan ID benang goroutine ini untuk mengunci. Dengan cara ini, apabila rutin go ini perlu membuka kunci atau mengunci semula kunci, tidak perlu menukar benang kerana tiada rutin go lain akan mengakses kunci.

Ringkasan

Struktur data asas peta di Golang ialah jadual cincangan baldinya menggunakan teknologi pencincangan rawak untuk mencincang semula pasangan nilai kunci dan menggunakan mekanisme penguncian berat sebelah untuk mengunci dan. Tidak berkunci. Butiran pelaksanaan ini membolehkan peta di Golang berfungsi dengan baik dalam beberapa operasi struktur data biasa.

Atas ialah kandungan terperinci Penerangan pelaksanaan peta golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!