W jaki sposób jest implementowana mapa skrótów JavaScript?

Question 1

Obecnie pracuję z OpenLayers i mam ogromny zestaw danych do narysowania na warstwie wektorowej (ponad 100 000 wektorów).

Teraz próbuję umieścić wszystkie te wektory w mapie mieszania JavaScript, aby przeanalizować wydajność. Chcę wiedzieć, w jaki sposób jest zaimplementowana mapa skrótów w JavaScript, czy jest to prawdziwa funkcja skrótu, czy tylko funkcja opakowana, która wykorzystuje prostą strukturę danych i algorytm wyszukiwania?

Question 2

każdy obiekt javascript jest prostym hashemapem, który akceptuje ciąg lub symbol jako klucz, więc możesz napisać swój kod jako:

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

obiekt javascript jest prawdziwym hashemapem na swojej implementacji, więc złożoność wyszukiwania to O (1), ale nie ma dedykowanej hashcode()funkcji dla ciągów javascript, jest zaimplementowana wewnętrznie przez silnik javascript (V8, SpiderMonkey, JScript.dll itp. .)

Aktualizacja 2020:

javascript obsługuje obecnie również inne typy danych: Mapi WeakMap. Zachowują się bardziej jak mapy skrótów niż tradycyjne obiekty.

Question 3

Obiekty JavaScript nie mogą być implementowane wyłącznie na mapach skrótów.

Spróbuj tego w konsoli przeglądarki:

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

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

... a otrzymasz je z powrotem w kolejności reklamowej, co jest de facto standardowym zachowaniem.

Mapy skrótów z natury nie zachowują kolejności, więc implementacje JavaScript mogą w jakiś sposób używać map mieszających, ale jeśli to robią, będzie to wymagało co najmniej oddzielnego indeksu i dodatkowej księgowości do wstawiania.

Oto wideo Larsa Baka wyjaśniającego, dlaczego wersja 8 nie używa map skrótów do implementowania obiektów .

Question 4

Oto łatwy i wygodny sposób korzystania z czegoś podobnego do mapy 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
    }

Aby uzyskać wartość:

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

......  etc  .....

Question 5

Powinieneś spróbować tej klasy 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"

Rozwiń fragment

Uwaga: klucz i wartość mogą być dowolnego typu.

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

Question 6

Chociaż zwykłe stare obiekty JavaScript mogą być używane jako mapy, są one zwykle implementowane w taki sposób, aby zachować kolejność wstawiania w celu zapewnienia zgodności z większością przeglądarek (patrz odpowiedź Craiga Barnesa), a zatem nie są prostymi mapami skrótów.

ES6 wprowadza odpowiednie mapy (patrz mapa JavaScript w MDN ), o których norma mówi :

Obiekt Map musi być zaimplementowany przy użyciu tabel skrótów lub innych mechanizmów, które średnio zapewniają czasy dostępu podliniowe względem liczby elementów w kolekcji.

Question 7

<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>

Question 8

Miałem problem, w którym miałem plik JSON z kilkoma typowymi kluczami. Chciałem zgrupować wszystkie wartości mające ten sam klucz. Po pewnym surfowaniu znalazłem pakiet hashmap . Co jest naprawdę pomocne.

Aby zgrupować element z tym samym kluczem, użyłem multi(key:*, value:*, key2:*, value2:*, ...).

Ten pakiet jest nieco podobny do kolekcji Java Hashmap, ale nie jest tak potężny jak Java Hashmap.

Answer 1

88

Obecnie pracuję z OpenLayers i mam ogromny zestaw danych do narysowania na warstwie wektorowej (ponad 100 000 wektorów).

Teraz próbuję umieścić wszystkie te wektory w mapie mieszania JavaScript, aby przeanalizować wydajność. Chcę wiedzieć, w jaki sposób jest zaimplementowana mapa skrótów w JavaScript, czy jest to prawdziwa funkcja skrótu, czy tylko funkcja opakowana, która wykorzystuje prostą strukturę danych i algorytm wyszukiwania?

javascript hash hashmap Patrick Hillert
źródło

2

Nie ma tylko jednej implementacji JS, więc nie ma sposobu, aby na to odpowiedzieć. ECMAScript nie określa, jakiej struktury danych użyć dla obiektów, ani nie określa ograniczeń czasu dostępu. Hashe są typowe, ale można użyć zrównoważonych drzew.

outis

1

ES6 ma czyste mapy. Link opisuje różnice między zwykłym obiektem a mapą, kluczowe szczegóły itp .: Mapa JavaScript w MDN

Den Roman

Answer 2

2

Nie ma tylko jednej implementacji JS, więc nie ma sposobu, aby na to odpowiedzieć. ECMAScript nie określa, jakiej struktury danych użyć dla obiektów, ani nie określa ograniczeń czasu dostępu. Hashe są typowe, ale można użyć zrównoważonych drzew.

outis

Answer 3

1

ES6 ma czyste mapy. Link opisuje różnice między zwykłym obiektem a mapą, kluczowe szczegóły itp .: Mapa JavaScript w MDN

Den Roman

Answer 4

193

każdy obiekt javascript jest prostym hashemapem, który akceptuje ciąg lub symbol jako klucz, więc możesz napisać swój kod jako:

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

obiekt javascript jest prawdziwym hashemapem na swojej implementacji, więc złożoność wyszukiwania to O (1), ale nie ma dedykowanej hashcode()funkcji dla ciągów javascript, jest zaimplementowana wewnętrznie przez silnik javascript (V8, SpiderMonkey, JScript.dll itp. .)

Aktualizacja 2020:

javascript obsługuje obecnie również inne typy danych: Mapi WeakMap. Zachowują się bardziej jak mapy skrótów niż tradycyjne obiekty.

otakustay
źródło

Idealny. Używałem wcześniej $ ('div # someDiv'). Data (klucz, wartość), a ta jest znacznie prostsza i prawdopodobnie ma lepszą obsługę również dla starszych przeglądarek. Dzięki

Swaroop

czy istnieje sposób, aby znaleźć długość mapy?

toczący się kamień

2

@Sridhar użyj Object.keys (map) .length

otakustay

1

Zauważ, że możesz użyć liczby jako klucza, map[2] = 'foo'ale jest ona wewnętrznie rzutowana na strunę> map = { '2': 'foo' }

Harry Moreno

@otakustay to była super fajna funkcja, którą poznałem dzisiaj :) Naprawdę muszę dokładnie nauczyć się Javascript.

Pankaj Prakash

Answer 5

Idealny. Używałem wcześniej $ ('div # someDiv'). Data (klucz, wartość), a ta jest znacznie prostsza i prawdopodobnie ma lepszą obsługę również dla starszych przeglądarek. Dzięki

Swaroop

Answer 6

czy istnieje sposób, aby znaleźć długość mapy?

toczący się kamień

Answer 7

2

@Sridhar użyj Object.keys (map) .length

otakustay

Answer 8

1

Zauważ, że możesz użyć liczby jako klucza, map[2] = 'foo'ale jest ona wewnętrznie rzutowana na strunę> map = { '2': 'foo' }

Harry Moreno

Answer 9

@otakustay to była super fajna funkcja, którą poznałem dzisiaj :) Naprawdę muszę dokładnie nauczyć się Javascript.

Pankaj Prakash

Answer 10

31

Obiekty JavaScript nie mogą być implementowane wyłącznie na mapach skrótów.

Spróbuj tego w konsoli przeglądarki:

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

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

... a otrzymasz je z powrotem w kolejności reklamowej, co jest de facto standardowym zachowaniem.

Mapy skrótów z natury nie zachowują kolejności, więc implementacje JavaScript mogą w jakiś sposób używać map mieszających, ale jeśli to robią, będzie to wymagało co najmniej oddzielnego indeksu i dodatkowej księgowości do wstawiania.

Oto wideo Larsa Baka wyjaśniającego, dlaczego wersja 8 nie używa map skrótów do implementowania obiektów .

Craig Barnes
źródło

3

„Otakustay jest technicznie zły, najgorszy rodzaj zła”. To trochę trudne. Może nie być 1: 1, ale dla celów i celów użycia skrótu, takiego jak słownik, działa w ten sam sposób.

prawdopodobnie do góry

1

Chcę tylko wyjaśnić, że może to być prawdą w przypadku niektórych implementacji JavaScript (takich jak większość przeglądarek), ale niekoniecznie zawsze jest prawdą. Kolejność iteracji po kluczach nie jest zdefiniowana przez standardy ECMAScript i może być dowolną kolejnością i nadal być poprawną implementacją JS.

TheZ

Answer 11

3

„Otakustay jest technicznie zły, najgorszy rodzaj zła”. To trochę trudne. Może nie być 1: 1, ale dla celów i celów użycia skrótu, takiego jak słownik, działa w ten sam sposób.

prawdopodobnie do góry

Answer 12

1

Chcę tylko wyjaśnić, że może to być prawdą w przypadku niektórych implementacji JavaScript (takich jak większość przeglądarek), ale niekoniecznie zawsze jest prawdą. Kolejność iteracji po kluczach nie jest zdefiniowana przez standardy ECMAScript i może być dowolną kolejnością i nadal być poprawną implementacją JS.

TheZ

Answer 13

Oto łatwy i wygodny sposób korzystania z czegoś podobnego do mapy 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
    }

Aby uzyskać wartość:

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

......  etc  .....

Answer 14

Powinieneś spróbować tej klasy 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"

Rozwiń fragment

Uwaga: klucz i wartość mogą być dowolnego typu.

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

Answer 15

Chociaż zwykłe stare obiekty JavaScript mogą być używane jako mapy, są one zwykle implementowane w taki sposób, aby zachować kolejność wstawiania w celu zapewnienia zgodności z większością przeglądarek (patrz odpowiedź Craiga Barnesa), a zatem nie są prostymi mapami skrótów.

ES6 wprowadza odpowiednie mapy (patrz mapa JavaScript w MDN ), o których norma mówi :

Obiekt Map musi być zaimplementowany przy użyciu tabel skrótów lub innych mechanizmów, które średnio zapewniają czasy dostępu podliniowe względem liczby elementów w kolekcji.

Answer 16

<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>

Answer 17

Miałem problem, w którym miałem plik JSON z kilkoma typowymi kluczami. Chciałem zgrupować wszystkie wartości mające ten sam klucz. Po pewnym surfowaniu znalazłem pakiet hashmap . Co jest naprawdę pomocne.

Aby zgrupować element z tym samym kluczem, użyłem multi(key:*, value:*, key2:*, value2:*, ...).

Ten pakiet jest nieco podobny do kolekcji Java Hashmap, ale nie jest tak potężny jak Java Hashmap.

W jaki sposób jest implementowana mapa skrótów JavaScript?

Odpowiedzi: