Bagaimana peta hash JavaScript diimplementasikan?

89

Saat ini saya bekerja dengan OpenLayers dan memiliki sekumpulan besar data untuk ditarik ke dalam lapisan vektor (lebih besar dari 100000 vektor).

Sekarang saya mencoba memasukkan semua vektor ini ke dalam peta hash JavaScript untuk menganalisis kinerja. Saya ingin tahu bagaimana peta hash di JavaScript diimplementasikan, apakah itu fungsi hash nyata atau hanya fungsi yang dibungkus yang menggunakan struktur data sederhana dan algoritma pencarian?

javascript hash hashmap Patrick Hillert
sumber
2
Tidak hanya ada satu implementasi JS, jadi tidak ada cara untuk menjawab ini. ECMAScript tidak menentukan struktur data apa yang akan digunakan untuk objek, juga tidak menentukan batasan waktu akses. Biasanya ada bulu mata, tetapi pohon yang seimbang bisa digunakan.
keluar
1
ES6 memiliki Maps murni. Tautan menjelaskan perbedaan antara objek biasa dan Peta, detail utama, dll.: Peta JavaScript MDN
Den Roman

Jawaban:

196

setiap objek javascript adalah peta hash sederhana yang menerima string atau Simbol sebagai kuncinya, sehingga Anda dapat menulis kode Anda sebagai:

var map = {};
// add a item
map[key1] = value1;
// or remove it
delete map[key1];
// or determine whether a key exists
key1 in map;

Objek javascript adalah hashmap nyata dalam implementasinya, jadi kompleksitas pencarian adalah O (1), tetapi tidak ada hashcode()fungsi khusus untuk string javascript, ini diimplementasikan secara internal oleh mesin javascript (V8, SpiderMonkey, JScript.dll, dll. .)

Pembaruan 2020:

javascript hari ini mendukung tipe data lain juga: Mapdan WeakMap. Mereka berperilaku lebih dekat sebagai peta hash daripada objek tradisional.

otakustay
sumber
Sempurna. Saya pernah menggunakan $ ('div # someDiv']. Data (key, value) sebelumnya dan yang ini jauh lebih sederhana dan mungkin memiliki dukungan yang lebih baik untuk browser lama juga. Terima kasih
Swaroop
apakah ada cara untuk mengetahui panjang peta?
batu bergulir
2
@Sridhar menggunakan Object.keys (map)
.length
1
Perhatikan Anda dapat menggunakan angka sebagai kunci map[2] = 'foo'tetapi itu akan dilemparkan ke string secara internal> map = { '2': 'foo' }
Harry Moreno
@otakustay itu fitur super keren yang saya kenal hari ini :) Sungguh saya perlu belajar Javascript dengan cermat.
Pankaj Prakash
31

Objek JavaScript tidak dapat diterapkan hanya di atas peta hash.

Coba ini di konsol browser Anda:

var foo = {
    a: true,
    b: true,
    z: true,
    c: true
}

for (var i in foo) {
    console.log(i);
}

... dan Anda akan menerimanya kembali dalam urutan penyisipan, yang merupakan perilaku standar de facto .

Peta hash secara inheren tidak mempertahankan pengurutan, jadi implementasi JavaScript mungkin menggunakan peta hash, tetapi jika demikian, itu akan membutuhkan setidaknya indeks terpisah dan beberapa pembukuan tambahan untuk penyisipan.

Berikut adalah video dari Lars Bak yang menjelaskan mengapa v8 tidak menggunakan peta hash untuk mengimplementasikan objek .

Craig Barnes
sumber
3
"otakustay secara teknis salah, jenis kesalahan terburuk." Itu sedikit kasar. Ini mungkin bukan 1: 1, tetapi untuk maksud dan tujuan menggunakan hash seperti kamus, ini bekerja dengan cara yang sama.
mungkin sampai
1
Hanya ingin menjelaskan bahwa ini mungkin benar untuk beberapa implementasi JavaScript (seperti kebanyakan browser) tetapi tidak selalu benar. Urutan iterasi atas kunci tidak ditentukan oleh standar ECMAScript dan dapat berupa urutan apa pun dan masih merupakan implementasi JS yang valid.
TheZ
19

Berikut ini cara yang mudah dan nyaman untuk menggunakan sesuatu yang mirip dengan peta Java :

var map= {
    'map_name_1': map_value_1,
    'map_name_2': map_value_2,
    'map_name_3': map_value_3,
    'map_name_4': map_value_4
    }

Dan untuk mendapatkan nilainya:

alert( map['map_name_1'] );    // fives the value of map_value_1

......  etc  .....
Miloš
sumber
13

Haruskah Anda mencoba kelas ini Map:

var myMap = new Map();

// setting the values
myMap.set("1", 'value1');
myMap.set("2", 'value2');
myMap.set("3", 'value3');

myMap.size; // 3

// getting the values
myMap.get("1");    // "value associated with "value1"
myMap.get("2");       // "value associated with "value1"
myMap.get("3");      // "value associated with "value3"
Luaskan cuplikan

Perhatikan: key dan value bisa jenis apa saja.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Nguyen Tan Dat
sumber
4

Sementara objek JavaScript lama biasa dapat digunakan sebagai peta, mereka biasanya diimplementasikan dengan cara untuk menjaga urutan penyisipan agar kompatibel dengan sebagian besar browser (lihat jawaban Craig Barnes) dan dengan demikian bukan peta hash sederhana.

ES6 memperkenalkan Peta yang tepat (lihat Peta JavaScript MDN ) yang standarnya mengatakan :

Objek peta harus diimplementasikan menggunakan tabel hash atau mekanisme lain yang, rata-rata, menyediakan waktu akses yang sublinear pada jumlah elemen dalam koleksi.

mb21
sumber
1 
<html>
<head>
<script type="text/javascript">
function test(){
var map= {'m1': 12,'m2': 13,'m3': 14,'m4': 15}
     alert(map['m3']);
}
</script>
</head>
<body>
<input type="button" value="click" onclick="test()"/>
</body>
</html>
rajendra kumar
sumber
0

Saya mengalami masalah di mana saya memiliki json dengan beberapa kunci umum. Saya ingin mengelompokkan semua nilai yang memiliki kunci yang sama. Setelah beberapa surfing saya menemukan paket hashmap . Yang sangat membantu.

Untuk mengelompokkan elemen dengan kunci yang sama, saya menggunakan multi(key:*, value:*, key2:*, value2:*, ...).

Paket ini agak mirip dengan koleksi Java Hashmap, tetapi tidak sekuat Java Hashmap.

dd619
sumber