Como um mapa de hash JavaScript é implementado?

89

Atualmente trabalho com OpenLayers e tenho um grande conjunto de dados para desenhar em uma camada vetorial (mais de 100.000 vetores).

Agora estou tentando colocar todos esses vetores em um mapa hash JavaScript para analisar o desempenho. Eu quero saber como o mapa de hash em JavaScript é implementado, é uma função hash real ou apenas uma função agrupada que usa uma estrutura de dados simples e um algoritmo de pesquisa?

javascript hash hashmap Patrick Hillert
fonte
2
Não há apenas uma implementação JS, então não há como responder a isso. ECMAScript não especifica qual estrutura de dados usar para objetos, nem especifica restrições no tempo de acesso. Hashes são típicos, mas árvores balanceadas podem ser usadas.
outis
1
ES6 tem mapas puros. O link descreve as diferenças entre objetos simples e Mapa, detalhes-chave etc: MDN JavaScript Mapa
Den Roman

Respostas:

196

cada objeto javascript é um hashmap simples que aceita uma string ou um símbolo como sua chave, então você pode escrever seu código como:

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

O objeto javascript é um hashmap real em sua implementação, então a complexidade na pesquisa é O (1), mas não há hashcode()função dedicada para strings javascript, ele é implementado internamente pelo mecanismo javascript (V8, SpiderMonkey, JScript.dll, etc. .)

Atualização de 2020:

o javascript hoje também oferece suporte a outros tipos de dados: Mape WeakMap. Eles se comportam mais como mapas hash do que objetos tradicionais.

otakustay
fonte
Perfeito. Eu estava usando $ ('div # someDiv'). Data (key, value) antes e este é muito mais simples e provavelmente tem melhor suporte para navegadores mais antigos também. Obrigado
Swaroop
existe uma maneira de encontrar o comprimento do mapa?
Rolling Stone
2
@Sridhar use Object.keys (map) .length
otakustay
1
Observe que você pode usar um número como uma chave, map[2] = 'foo'mas ele é convertido em uma string internamente> map = { '2': 'foo' }
Harry Moreno
@otakustay foi um recurso super legal que eu conheci hoje :) Realmente preciso aprender Javascript de perto.
Pankaj Prakash de
31

Objetos JavaScript não podem ser implementados puramente em mapas hash.

Experimente isso no console do seu navegador:

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

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

... e você os receberá de volta na ordem de inserção, que é o comportamento padrão de fato .

Os mapas hash inerentemente não mantêm a ordenação, portanto, as implementações de JavaScript podem usar mapas hash de alguma forma, mas se o fizerem, será necessário pelo menos um índice separado e alguns registros extras para inserções.

Aqui está um vídeo de Lars Bak explicando por que a v8 não usa mapas hash para implementar objetos .

Craig Barnes
fonte
3
"otakustay é tecnicamente errado, o pior tipo de erro." Isso é um pouco duro. Pode não ser 1: 1, mas para o propósito de usar um hash como um dicionário, funciona da mesma maneira.
provavelmente até
1
Só quero esclarecer que isso pode ser verdade para algumas implementações de JavaScript (como a maioria dos navegadores), mas nem sempre é necessariamente verdade. A ordem de iteração sobre as chaves não é definida pelos padrões ECMAScript e pode ser qualquer ordem e ainda ser uma implementação JS válida.
TheZ
19

Esta é uma maneira fácil e conveniente de usar algo semelhante ao mapa 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
    }

E para obter o valor:

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

......  etc  .....
Miloš
fonte
13

Você deveria tentar esta aula 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"
Expandir snippet

Aviso: a chave e o valor podem ser de qualquer tipo.

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

Nguyen Tan Dat
fonte
4

Embora objetos JavaScript simples e antigos possam ser usados ​​como mapas, eles geralmente são implementados de forma a preservar a ordem de inserção para compatibilidade com a maioria dos navegadores (consulte a resposta de Craig Barnes) e, portanto, não são mapas hash simples.

ES6 apresenta Mapas adequados (consulte Mapa MDN JavaScript ), dos quais o padrão diz :

O objeto de mapa deve ser implementado usando tabelas hash ou outros mecanismos que, em média, fornecem tempos de acesso que são sublineares no número de elementos na coleção.

mb21
fonte
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
fonte
0

Eu estava tendo o problema em que tinha o JSON com algumas chaves comuns. Eu queria agrupar todos os valores com a mesma chave. Depois de navegar, encontrei o pacote hashmap . O que é realmente útil.

Para agrupar o elemento com a mesma chave, usei multi(key:*, value:*, key2:*, value2:*, ...).

Este pacote é um pouco semelhante à coleção Java Hashmap, mas não tão poderoso quanto Java Hashmap.

dd619
fonte