MegaHash - Hash Table cepat untuk Node.JS yang dikembangkan dengan C++

 (github.com)
7 poin oleh xguru 2020-07-24 | 2 komentar | Bagikan ke WhatsApp

  • Pengganti ES6 Maps yang dibatasi hingga 16 juta entri: dapat menyimpan lebih dari 1 miliar key

  • Dikembangkan dengan C++ dan menyertakan wrapper untuk Node.js

→ Dapat melakukan baca/tulis 500 ribu key per detik

→ Overhead memori rendah

→ Tidak disimpan di V8 Heap

→ Mendukung buffer, string, angka, boolean, dan objek

  • Kompatibel secara dasar dengan API ES6 Map: get, set, has, ddelete, clear, length

  • Secara internal menggunakan teknik Separate Chaining: metode indeks + linked list

Bacaan terkait

2 komentar

 
kbumsik 2020-07-24

Wah, apa memang ada alasan untuk memakai Map sebesar itu ya deuh
 
xguru 2020-07-24

Dalam praktiknya, jika Anda memasukkan lebih dari 2^24 kunci ke Map di Node.JS, akan terjadi heap error.

Ini bukan bug melainkan batasan yang ditetapkan oleh implementasinya, dan ada jawaban dari pengembang V8 tentang hal ini di StackOverflow.

https://stackoverflow.com/a/54466812/166418

  • FixedArray yang menyimpan Map memiliki ukuran maksimum 1GB

  • Pada sistem 64-bit, 1GB / 8B = 2^30 / 2^3 = 2^27 ~= 134M, jadi FixedArray dapat menyimpan maksimum 134 juta elemen

  • Map memerlukan 3 elemen per entri (Key, value, next bucket link), dan jumlah muatan maksimum dibatasi hingga 50% untuk menghindari tabrakan bucket.

→ Karena kapasitas harus berupa pangkat dua, jika hasil perhitungan 2^27 / (3 * 2) dibulatkan turun ke pangkat dua berikutnya, nilai maksimumnya adalah 2^24