Kami akan membahas implementasi peta dalam bahasa tanpa obat generik, mempertimbangkan apa tabel hash, bagaimana ini diatur dalam Go, apa pro dan kontra dari implementasi ini, dan apa yang harus Anda perhatikan ketika menggunakan struktur ini.
Detail di bawah potongan.
Perhatian! Jika Anda sudah terbiasa dengan tabel hash di Go, saya menyarankan Anda untuk melewatkan dasar-dasar dan pergi di
sini , jika tidak ada risiko bosan saat yang paling menarik.
Apa itu tabel hash
Untuk memulainya, saya akan mengingatkan Anda apa itu tabel hash. Ini adalah struktur data yang memungkinkan Anda untuk menyimpan pasangan nilai kunci, dan, sebagai aturannya, memiliki fungsi:
- Pemetaan:
map(key) → value
- Sisipan:
insert(map, key, value)
- Penghapusan:
delete(map, key)
- Cari:
lookup(key) → value
Tabel hash dalam bahasa go
Tabel hash dalam bahasa go diwakili oleh kata kunci peta dan dapat dideklarasikan dengan salah satu cara di bawah ini (selengkapnya tentang mereka nanti):
m := make(map[key_type]value_type) m := new(map[key_type]value_type) var m map[key_type]value_type m := map[key_type]value_type{key1: val1, key2: val2}
Operasi utama dilakukan sebagai berikut:
- Masukkan:
m[key] = value
- Penghapusan:
delete(m, key)
- Cari:
value = m[key]
atau
value, ok = m[key]
Pergi berkeliling meja di mana saja
Pertimbangkan program berikut:
package main import "fmt" func main() { m := map[int]bool{} for i := 0; i < 5; i++ { m[i] = ((i % 2) == 0) } for k, v := range m { fmt.Printf("key: %d, value: %t\n", k, v) } }
Peluncuran 1:
key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true
Jalankan 2:
key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true key: 3, value: false
Seperti yang Anda lihat, output bervariasi dari satu menjalankan ke menjalankan. Dan semua karena peta di Go tidak berurutan, artinya, tidak dipesan. Ini berarti Anda tidak perlu bergantung pada pesanan saat berkeliling. Alasannya dapat ditemukan dalam kode sumber runtime bahasa:
Lokasi pencarian ditentukan
secara acak , ingat ini! Rumor mengatakan bahwa pengembang runtime memaksa pengguna untuk tidak bergantung pada pesanan.
Pergi mencari tabel
Mari kita lihat sepotong kode lagi. Misalkan kita ingin membuat pasangan "angka" - "angka kali 10":
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} fmt.Println(m, m[0], m[1], m[2]) }
Kami meluncurkan:
map[0:0 1:10] 0 10 0
Dan kami melihat bahwa ketika kami mencoba untuk mendapatkan nilai dua (yang kami lupa letakkan) kami mendapat 0. Kami menemukan baris dalam
dokumentasi yang menjelaskan perilaku ini: “Upaya untuk mengambil nilai peta dengan kunci yang tidak ada di peta akan mengembalikan nilai nol untuk jenis entri di peta. ", tetapi diterjemahkan ke dalam bahasa Rusia, ini berarti bahwa ketika kami mencoba untuk mendapatkan nilai dari peta, tetapi tidak ada di sana, kami mendapatkan" nilai tipe nol ", yang dalam hal angka 0. Apa yang harus dilakukan, jika kita ingin membedakan antara kasus 0 dan tidak adanya 2? Untuk melakukan ini, kami datang dengan bentuk khusus "penugasan berganda" - suatu bentuk di mana alih-alih nilai tunggal biasa, peta mengembalikan pasangan: nilai itu sendiri dan Boolean lain yang menjawab pertanyaan apakah kunci yang diminta ada di peta atau tidak "
Potongan kode yang sebelumnya akan terlihat seperti ini:
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} m2, ok := m[2] if !ok {
Dan saat startup, kami mendapatkan:
map[0:0 1:10] 0 10 20
Buat tabel di Go.
Misalkan kita ingin menghitung jumlah kemunculan setiap kata dalam sebuah string, mulai kamus untuk ini dan lanjutkan.
package main func main() { var m map[string]int for _, word := range []string{"hello", "world", "from", "the", "best", "language", "in", "the", "world"} { m[word]++ } for k, v := range m { println(k, v) } }
Apakah Anda melihat tangkapan
gopher ? - Dan dia!
Ketika kami mencoba memulai program semacam itu, kami mendapatkan kepanikan dan pesan "tugas untuk masuk di peta nil". Dan semua karena mapa adalah tipe referensi dan tidak cukup untuk mendeklarasikan variabel, Anda perlu menginisialisasi:
m := make(map[string]int)
Sedikit lebih rendah akan jelas mengapa ini bekerja seperti ini. Pada awalnya, sudah disajikan 4 cara untuk membuat peta, dua di antaranya kami periksa - deklarasi ini sebagai variabel dan pembuatan melalui make. Anda juga dapat membuat menggunakan desain "
Komposit literal "
map[key_type]value_type{}
dan jika Anda ingin, bahkan segera menginisialisasi dengan nilai-nilai, metode ini juga valid. Adapun pembuatan menggunakan baru - menurut saya, itu tidak masuk akal, karena fungsi ini mengalokasikan memori untuk variabel dan mengembalikan pointer ke itu diisi dengan nilai nol dari jenisnya, yang dalam kasus peta akan nihil (kami mendapatkan hasil yang sama seperti di var, lebih tepatnya sebuah pointer ke sana).
Bagaimana peta diteruskan ke suatu fungsi?
Misalkan kita memiliki fungsi yang mencoba mengubah angka yang diteruskan ke sana. Mari kita lihat apa yang terjadi sebelum dan sesudah panggilan:
package main func foo(n int) { n = 10 } func main() { n := 15 println("n before foo =", n) foo(n) println("n after foo =", n) }
Sebuah contoh, saya pikir, cukup jelas, tetapi masih termasuk kesimpulan:
n before foo = 15 n after foo = 15
Seperti yang mungkin Anda tebak, fungsi n datang dengan nilai, bukan oleh referensi, sehingga variabel asli tidak berubah.
Mari kita lakukan trik mapa yang serupa:
package main func foo(m map[int]int) { m[10] = 10 } func main() { m := make(map[int]int) m[10] = 15 println("m[10] before foo =", m[10]) foo(m) println("m[10] after foo =", m[10]) }
Dan lihatlah:
m[10] before foo = 15 m[10] after foo = 10
Nilainya telah berubah. "Yah, Mapa disahkan dengan referensi?", Anda bertanya.
Tidak. Tidak ada tautan di Go. Tidak mungkin membuat 2 variabel dengan 1 alamat, seperti dalam C ++ misalnya. Tapi kemudian Anda bisa membuat 2 variabel yang menunjuk ke alamat yang sama (tetapi ini adalah pointer, dan mereka dalam Go).
Misalkan kita memiliki fungsi fn yang menginisialisasi peta m. Pada fungsi utama, kita cukup mendeklarasikan variabel, mengirimkannya untuk menginisialisasi dan melihat apa yang terjadi setelahnya.
package main import "fmt" func fn(m map[int]int) { m = make(map[int]int) fmt.Println("m == nil in fn?:", m == nil) } func main() { var m map[int]int fn(m) fmt.Println("m == nil in main?:", m == nil) }
Kesimpulan:
m == nil in fn?: false
m == nil in main?: true
Jadi, variabel m diteruskan
oleh nilai , oleh karena itu, seperti dalam kasus meneruskan int reguler ke fungsi, itu tidak berubah (salinan lokal dari nilai dalam fn berubah). Lalu mengapa nilai yang terletak pada m itu sendiri berubah? Untuk menjawab pertanyaan ini, pertimbangkan kode dari runtime bahasa:
Map in Go hanyalah sebuah penunjuk ke struktur hmap. Ini adalah jawaban untuk pertanyaan mengapa, terlepas dari kenyataan bahwa peta dilewatkan ke fungsi berdasarkan nilai, nilai-nilai itu sendiri di dalamnya berubah - itu semua tentang penunjuk. Struktur hmap juga berisi yang berikut: jumlah elemen, jumlah "ember" (disajikan sebagai logaritma untuk mempercepat perhitungan), seeding untuk hash acak (untuk membuatnya lebih sulit untuk ditambahkan - coba mengambil kunci sehingga ada tabrakan terus-menerus), semua jenis bidang layanan dan yang paling penting, sebuah penunjuk ke kotak tempat nilai disimpan. Mari kita lihat gambarnya:
Gambar ini menunjukkan gambar skematis dari struktur dalam memori - ada header hmap, penunjuk yang merupakan peta di Go (dibuat ketika dideklarasikan dengan var, tetapi tidak diinisialisasi, yang menyebabkan program macet ketika mencoba memasukkannya). Bidang kotak adalah tempat penyimpanan pasangan nilai kunci, ada beberapa kotak seperti itu, masing-masing berisi 8 pasang. Pertama di "bucket" adalah slot untuk bit hash tambahan (e0..e7 disebut e - karena bit hash
tambahan ). Berikutnya adalah kunci dan nilai sebagai daftar semua kunci terlebih dahulu, lalu daftar semua nilai.
Menurut hash dari fungsi, ditentukan di mana "ember" kita beri nilai, di dalam setiap "ember" bisa ada hingga 8 tabrakan, di akhir setiap "ember" ada penunjuk ke yang lain, jika yang sebelumnya meluap.
Bagaimana peta itu tumbuh?
Di kode sumber, Anda dapat menemukan baris:
yaitu, jika ada rata-rata lebih dari 6,5 elemen di setiap bucket, terjadi peningkatan susunan bucket. Pada saat yang sama, array dialokasikan 2 kali lebih banyak, dan data lama disalin ke dalamnya dalam porsi kecil setiap penyisipan atau penghapusan, sehingga tidak membuat penundaan yang sangat besar. Oleh karena itu, semua operasi akan sedikit lebih lambat dalam proses evakuasi data (saat mencari, kami juga harus mencari di dua tempat). Setelah evakuasi yang berhasil, data baru mulai digunakan.
Mengambil alamat elemen peta.
Hal menarik lainnya - di awal menggunakan bahasa yang ingin saya lakukan seperti ini:
package main import ( "fmt" ) func main() { m := make(map[int]int) m[1] = 10 a := &m[1] fmt.Println(m[1], *a) }
Tapi Go mengatakan: "tidak dapat mengambil alamat m [1]". Penjelasan mengapa tidak mungkin untuk mengambil alamat nilai terletak pada prosedur evakuasi data. Bayangkan kita mengambil alamat nilai, dan kemudian mapa tumbuh, memori baru dialokasikan, data dievakuasi, yang lama dihapus, penunjuknya menjadi salah, sehingga operasi seperti itu dilarang.
Bagaimana peta diimplementasikan tanpa obat generik?
Baik antarmuka kosong, maupun pembuatan kode tidak ada hubungannya dengan itu, semuanya adalah untuk menggantikannya pada waktu kompilasi. Pertimbangkan apa fungsi akrab dari Go berubah menjadi:
v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
Kami melihat bahwa ada fungsi akses map untuk mengakses, masing-masing untuk menulis dan menghapus mapassign dan mapdelete. Semua operasi menggunakan unsafe.Pointer, yang tidak peduli apa yang ditunjukkannya, dan informasi tentang setiap nilai dijelaskan oleh
deskriptor tipe .
type mapType struct { key *_type elem *_type ...} type _type struct { size uintptr alg *typeAlg ...} type typeAlg struct { hash func(unsafe.Pointer, uintptr) uintptr equal func(unsafe.Pointer, unsafe.Pointer) bool...}
MapType menyimpan deskriptor (_type) kunci dan nilai. Untuk deskriptor tipe, operasi (typeAlg) perbandingan, mengambil hash, ukuran, dan sebagainya didefinisikan, jadi kami selalu tahu cara memproduksinya.
Sedikit lagi tentang cara kerjanya. Ketika kita menulis v = m [k] (mencoba mendapatkan nilai v dari kunci k), kompiler menghasilkan sesuatu seperti berikut:
kPointer := unsafe.Pointer(&k) vPointer := mapaccess1(typeOf(m), m, kPointer) v = *(*typeOfvalue)vPointer
Yaitu, kita mengambil sebuah pointer ke kunci, struktur mapType, dari mana kita menemukan deskriptor mana dari kunci dan nilai, pointer ke hmap itu sendiri (yaitu, peta) dan meneruskan semuanya ke mapaccess1, yang akan mengembalikan pointer ke nilai. Kami mengarahkan pointer ke tipe yang diinginkan, dereference dan mendapatkan nilainya.
Sekarang mari kita lihat kode pencarian dari runtime (yang sedikit disesuaikan untuk membaca):
func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {
Fungsi mencari kunci di peta dan mengembalikan pointer ke nilai yang sesuai, argumen sudah akrab bagi kita - ini adalah mapType, yang menyimpan deskriptor dari jenis dan nilai kunci, memetakan sendiri (mapHeader) dan pointer ke memori yang menyimpan kunci. Kami mengembalikan pointer ke memori yang menyimpan nilai.
if m == nil || m.count == 0 { return zero }
Selanjutnya, kami memeriksa apakah pointer ke header peta tidak nol, jika ada 0 elemen di sana dan mengembalikan nilai nol, jika demikian.
hash := t.key.hash(key, m.seed)
Kami menghitung hash kunci (kami tahu cara menghitung kunci yang diberikan dari deskriptor tipe). Lalu kami mencoba memahami "ember" mana yang perlu Anda tuju (sisa pembagian dengan jumlah "ember", perhitungannya hanya sedikit dipercepat). Kemudian kita menghitung hash tambahan (kita mengambil 8 bit hash paling signifikan) dan menentukan posisi "ember" dalam memori (aritmatika alamat).
for { for i := 0; i < 8; i++ { if b.extra[i] != extra {
Cari, jika Anda melihat, tidak begitu rumit: kita pergi melalui rantai "ember", pindah ke yang berikutnya, jika Anda tidak menemukannya. Pencarian di "bucket" dimulai dengan perbandingan cepat hash tambahan (itulah sebabnya e0 ... e7 di awal masing-masing adalah hash "mini" dari pasangan untuk perbandingan cepat). Jika tidak cocok, melangkah lebih jauh, jika tidak, maka kami memeriksa lebih hati-hati - kami menentukan di mana kunci yang dicurigai dicari terletak di memori, membandingkan apakah itu sama dengan apa yang diminta. Jika sama, tentukan posisi nilai dalam memori dan kembali. Seperti yang Anda lihat, tidak ada yang supranatural.
Kesimpulan
Gunakan peta, tetapi ketahui dan pahami cara kerjanya! Anda dapat menghindari menyapu dengan memahami beberapa seluk-beluk - mengapa Anda tidak dapat mengambil alamat nilainya, mengapa semuanya jatuh selama deklarasi tanpa inisialisasi, mengapa lebih baik mengalokasikan memori terlebih dahulu, jika jumlah elemen diketahui (kami akan menghindari evakuasi) dan banyak lagi.
Referensi:
"Pergi peta dalam aksi", Andrew Gerrand"Bagaimana go runtime mengimplementasikan peta secara efisien", Dave Cheney"Memahami tipe in go", William KennedyImplementasi peta di dalam, Keith Randallkode sumber peta, Go Runtimegolang specpergi efektifgambar gopher