Standar ECMAScript 2015 , dikenal sebagai ES6, ada banyak JavaScript-koleksi baru seperti
Map, Set, WeakMapdan WeakSet. Mereka tampaknya menjadi tambahan yang bagus untuk kemampuan JavaScript standar. Mereka banyak digunakan di berbagai pustaka, dalam aplikasi, di inti Node.js. Hari ini kita akan berbicara tentang koleksi Map, mencoba mencari tahu secara spesifik penerapannya di V8 dan menarik beberapa kesimpulan praktis berdasarkan pengetahuan yang diperoleh.
Standar ES6 tidak memberikan indikasi yang jelas tentang pendekatan yang harus diambil untuk mengimplementasikan dukungan struktur data
Map. Ini hanya memberikan beberapa petunjuk tentang kemungkinan cara untuk menerapkannya. Ini juga berisi informasi tentang yang diharapkan dariMapMetrik kinerja:
Objek Map harus diimplementasikan menggunakan tabel hash atau mekanisme lain yang, rata-rata, menyediakan akses sublinear ke elemen koleksi. Struktur data yang digunakan dalam spesifikasi Map hanya dimaksudkan untuk mendeskripsikan semantik obyek Map yang dapat diamati. Mereka tidak dipahami sebagai model nyata untuk implementasi objek-objek ini.
Seperti yang Anda lihat, spesifikasinya memberi mereka yang membuat mesin JS banyak kebebasan. Namun pada saat yang sama, tidak ada pedoman khusus mengenai pendekatan khusus yang digunakan untuk implementasi
Map, performanya, dan karakteristik konsumsi memori. Jika struktur data digunakan di bagian penting aplikasi AndaMapdan jika Anda menulis sejumlah besar informasi ke dalam struktur data tersebut, maka pengetahuan yang kuat tentang penerapannya Mappasti akan sangat bermanfaat bagi Anda.
Saya memiliki pengalaman pengembangan Java, saya terbiasa dengan koleksi Java, di mana Anda dapat memilih antara implementasi antarmuka yang berbeda
Mapdan bahkan menyempurnakan implementasi yang dipilih jika kelas yang sesuai mendukungnya. Selain itu, di Java, Anda selalu dapat membaca kode sumber terbuka dari setiap kelas pustaka standar dan membiasakan diri dengan implementasinya (tentu saja, dapat berubah dalam versi baru, tetapi hanya dalam arah peningkatan efisiensi). Itulah mengapa saya tidak bisa menahan diri untuk mempelajari cara kerja objek Mapdi V8.
Sebelum kita mulai, saya ingin mencatat bahwa apa yang akan dibahas di bawah ini mengacu pada mesin V8 8.4, yang dibangun ke dalam versi dev baru Node.js (lebih tepatnya, kita berbicara tentang commit 238104c). Anda tidak perlu mengharapkan apa pun di luar spesifikasi.
Algoritme di balik implementasi Peta
Pertama-tama, saya akan mengatakan bahwa struktur data
Mapdidasarkan pada tabel hash. Di bawah ini saya berasumsi bahwa Anda tahu cara kerja tabel hash. Jika Anda tidak terbiasa dengan tabel hash, maka Anda harus membacanya terlebih dahulu (di sini , misalnya) dan baru kemudian melanjutkan membaca artikel ini.
Jika Anda memiliki pengalaman yang signifikan dengan objek
Map, maka Anda mungkin telah memperhatikan kontradiksi. Yakni, tabel hash tidak dijamin untuk mengembalikan item dalam beberapa urutan konstan saat mengulanginya. Dan spesifikasi ES6 menyatakan bahwa untuk mengimplementasikan suatu objek, Mapperlu, saat menjelajahinya, untuk memancarkan elemen sesuai urutan penambahannya. Hasilnya, algoritme "klasik" untukMaptidak muat. Tapi ada perasaan bahwa dengan beberapa perubahan, masih bisa digunakan.
V8 menggunakan apa yang disebut " tabel hash deterministik " yang diusulkan oleh Tyler Close. Pseudocode berikut, berdasarkan TypeScript, mendemonstrasikan struktur data dasar yang digunakan untuk mengimplementasikan tabel hash tersebut:
interface Entry {
key: any;
value: any;
chain: number;
}
interface CloseTable {
hashTable: number[];
dataTable: Entry[];
nextSlot: number;
size: number;
}
Di sini antarmuka
CloseTablemewakili tabel hash. Ini berisi larik hashTableyang ukurannya setara dengan jumlah wadah hash. Elemen array dengan indeks Nsesuai dengan Nwadah hash -th dan menyimpan indeks dari elemen head yang ada di dalam array dataTable. Dan larik ini berisi record tabel dalam urutan saat dimasukkan ke dalamnya. Entri disajikan oleh antarmuka Entry. Terakhir, setiap entri memiliki properti chainyang mengarah ke entri berikutnya dalam rangkaian entri kontainer hash (atau, lebih tepatnya, dalam daftar tertaut tunggal).
Setiap kali record baru dimasukkan ke dalam tabel, itu disimpan dalam elemen array
dataTabledengan indexnextSlot... Proses ini juga memerlukan pembaruan data dalam wadah hash terkait, yang menyebabkan rekaman yang disisipkan menjadi elemen terakhir baru dari daftar tertaut tunggal.
Ketika sebuah record dihapus dari tabel, record tersebut dihapus dari
dataTable(misalnya, dengan menulis ke properti keydan valuenilainya undefined). Kemudian entri yang mendahuluinya dan entri yang mengikutinya ditautkan secara langsung satu sama lain. Seperti yang Anda lihat, ini berarti bahwa semua entri yang dihapus terus menempati ruang di file dataTable.
Sekarang untuk bagian terakhir dari teka-teki kita. Ketika tabel penuh dengan catatan (baik yang sekarang maupun yang dihapus), itu harus di-rehash (dibangun kembali) dengan peningkatan ukurannya. Ukuran meja bisa diubah ke bawah.
Dengan pendekatan ini, melintasi struktur data
Mapsama dengan melintasi larik dataTable. Ini memastikan bahwa urutan record yang dimasukkan ke dalam tabel dipertahankan dan standar terpenuhi. Dengan pemikiran ini, saya berharap sebagian besar (jika tidak semua) mesin JS menggunakan tabel hash deterministik sebagai salah satu mekanisme implementasi yang mendasarinya Map.
Penelitian praktis dari algoritma
Mari kita lihat beberapa contoh untuk membantu kita menjelajahi algoritme dalam praktik. Misalkan kita memiliki
CloseTable2 kontainer hash ( hastTable.length), kapasitas totalnya adalah 4 elemen ( dataTable.length). Tabel ini diisi dengan konten berikut:
// , -,
// , , function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)
Representasi internal dari tabel yang diperoleh dalam contoh ini mungkin terlihat seperti ini:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: 0,
value: 'a',
chain: 2 // <2, 'c'>
},
{
key: 1,
value: 'b',
chain: -1 // -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3, //
size: 3
}
Jika Anda menghapus record menggunakan metode ini
table.delete(0), tabel hash akan terlihat seperti berikut:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: undefined, //
value: undefined,
chain: 2
},
{
key: 1,
value: 'b',
chain: -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3,
size: 2 //
}
Jika kita menambahkan beberapa record lagi ke tabel, maka itu perlu di-hash. Kami akan membahas proses ini secara rinci di bawah.
Pendekatan yang sama dapat diterapkan saat mengimplementasikan struktur data
Set. Satu-satunya perbedaan adalah bahwa struktur data ini tidak memerlukan properti value.
Sekarang setelah kami menemukan apa yang ada di balik objek
Mapdi V8, kami siap untuk melanjutkan.
Detail implementasi
Implementasi struktur data
Mapdi V8 ditulis dalam C ++, setelah itu kode JS diberikan akses ke mekanisme yang sesuai. Sebagian besar kode yang terkait Mapada di kelas OrderedHashTabledan OrderedHashMap. Kami sudah tahu cara kerja kelas-kelas ini. Jika Anda ingin melihat sendiri kode mereka, Anda dapat menemukannya di sini , di sini , dan di sini .
Karena kami sangat tertarik dengan detail praktis implementasi
Mapdi V8, pertama-tama kami perlu memahami bagaimana kapasitas tabel diatur.
Kapasitas meja
Di V8, kapasitas tabel hash (struktur data
Map) selalu merupakan pangkat dua. Jika kita berbicara tentang tingkat pemanfaatan kontainer hash, maka itu selalu diwakili oleh angka 2. Artinya, kapasitas maksimum tabel 2 * number_of_bucketsadalah 2 kali jumlah kontainer hash. Saat membuat objek kosong, Mapada 2 wadah hash di tabel hash internalnya. Hasilnya, kapasitas benda semacam itu sama dengan 4 record.
Ada batasan pada kapasitas maksimum objek
Map. Pada sistem 64-bit, ini akan menjadi sekitar 16,7 juta rekaman. Batasan ini disebabkan oleh kekhasan merepresentasikan struktur data Mapdi heap. Kami akan membicarakannya nanti.
Dan akhirnya, faktor naik atau turunnya tabel juga selalu diwakili oleh perkalian beberapa angka dengan 2. Ini berarti bahwa setelah 4 record ditambahkan ke tabel yang dijelaskan, operasi penyisipan berikutnya akan menyebabkan kebutuhan untuk rewash tabel, di mana ukuran tabel akan bertambah dua waktu. Dengan penurunan ukuran tabel, masing-masing bisa menjadi 2 kali lebih kecil.
Untuk memastikan bahwa apa yang saya lihat di kode sumber berfungsi persis seperti yang saya pahami, saya memodifikasi kode mesin V8 yang dibangun ke dalam Node.js, membuatnya menjadi
Mapproperti baru yang bucketsberisi informasi tentang jumlah wadah hash. Hasil modifikasi ini dapat Anda temukan di sini... Dalam perakitan khusus Node.js ini, skrip berikut dapat dijalankan:
const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
if (prevBuckets !== map.buckets) {
console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
map.set({}, {});
}
Skrip ini hanya memasukkan
Map100 record ke dalam struktur data . Inilah yang ditampilkan di konsol setelah meluncurkannya:
$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128
Seperti yang Anda lihat, saat tabel terisi, maka, dengan setiap perubahan ukurannya, tabel itu berlipat ganda. Sekarang mari kita coba mengurangi tabel dengan menghapus elemen darinya:
const map = new Map();
for (let i = 0; i < 100; i++) {
map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
map.delete(i);
if (prevBuckets !== map.buckets) {
console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
}
Inilah yang akan dihasilkan skrip ini:
$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4
Di sini, sekali lagi, Anda dapat melihat bahwa ukuran tabel berkurang setiap kali
number_of_buckets / 2elemennya lebih sedikit .
Fungsi hash
Sejauh ini, kami belum menyentuh pertanyaan tentang bagaimana V8 menghitung kode hash untuk kunci yang disimpan dalam objek
Map. Dan ini adalah pertanyaan penting.
Untuk nilai yang dapat diklasifikasikan sebagai numerik, beberapa fungsi hash terkenal dengan probabilitas tabrakan rendah digunakan.
Untuk nilai string, kode hash dihitung berdasarkan nilai itu sendiri. Setelah itu, kode ini di-cache di header internal.
Dan terakhir, untuk objek, hash dihitung berdasarkan nomor acak, dan yang terjadi kemudian di-cache di header internal.
Kompleksitas waktu operasi dengan objek Map
Sebagian besar operasi yang dilakukan pada struktur data
Map, seperti setatau delete, memerlukan pencarian melalui struktur data ini. Seperti dalam kasus dengan tabel hash "klasik", kompleksitas waktu pencarian dalam kasus kami adalah O(1).
Bayangkan skenario terburuk, ketika meja penuh, artinya, itu terisi
Ndari Nkursi. Dalam kasus ini, semua rekaman dimiliki oleh wadah hash tunggal, dan rekaman yang diperlukan berada di ujung rantai rekaman. Dalam skenario seperti ini, Anda perlu mengambil langkah-langkah untuk menemukan entri ini N.
Di sisi lain, dalam skenario terbaik, ketika tabel penuh dan hanya ada 2 catatan di setiap wadah hash, menemukan catatan hanya membutuhkan 2 langkah.
Operasi tertentu dalam tabel hash sangat cepat, tetapi tidak demikian halnya dengan operasi hash. Kompleksitas waktu dari operasi hash adalah
O(N). Ini membutuhkan tabel hash baru untuk dialokasikan di heap. Selain itu, pengulangan dilakukan sesuai kebutuhan, sebagai bagian dari operasi untuk memasukkan atau menghapus elemen dari tabel. Oleh karena itu, misalnya, panggilan tersebut map.set()mungkin menjadi jauh "lebih mahal" dari yang diharapkan. Untungnya, operasi hash jarang dilakukan.
Konsumsi memori
Tentu saja, tabel hash yang mendasari
Mapharus disimpan di heap. Itu disimpan dalam apa yang disebut "penyimpanan tambahan". Dan di sini fakta menarik lainnya menanti kita. Seluruh tabel (dan, oleh karena itu, segala sesuatu yang ditempatkan Map) disimpan dalam satu larik dengan panjang tetap. Struktur larik ini ditunjukkan pada gambar berikut.
Larik yang digunakan untuk menyimpan struktur data Peta di memori Bagian
individual larik memiliki tujuan berikut:
- Header: Berisi informasi umum, seperti jumlah wadah hash atau jumlah item yang dihapus
Map. - Hash Container Details: Di sinilah informasi container disimpan yang sesuai dengan array
hashTabledari contoh kami. - Entri tabel hash: Di sinilah data yang sesuai dengan array disimpan
dataTable. Yaitu, berisi informasi tentang entri tabel hash. Setiap record menempati tiga sel dalam array. Yang satu menyimpan kunci, yang kedua menyimpan nilainya, dan yang ketiga menyimpan "penunjuk" ke rekaman berikutnya dalam rantai.
Jika kita berbicara tentang ukuran array, maka secara kasar dapat diperkirakan sebagai
N * 3,5. Berikut Nkapasitas meja. Untuk memahami apa artinya ini dalam hal konsumsi memori, mari kita bayangkan bahwa kita memiliki sistem 64-bit dan fitur kompresi penunjuk V8 dinonaktifkan . Dalam hal ini, 8 byte dibutuhkan untuk menyimpan setiap elemen dari array. Akibatnya Map, memori heap sebesar 29 MB diperlukan untuk menyimpan struktur data yang berisi sekitar 1 juta catatan.
Hasil
Pada artikel ini, kami telah membahas banyak hal yang berkaitan dengan struktur data
Mapdi JavaScript. Mari kita rangkum:
- V8
Mapmenggunakan tabel hash deterministik untuk implementasi . Sangat mungkin bahwa struktur data ini juga diterapkan di mesin JS lainnya. - Mekanisme yang mendukung pekerjaan
Mapdiimplementasikan dalam C ++, setelah itu mereka disajikan sebagai API yang dapat diakses dari JavaScript. - Jika kita berbicara tentang kompleksitas waktu operasi yang dilakukan dengan objek
Map, maka, seperti saat bekerja dengan tabel hash "klasik", mereka memiliki kompleksitasO(1). Dalam kasus ini, kompleksitas waktu dari operasi hashing adalahO(N). - 64-
Map1 29 , . - , ,
Set.
Map JavaScript-?
