Equivalente de Hashmap JavaScript

354

Como ficou claro na atualização 3 desta resposta , esta notação:

var hash = {};
hash[X]

na verdade não faz o hash do objeto X; na verdade, apenas converte Xem uma sequência de caracteres (via .toString()se for um objeto ou em algumas outras conversões internas para vários tipos primitivos) e, em seguida, procura essa sequência, sem hash, em " hash". A igualdade de objetos também não é verificada - se dois objetos diferentes tiverem a mesma conversão de cadeia, eles serão substituídos.

Diante disso - existem implementações eficientes de hashmaps em javascript? (Por exemplo, o segundo resultado do Google javascript hashmapproduz uma implementação que é O (n) para qualquer operação. Vários outros resultados ignoram o fato de que objetos diferentes com representações de sequência equivalentes se sobrescrevem.

Claudiu
fonte
11
@ Claudiu: Desculpe pela edição, mas o "Mapa" no título foi realmente enganador. Reverter se você não concordar, eu não pretendia patrocinar. :)
Tomalak
6
@ Claudiu: Você faz muitas perguntas sobre javascript. Boas perguntas. Eu gosto disso.
alguns
2
@ Claudiu: Além disso, você poderia criar um link para o resultado do Google ao qual se refere? Diferentes versões locais do Google retornam resultados diferentes, a implementação a que você se refere nem parece aparecer para mim.
Tomalak
@Tomalak: Eu ia escrever exatamente a mesma coisa!
alguns
3
@ Claudiu Não, não conecte ao google. Link para a página que você estava falando (que você encontrou no google). A vinculação ao google tem os mesmos problemas que os explicados no que procurar: personalização de resultados do Google com base no local ou no histórico de pesquisas, alteração dos resultados do google ao longo do tempo (atualmente, esse é o resultado principal dessa pesquisa) e qualquer outra coisa que possa torná-lo mostrar resultados diferentes.
Jasper

Respostas:

370

Por que não manipular seus objetos manualmente e usar as seqüências resultantes como chaves para um dicionário JavaScript comum? Afinal, você está na melhor posição para saber o que torna seus objetos únicos. Isto é o que eu faço.

Exemplo:

var key = function(obj){
  // some unique object-dependent key
  return obj.totallyUniqueEmployeeIdKey; // just an example
};

var dict = {};

dict[key(obj1)] = obj1;
dict[key(obj2)] = obj2;

Dessa forma, você pode controlar a indexação feita por JavaScript sem sobrecarregar a alocação de memória e manipular o estouro.

Obviamente, se você realmente deseja a "solução de nível industrial", pode criar uma classe parametrizada pela função-chave e com toda a API necessária do contêiner, mas ... usamos JavaScript e tentamos ser simples e leves, então Esta solução funcional é simples e rápida.

A função de chave pode ser tão simples quanto selecionar os atributos corretos do objeto, por exemplo, uma chave ou um conjunto de chaves que já são únicas, uma combinação de chaves que são únicas juntas ou tão complexas quanto o uso de alguns hashes criptográficos, como na codificação DojoX , ou DojoX UUID . Embora as últimas soluções possam produzir chaves exclusivas, pessoalmente tento evitá-las a todo custo, principalmente se souber o que torna meus objetos únicos.

Atualização em 2014: respondida em 2008, esta solução simples ainda requer mais explicações. Deixe-me esclarecer a ideia em um formulário de perguntas e respostas.

Sua solução não possui um hash real. Cadê???

JavaScript é uma linguagem de alto nível. Sua primitiva básica ( Object ) inclui uma tabela de hash para manter as propriedades. Essa tabela de hash geralmente é escrita em um idioma de baixo nível para eficiência. Usando um objeto simples com chaves de string, usamos uma tabela de hash implementada com eficiência, sem nenhum esforço de nossa parte.

Como você sabe que eles usam hash?

Existem três maneiras principais de manter uma coleção de objetos endereçáveis ​​por uma chave:

  • Não ordenado. Nesse caso, para recuperar um objeto por sua chave, precisamos passar por todas as chaves, parando quando o encontrarmos. Em média, serão necessárias n / 2 comparações.
  • Encomendado.
    • Exemplo # 1: uma matriz classificada - fazendo uma pesquisa binária, encontraremos nossa chave após comparações em ~ log2 (n), em média. Muito melhor.
    • Exemplo # 2: uma árvore. Novamente, serão ~ log (n) tentativas.
  • Tabela de hash. Em média, exige um tempo constante. Compare: O (n) vs. O (log n) vs. O (1). Estrondo.

Obviamente, os objetos JavaScript usam tabelas de hash de alguma forma para lidar com casos gerais.

Os fornecedores de navegadores realmente usam tabelas de hash ???

Realmente.

Eles lidam com colisões?

Sim. Veja acima. Se você encontrou uma colisão em cadeias desiguais, não hesite em registrar um bug com um fornecedor.

Então, qual é a sua ideia?

Se você deseja fazer o hash de um objeto, encontre o que o torna único e use-o como chave. Não tente calcular o hash real ou emular tabelas de hash - ele já é tratado com eficiência pelo objeto JavaScript subjacente.

Use essa chave com JavaScript Objectpara alavancar sua tabela de hash integrada enquanto evita possíveis conflitos com propriedades padrão.

Exemplos para você começar:

  • Se seus objetos incluem um nome de usuário exclusivo - use-o como chave.
  • Se incluir um número de cliente exclusivo - use-o como chave.
    • Se ele incluir números exclusivos emitidos pelo governo, como um SSN ou um número de passaporte, e seu sistema não permitir duplicatas - use-o como chave.
  • Se uma combinação de campos for única - use-a como chave.
    • Abreviação do estado + número da carteira de motorista é uma excelente chave.
    • A abreviação do país + número do passaporte também é uma excelente chave.
  • Algumas funções nos campos ou em um objeto inteiro podem retornar um valor exclusivo - use-o como chave.

Usei sua sugestão e coloquei em cache todos os objetos usando um nome de usuário. Mas um cara sábio se chama "toString", que é uma propriedade interna! O que eu deveria fazer agora?

Obviamente, se é possível remotamente que a chave resultante consista exclusivamente em caracteres latinos, você deve fazer algo a respeito. Por exemplo, adicione qualquer caractere Unicode não latino que você goste no início ou no final para desestabilizar as propriedades padrão: "#toString", "#MarySmith". Se uma chave composta for usada, separe os componentes-chave usando algum tipo de delimitador não latino: "nome, cidade, estado".

Em geral, este é o local em que precisamos ser criativos e selecionar as chaves mais fáceis com limitações dadas (exclusividade, possíveis conflitos com propriedades padrão).

Nota: as chaves exclusivas não se chocam por definição, enquanto os possíveis confrontos de hash serão tratados pelo subjacente Object.

Por que você não gosta de soluções industriais?

IMHO, o melhor código não é código: não possui erros, não requer manutenção, é fácil de entender e é executado instantaneamente. Todas as "tabelas de hash em JavaScript" que vi eram> 100 linhas de código e envolviam vários objetos. Compará-lo com: dict[key] = value.

Outro ponto: é possível vencer uma performance de um objeto primordial escrito em uma linguagem de baixo nível, usando JavaScript e os mesmos objetos primordiais para implementar o que já está implementado?

Eu ainda quero misturar meus objetos sem nenhuma chave!

Estamos com sorte: o ECMAScript 6 (agendado para lançamento em meados de 2015, mais ou menos 1 a 2 anos depois disso para se espalhar) define mapa e cenário .

A julgar pela definição, eles podem usar o endereço do objeto como uma chave, o que torna os objetos instantaneamente distintos sem chaves artificiais. OTOH, dois objetos diferentes, mas idênticos, serão mapeados como distintos.

Análise comparativa do MDN :

Os objetos são semelhantes aos Mapas, pois ambos permitem definir chaves para valores, recuperar esses valores, excluir chaves e detectar se algo está armazenado em uma chave. Por causa disso (e porque não havia alternativas internas), os Objetos têm sido usados ​​como Mapas historicamente; no entanto, existem diferenças importantes que tornam preferível o uso de um mapa em certos casos:

  • As chaves de um Objeto são Strings e Símbolos, enquanto que podem ter qualquer valor para um Mapa, incluindo funções, objetos e qualquer primitivo.
  • As chaves no mapa são ordenadas, enquanto as chaves adicionadas ao objeto não são. Assim, ao iterar sobre ele, um objeto Map retorna chaves em ordem de inserção.
  • Você pode obter facilmente o tamanho de um mapa com a propriedade size, enquanto o número de propriedades em um objeto deve ser determinado manualmente.
  • Um mapa é iterável e, portanto, pode ser iterado diretamente, enquanto a iteração sobre um objeto requer a obtenção de suas chaves de alguma maneira e a iteração sobre elas.
  • Um objeto tem um protótipo; portanto, existem chaves padrão no mapa que podem colidir com suas chaves se você não tomar cuidado. No ES5, isso pode ser ignorado usando map = Object.create (null), mas isso raramente é feito.
  • Um mapa pode ter um desempenho melhor em cenários que envolvem adição e remoção freqüentes de pares de chaves.
Eugene Lazutkin
fonte
13
Isso não parece um mapa adequado, porque você não lida com colisões. Se isso for verdade: hash (obj1) == hash (obj2), você perderá seus dados.
beefeather 2/12/12
32
Céu ajudá-lo quando ambos "PAUL Ainley" e "PAULA Inley" registrar em seu sistema ...
Matt R
34
@MattR Na verdade, seu exemplo funcionará corretamente sem a ajuda do céu, mesmo com uma função de hash simulada. Espero que outros leitores percebam que uma função hash não-realista simplificada demais foi usada como espaço reservado para demonstrar uma técnica diferente. Ambos os comentários de código e a resposta em si enfatizam que não é real. A seleção das chaves apropriadas é discutida no último parágrafo da resposta.
Eugene Lazutkin
6
@EugeneLazutkin - você ainda está enganado, eu tenho medo. Seu exemplo ainda é propenso a colisões de hash. Não pense que apenas colocar o sobrenome em primeiro lugar irá ajudá-lo!
Matt R
3
@EugeneLazutkin A maioria das pessoas não lê, você responde isso ANTES que o ES6 apareça ... Deixe-me parabenizar pelo seu profundo conhecimento em JS.
Gabriel Andrés Brancolini
171

Descrição do Problema

O JavaScript não possui um tipo de mapa geral embutido (às vezes chamado de array ou dicionário associativo ) que permite acessar valores arbitrários por chaves arbitrárias. A estrutura de dados fundamental do JavaScript é o objeto , um tipo especial de mapa que aceita apenas cadeias de caracteres como chaves e possui semântica especial como herança prototípica, getters e setters e mais algum vodu.

Ao usar objetos como mapas, lembre-se de que a chave será convertida em um valor de string via toString(), o que resulta no mapeamento 5e '5'no mesmo valor e em todos os objetos que não substituem o toString()método pelo valor indexado por '[object Object]'. Você também pode acessar involuntariamente suas propriedades herdadas se não marcar hasOwnProperty().

O tipo de matriz interno do JavaScript não ajuda em nada: as matrizes JavaScript não são matrizes associativas, mas apenas objetos com mais algumas propriedades especiais. Se você quiser saber por que eles não podem ser usados ​​como mapas, veja aqui .

Solução de Eugene

Eugene Lazutkin já descreveu a idéia básica de usar uma função hash customizada para gerar strings exclusivas que podem ser usadas para procurar os valores associados como propriedades de um objeto de dicionário. Essa provavelmente será a solução mais rápida, porque os objetos são implementados internamente como tabelas de hash .

  • Nota: As tabelas de hash (às vezes chamadas de mapas de hash ) são uma implementação específica do conceito de mapa usando uma matriz de apoio e pesquisa através de valores numéricos de hash. O ambiente de tempo de execução pode usar outras estruturas (como árvores de pesquisa ou ignorar listas ) para implementar objetos JavaScript, mas como os objetos são a estrutura de dados fundamental, eles devem ser suficientemente otimizados.

Para obter um valor de hash exclusivo para objetos arbitrários, uma possibilidade é usar um contador global e armazenar em cache o valor de hash no próprio objeto (por exemplo, em uma propriedade chamada __hash).

Uma função hash que faz isso e funciona para valores e objetos primitivos é:

function hash(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
}

hash.current = 0;

Esta função pode ser usada como descrito por Eugene. Por conveniência, vamos envolvê-lo ainda mais em uma Mapclasse.

Minha Mapimplementação

A implementação a seguir armazenará adicionalmente os pares de valores-chave em uma lista duplamente vinculada para permitir uma iteração rápida sobre chaves e valores. Para fornecer sua própria função de hash, você pode substituir o hash()método da instância após a criação.

// linking the key-value-pairs is optional
// if no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
    this.current = undefined;
    this.size = 0;

    if(linkItems === false)
        this.disableLinking();
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;

    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }

    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;
    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
    this.removeAll = Map.illegal;

    return this;
};

// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;

    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];

    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }

    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    while(this.size)
        this.remove(this.key());

    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    return this.current.key;
};

Map.prototype.value = function() {
    return this.current.value;
};

Exemplo

O script a seguir

var map = new Map;

map.put('spam', 'eggs').
    put('foo', 'bar').
    put('foo', 'baz').
    put({}, 'an object').
    put({}, 'another object').
    put(5, 'five').
    put(5, 'five again').
    put('5', 'another five');

for(var i = 0; i++ < map.size; map.next())
    document.writeln(map.hash(map.key()) + ' : ' + map.value());

gera esta saída:

string spam : eggs
string foo : baz
object 1 : an object
object 2 : another object
number 5 : five again
string 5 : another five

Considerações adicionais

O PEZ sugeriu sobrescrever o toString()método, presumivelmente com a nossa função hash. Esta não é viável porque ele não funciona para valores primitivos (mudando toString()para primitivas é uma muito má ideia). Se quisermos toString()retornar valores significativos para objetos arbitrários, teríamos que modificar Object.prototype, o que algumas pessoas (inclusive eu) não consideram verboten .


Edit: A versão atual da minha Mapimplementação, bem como outras vantagens do JavaScript, podem ser obtidas aqui .

Christoph
fonte
O ES5 descontinua o uso de chamada ( goo.gl/EeStE ). Em vez disso, sugiro Map._counter = 0, e no construtor Map, faça this._hash = 'object ' + Map._counter++. Então, o hash () se tornareturn (value && value._hash) || (typeof(value) + ' ' + String(value));
broofa
Link para o código é quebrado: mercurial.intuxication.org/hg/js-hacks/raw-file/tip/map.js
ahcox
oi @Christoph, você poderia atualizar seu link para onde eu posso encontrar a implementação do seu mapa?
NumenorForLife 30/07/2013
2
@ jsc123: Examinarei isso - por enquanto, você pode obter um despejo do repositório em pikacode.com/mercurial.intuxication.org/js-hacks.tar.gz #
Christoph
58

Eu sei que essa pergunta é bastante antiga, mas existem algumas ótimas soluções hoje em dia com bibliotecas externas.

O JavaScript também possui sua linguagem fornecida Map.

Jamel Toms
fonte
2
Esta é a maneira de avançar para o século XXI. Pena que eu encontrei sua postagem depois de terminar meu código com um mapa feio feito em casa. Os REEE precisam de mais votos para a sua resposta
Phung D. Um dia
11
O Collections.js tem algumas implementações, mas não consigo encontrar nenhum no underscore.js ou no lodash ... a que você se referia no sublinhado que seria útil?
Codebling 23/09/16
@CodeBling não faz ideia. acho que confundi com a função map. vou removê-lo da resposta.
Jamel Toms
3
Isso é justo. Qualquer pessoa que considerar o Collections.js deve estar ciente de que ele modifica os protótipos globais de Matriz, Função, Objeto e Regexp de maneira problemática ( consulte os problemas que encontrei aqui ). Embora eu estivesse inicialmente muito satisfeito com o collections.js (e, portanto, esta resposta), os riscos associados ao seu uso eram muito altos, então eu o deixei cair. Somente o ramo v2 do kriskowal do collections.js (especificamente, v2.0.2 +) elimina as modificações do protótipo global e é seguro de usar.
Codebling
28

Aqui está 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
2
Isso funciona apenas para chaves de seqüência de caracteres. Acredito que o OP estava interessado em usar chaves de qualquer tipo.
fractor
26

De acordo com o padrão ECMAScript 2015 (ES6), o javascript possui uma implementação de Mapa. Mais sobre o que pode ser encontrado aqui

Uso básico:

var myMap = new Map();
var keyString = "a string",
    keyObj = {},
    keyFunc = function () {};

// setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");

myMap.size; // 3

// getting the values
myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"
Riyafa Abdul Hameed
fonte
21

Você pode usar o ES6 WeakMapou Map:

  • WeakMaps são mapas de chave / valor nos quais as chaves são objetos.

  • Mapobjetos são simples mapas de chave / valor. Qualquer valor (objetos e valores primitivos) pode ser usado como uma chave ou um valor.

Esteja ciente de que nenhum deles é amplamente suportado, mas você pode usar o ES6 Shim (requer ES5 nativo ou ES5 Shim ) para dar suporte Map, mas não WeakMap( veja o porquê ).

Oriol
fonte
Em 2019, eles são muito bem suportados e têm métodos incríveis! developer.mozilla.org/pt-BR/docs/Web/JavaScript/Reference/…
Juanma Menendez
13

Você precisaria armazenar em alguns dísticos de estado interno dos pares objeto / valor

HashMap = function(){
  this._dict = [];
}
HashMap.prototype._get = function(key){
  for(var i=0, couplet; couplet = this._dict[i]; i++){
    if(couplet[0] === key){
      return couplet;
    }
  }
}
HashMap.prototype.put = function(key, value){
  var couplet = this._get(key);
  if(couplet){
    couplet[1] = value;
  }else{
    this._dict.push([key, value]);
  }
  return this; // for chaining
}
HashMap.prototype.get = function(key){
  var couplet = this._get(key);
  if(couplet){
    return couplet[1];
  }
}

E use-o como tal:

var color = {}; // unique object instance
var shape = {}; // unique object instance
var map = new HashMap();
map.put(color, "blue");
map.put(shape, "round");
console.log("Item is", map.get(color), "and", map.get(shape));

Obviamente, essa implementação também está em algum lugar na linha de O (n). Os exemplos de Eugene acima são a única maneira de obter um hash que funcione com qualquer velocidade que você esperaria de um hash real.

Atualizar:

Outra abordagem, na linha da resposta de Eugene, é de alguma forma anexar um ID exclusivo a todos os objetos. Uma das minhas abordagens favoritas é usar um dos métodos internos herdados da superclasse Object, substituí-lo por uma passagem de função personalizada e anexar propriedades a esse objeto de função. Se você reescrevesse meu método HashMap para fazer isso, seria semelhante a:

HashMap = function(){
  this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
  if(typeof key == "object"){
    if(!key.hasOwnProperty._id){
      key.hasOwnProperty = function(key){
        return Object.prototype.hasOwnProperty.call(this, key);
      }
      key.hasOwnProperty._id = this._shared.id++;
    }
    this._dict[key.hasOwnProperty._id] = value;
  }else{
    this._dict[key] = value;
  }
  return this; // for chaining
}
HashMap.prototype.get = function get(key){
  if(typeof key == "object"){
    return this._dict[key.hasOwnProperty._id];
  }
  return this._dict[key];
}

Essa versão parece ser apenas um pouco mais rápida, mas em teoria será significativamente mais rápida para grandes conjuntos de dados.

pottedmeat
fonte
Uma matriz associativa, ou seja, uma matriz de 2 tuplas, é um mapa, não um HashMap; um HashMap é um mapa que usa hashes para melhor desempenho.
precisa
É verdade, mas por que dividir os cabelos sobre o assunto? Não há como criar um mapa de hash verdadeiro em JavaScript, pois você não pode obter endereços de memória de objeto. E os pares de chave / valor de objeto interno do JavaScript (usados ​​no meu segundo exemplo) podem atuar como HashMaps, mas não necessariamente, pois depende do tempo de execução usado no navegador e de como a pesquisa é implementada.
Pottedmeat
11

Infelizmente, nenhuma das respostas acima foi boa para o meu caso: objetos-chave diferentes podem ter o mesmo código de hash. Portanto, escrevi uma versão simples do HashMap semelhante a Java:

function HashMap() {
    this.buckets = {};
}

HashMap.prototype.put = function(key, value) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        bucket = new Array();
        this.buckets[hashCode] = bucket;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            bucket[i].value = value;
            return;
        }
    }
    bucket.push({ key: key, value: value });
}

HashMap.prototype.get = function(key) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        return null;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            return bucket[i].value;
        }
    }
}

HashMap.prototype.keys = function() {
    var keys = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            keys.push(bucket[i].key);
        }
    }
    return keys;
}

HashMap.prototype.values = function() {
    var values = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            values.push(bucket[i].value);
        }
    }
    return values;
}

Nota: os objetos principais devem "implementar" os métodos hashCode () e equals ().

Michael Spector
fonte
7
A preferência de new Array()over []é garantir a absoluta semelhança com Java do seu código? :)
Erik Kaplun
6

Eu implementei um HashMap JavaScript, cujo código pode ser obtido em http://github.com/lambder/HashMapJS/tree/master

Aqui está o código:

/*
 =====================================================================
 @license MIT
 @author Lambder
 @copyright 2009 Lambder.
 @end
 =====================================================================
 */
var HashMap = function() {
  this.initialize();
}

HashMap.prototype = {
  hashkey_prefix: "<#HashMapHashkeyPerfix>",
  hashcode_field: "<#HashMapHashkeyPerfix>",

  initialize: function() {
    this.backing_hash = {};
    this.code = 0;
  },
  /*
   maps value to key returning previous assocciation
   */
  put: function(key, value) {
    var prev;
    if (key && value) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        prev = this.backing_hash[hashCode];
      } else {
        this.code += 1;
        hashCode = this.hashkey_prefix + this.code;
        key[this.hashcode_field] = hashCode;
      }
      this.backing_hash[hashCode] = value;
    }
    return prev;
  },
  /*
   returns value associated with given key
   */
  get: function(key) {
    var value;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        value = this.backing_hash[hashCode];
      }
    }
    return value;
  },
  /*
   deletes association by given key.
   Returns true if the assocciation existed, false otherwise
   */
  del: function(key) {
    var success = false;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        var prev = this.backing_hash[hashCode];
        this.backing_hash[hashCode] = undefined;
        if(prev !== undefined)
          success = true;
      }
    }
    return success;
  }
}

//// Usage

// creation

var my_map = new HashMap();

// insertion

var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};

my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);

// retrieval

if(my_map.get(a_key) !== a_value){
  throw("fail1")
}
if(my_map.get(b_key) !== c_value){
  throw("fail2")
}
if(prev_b !== b_value){
  throw("fail3")
}

// deletion

var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);

if(a_existed !== true){
  throw("fail4")
}
if(c_existed !== false){
  throw("fail5")
}
if(a2_existed !== false){
  throw("fail6")
}
Lambder
fonte
2
Seu código parece não funcionar com a colocação do mesmo objeto em vários HashMaps.
precisa
5

No ECMA6, você pode usar o WeakMap

Exemplo:

var wm1 = new WeakMap(),
    wm2 = new WeakMap(),
    wm3 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // a value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // keys and values can be any objects. Even WeakMaps!

wm1.get(o2); // "azerty"
wm2.get(o2); // undefined, because there is no value for o2 on wm2
wm2.get(o3); // undefined, because that is the set value

wm1.has(o2); // true
wm2.has(o2); // false
wm2.has(o3); // true (even if the value itself is 'undefined')

wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // undefined, because wm3 was cleared and there is no value for o1 anymore

wm1.has(o1);   // true
wm1.delete(o1);
wm1.has(o1);   // false

Mas:

Because of references being weak, WeakMap keys are not enumerable (i.e. there is no method giving you a list of the keys). 
Nox73
fonte
oh louvor jesus, eles finalmente estão adicionando referências fracas ao javascript. é sobre o tempo ... +1 para isso, mas isso seria realmente terrível para uso, porque as referências são fracos
Claudiu
2

Javascript não constrói Mapa / hashmap. Deve ser chamado de matriz associativa .

hash["X"]é igual a hash.X, mas permite "X" como uma variável de sequência. Em outras palavras, hash[x]é funcionalmente igual aeval("hash."+x.toString())

É mais semelhante a object.properties, em vez de mapeamento de valores-chave. Se você estiver procurando um melhor mapeamento de chave / valor em Javascript, use o objeto Map que pode ser encontrado na web.

Dennis C
fonte
2

Tente minha implementação da tabela de hash JavaScript: http://www.timdown.co.uk/jshashtable

Ele procura um método hashCode () dos objetos principais, ou você pode fornecer uma função de hash ao criar um objeto Hashtable.

Tim Down
fonte
2

Parece uma solução bastante robusta: https://github.com/flesler/hashmap . Até funcionará bem para funções e objetos que parecem idênticos. O único truque usado é adicionar um membro obscuro a um objeto para identificá-lo. Se o seu programa não sobrescrever essa variável obscura (é algo como hashid ), você estará em ouro.

BT
fonte
2

Se o desempenho não é crítico (por exemplo, a quantidade de chaves é relativamente pequeno) e você não quer poluir o seu (ou talvez não a sua) objetos com campos adicionais, como _hash, _id, etc., então você pode fazer uso do fato de que Array.prototype.indexOfemprega igualdade estrita. Aqui está uma implementação simples:

var Dict = (function(){
    // IE 8 and earlier has no Array.prototype.indexOf
    function indexOfPolyfill(val) {
      for (var i = 0, l = this.length; i < l; ++i) {
        if (this[i] === val) {
          return i;
        }
      }
      return -1;
    }

    function Dict(){
      this.keys = [];
      this.values = [];
      if (!this.keys.indexOf) {
        this.keys.indexOf = indexOfPolyfill;
      }
    };

    Dict.prototype.has = function(key){
      return this.keys.indexOf(key) != -1;
    };

    Dict.prototype.get = function(key, defaultValue){
      var index = this.keys.indexOf(key);
      return index == -1 ? defaultValue : this.values[index];
    };

    Dict.prototype.set = function(key, value){
      var index = this.keys.indexOf(key);
      if (index == -1) {
        this.keys.push(key);
        this.values.push(value);
      } else {
        var prevValue = this.values[index];
        this.values[index] = value;
        return prevValue;
      }
    };

    Dict.prototype.delete = function(key){
      var index = this.keys.indexOf(key);
      if (index != -1) {
        this.keys.splice(index, 1);
        return this.values.splice(index, 1)[0];
      }
    };

    Dict.prototype.clear = function(){
      this.keys.splice(0, this.keys.length);
      this.values.splice(0, this.values.length);
    };

    return Dict;
})();

Exemplo de uso:

var a = {}, b = {},
    c = { toString: function(){ return '1'; } },
    d = 1, s = '1', u = undefined, n = null,
    dict = new Dict();

// keys and values can be anything
dict.set(a, 'a');
dict.set(b, 'b');
dict.set(c, 'c');
dict.set(d, 'd');
dict.set(s, 's');
dict.set(u, 'u');
dict.set(n, 'n');

dict.get(a); // 'a'
dict.get(b); // 'b'
dict.get(s); // 's'
dict.get(u); // 'u'
dict.get(n); // 'n'
// etc.

Comparando com o ES6 WeakMap, há dois problemas: O (n) tempo de pesquisa e não fraqueza (ou seja, causará vazamento de memória se você não usar deleteou clearliberar chaves).

skozin
fonte
2

My Map Implementation, derivado do exemplo de Christoph:

Exemplo de uso:

var map = new Map();  //creates an "in-memory" map
var map = new Map("storageId");  //creates a map that is loaded/persisted using html5 storage

function Map(storageId) {
    this.current = undefined;
    this.size = 0;
    this.storageId = storageId;
    if (this.storageId) {
        this.keys = new Array();
        this.disableLinking();
    }
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;
    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }
    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;

    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
//    this.removeAll = Map.illegal;


    return this;
};

// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    if (item === undefined) {
        if (this.storageId) {
            try {
                var itemStr = localStorage.getItem(this.storageId + key);
                if (itemStr && itemStr !== 'undefined') {
                    item = JSON.parse(itemStr);
                    this[this.hash(key)] = item;
                    this.keys.push(key);
                    ++this.size;
                }
            } catch (e) {
                console.log(e);
            }
        }
    }
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;
    if (this.storageId) {
        this.keys.push(key);
        try {
            localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
        } catch (e) {
            console.log(e);
        }
    }
    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];
    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }
    if (this.storageId) {
        try {
            localStorage.setItem(this.storageId + key, undefined);
        } catch (e) {
            console.log(e);
        }
    }
    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    if (this.storageId) {
        for (var i=0; i<this.keys.length; i++) {
            this.remove(this.keys[i]);
        }
        this.keys.length = 0;
    } else {
        while(this.size)
            this.remove(this.key());
    }
    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if (this.storageId) {
        return;
    }
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if (this.storageId) {
        return;
    }
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    if (this.storageId) {
        return undefined;
    } else {
        return this.current.key;
    }
};

Map.prototype.value = function() {
    if (this.storageId) {
        return undefined;
    }
    return this.current.value;
};
g00dnatur3
fonte
1

Adicionando mais uma solução: HashMapé praticamente a primeira classe que eu movi de Java para Javascript. Você poderia dizer que há muita sobrecarga, mas a implementação é quase 100% igual à implementação do Java e inclui todas as interfaces e subclasses.

O projeto pode ser encontrado aqui: https://github.com/Airblader/jsava Também anexarei o código-fonte (atual) da classe HashMap, mas, como afirmado, também depende da superclasse etc. A estrutura OOP usada é qooxdoo.

Edit: Observe que este código já está desatualizado e consulte o projeto github para o trabalho atual. No momento em que escrevemos isso, também há uma ArrayListimplementação.

qx.Class.define( 'jsava.util.HashMap', {
    extend: jsava.util.AbstractMap,
    implement: [jsava.util.Map, jsava.io.Serializable, jsava.lang.Cloneable],

    construct: function () {
        var args = Array.prototype.slice.call( arguments ),
            initialCapacity = this.self( arguments ).DEFAULT_INITIAL_CAPACITY,
            loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;

        switch( args.length ) {
            case 1:
                if( qx.Class.implementsInterface( args[0], jsava.util.Map ) ) {
                    initialCapacity = Math.max( ((args[0].size() / this.self( arguments ).DEFAULT_LOAD_FACTOR) | 0) + 1,
                        this.self( arguments ).DEFAULT_INITIAL_CAPACITY );
                    loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
                } else {
                    initialCapacity = args[0];
                }
                break;
            case 2:
                initialCapacity = args[0];
                loadFactor = args[1];
                break;
        }

        if( initialCapacity < 0 ) {
            throw new jsava.lang.IllegalArgumentException( 'Illegal initial capacity: ' + initialCapacity );
        }
        if( initialCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
            initialCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
        }
        if( loadFactor <= 0 || isNaN( loadFactor ) ) {
            throw new jsava.lang.IllegalArgumentException( 'Illegal load factor: ' + loadFactor );
        }

        var capacity = 1;
        while( capacity < initialCapacity ) {
            capacity <<= 1;
        }

        this._loadFactor = loadFactor;
        this._threshold = (capacity * loadFactor) | 0;
        this._table = jsava.JsavaUtils.emptyArrayOfGivenSize( capacity, null );
        this._init();
    },

    statics: {
        serialVersionUID: 1,

        DEFAULT_INITIAL_CAPACITY: 16,
        MAXIMUM_CAPACITY: 1 << 30,
        DEFAULT_LOAD_FACTOR: 0.75,

        _hash: function (hash) {
            hash ^= (hash >>> 20) ^ (hash >>> 12);
            return hash ^ (hash >>> 7) ^ (hash >>> 4);
        },

        _indexFor: function (hashCode, length) {
            return hashCode & (length - 1);
        },

        Entry: qx.Class.define( 'jsava.util.HashMap.Entry', {
            extend: jsava.lang.Object,
            implement: [jsava.util.Map.Entry],

            construct: function (hash, key, value, nextEntry) {
                this._value = value;
                this._next = nextEntry;
                this._key = key;
                this._hash = hash;
            },

            members: {
                _key: null,
                _value: null,
                /** @type jsava.util.HashMap.Entry */
                _next: null,
                /** @type Number */
                _hash: 0,

                getKey: function () {
                    return this._key;
                },

                getValue: function () {
                    return this._value;
                },

                setValue: function (newValue) {
                    var oldValue = this._value;
                    this._value = newValue;
                    return oldValue;
                },

                equals: function (obj) {
                    if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.HashMap.Entry ) ) {
                        return false;
                    }

                    /** @type jsava.util.HashMap.Entry */
                    var entry = obj,
                        key1 = this.getKey(),
                        key2 = entry.getKey();
                    if( key1 === key2 || (key1 !== null && key1.equals( key2 )) ) {
                        var value1 = this.getValue(),
                            value2 = entry.getValue();
                        if( value1 === value2 || (value1 !== null && value1.equals( value2 )) ) {
                            return true;
                        }
                    }

                    return false;
                },

                hashCode: function () {
                    return (this._key === null ? 0 : this._key.hashCode()) ^
                        (this._value === null ? 0 : this._value.hashCode());
                },

                toString: function () {
                    return this.getKey() + '=' + this.getValue();
                },

                /**
                 * This method is invoked whenever the value in an entry is
                 * overwritten by an invocation of put(k,v) for a key k that's already
                 * in the HashMap.
                 */
                _recordAccess: function (map) {
                },

                /**
                 * This method is invoked whenever the entry is
                 * removed from the table.
                 */
                _recordRemoval: function (map) {
                }
            }
        } )
    },

    members: {
        /** @type jsava.util.HashMap.Entry[] */
        _table: null,
        /** @type Number */
        _size: 0,
        /** @type Number */
        _threshold: 0,
        /** @type Number */
        _loadFactor: 0,
        /** @type Number */
        _modCount: 0,
        /** @implements jsava.util.Set */
        __entrySet: null,

        /**
         * Initialization hook for subclasses. This method is called
         * in all constructors and pseudo-constructors (clone, readObject)
         * after HashMap has been initialized but before any entries have
         * been inserted.  (In the absence of this method, readObject would
         * require explicit knowledge of subclasses.)
         */
        _init: function () {
        },

        size: function () {
            return this._size;
        },

        isEmpty: function () {
            return this._size === 0;
        },

        get: function (key) {
            if( key === null ) {
                return this.__getForNullKey();
            }

            var hash = this.self( arguments )._hash( key.hashCode() );
            for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
                 entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash && ((k = entry._key) === key || key.equals( k )) ) {
                    return entry._value;
                }
            }

            return null;
        },

        __getForNullKey: function () {
            for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
                if( entry._key === null ) {
                    return entry._value;
                }
            }

            return null;
        },

        containsKey: function (key) {
            return this._getEntry( key ) !== null;
        },

        _getEntry: function (key) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() );
            for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
                 entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash
                    && ( ( k = entry._key ) === key || ( key !== null && key.equals( k ) ) ) ) {
                    return entry;
                }
            }

            return null;
        },

        put: function (key, value) {
            if( key === null ) {
                return this.__putForNullKey( value );
            }

            var hash = this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length );
            for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash && ( (k = entry._key) === key || key.equals( k ) ) ) {
                    var oldValue = entry._value;
                    entry._value = value;
                    entry._recordAccess( this );
                    return oldValue;
                }
            }

            this._modCount++;
            this._addEntry( hash, key, value, i );
            return null;
        },

        __putForNullKey: function (value) {
            for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
                if( entry._key === null ) {
                    var oldValue = entry._value;
                    entry._value = value;
                    entry._recordAccess( this );
                    return oldValue;
                }
            }

            this._modCount++;
            this._addEntry( 0, null, value, 0 );
            return null;
        },

        __putForCreate: function (key, value) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length );
            for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash
                    && ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
                    entry._value = value;
                    return;
                }
            }

            this._createEntry( hash, key, value, i );
        },

        __putAllForCreate: function (map) {
            var iterator = map.entrySet().iterator();
            while( iterator.hasNext() ) {
                var entry = iterator.next();
                this.__putForCreate( entry.getKey(), entry.getValue() );
            }
        },

        _resize: function (newCapacity) {
            var oldTable = this._table,
                oldCapacity = oldTable.length;
            if( oldCapacity === this.self( arguments ).MAXIMUM_CAPACITY ) {
                this._threshold = Number.MAX_VALUE;
                return;
            }

            var newTable = jsava.JsavaUtils.emptyArrayOfGivenSize( newCapacity, null );
            this._transfer( newTable );
            this._table = newTable;
            this._threshold = (newCapacity * this._loadFactor) | 0;
        },

        _transfer: function (newTable) {
            var src = this._table,
                newCapacity = newTable.length;
            for( var j = 0; j < src.length; j++ ) {
                var entry = src[j];
                if( entry !== null ) {
                    src[j] = null;
                    do {
                        var next = entry._next,
                            i = this.self( arguments )._indexFor( entry._hash, newCapacity );
                        entry._next = newTable[i];
                        newTable[i] = entry;
                        entry = next;
                    } while( entry !== null );
                }
            }
        },

        putAll: function (map) {
            var numKeyToBeAdded = map.size();
            if( numKeyToBeAdded === 0 ) {
                return;
            }

            if( numKeyToBeAdded > this._threshold ) {
                var targetCapacity = (numKeyToBeAdded / this._loadFactor + 1) | 0;
                if( targetCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
                    targetCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
                }

                var newCapacity = this._table.length;
                while( newCapacity < targetCapacity ) {
                    newCapacity <<= 1;
                }
                if( newCapacity > this._table.length ) {
                    this._resize( newCapacity );
                }
            }

            var iterator = map.entrySet().iterator();
            while( iterator.hasNext() ) {
                var entry = iterator.next();
                this.put( entry.getKey(), entry.getValue() );
            }
        },

        remove: function (key) {
            var entry = this._removeEntryForKey( key );
            return entry === null ? null : entry._value;
        },

        _removeEntryForKey: function (key) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length ),
                prev = this._table[i],
                entry = prev;

            while( entry !== null ) {
                var next = entry._next,
                    /** @type jsava.lang.Object */
                        k;
                if( entry._hash === hash
                    && ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
                    this._modCount++;
                    this._size--;
                    if( prev === entry ) {
                        this._table[i] = next;
                    } else {
                        prev._next = next;
                    }
                    entry._recordRemoval( this );
                    return entry;
                }
                prev = entry;
                entry = next;
            }

            return entry;
        },

        _removeMapping: function (obj) {
            if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
                return null;
            }

            /** @implements jsava.util.Map.Entry */
            var entry = obj,
                key = entry.getKey(),
                hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length ),
                prev = this._table[i],
                e = prev;

            while( e !== null ) {
                var next = e._next;
                if( e._hash === hash && e.equals( entry ) ) {
                    this._modCount++;
                    this._size--;
                    if( prev === e ) {
                        this._table[i] = next;
                    } else {
                        prev._next = next;
                    }
                    e._recordRemoval( this );
                    return e;
                }
                prev = e;
                e = next;
            }

            return e;
        },

        clear: function () {
            this._modCount++;
            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                table[i] = null;
            }
            this._size = 0;
        },

        containsValue: function (value) {
            if( value === null ) {
                return this.__containsNullValue();
            }

            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                for( var entry = table[i]; entry !== null; entry = entry._next ) {
                    if( value.equals( entry._value ) ) {
                        return true;
                    }
                }
            }

            return false;
        },

        __containsNullValue: function () {
            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                for( var entry = table[i]; entry !== null; entry = entry._next ) {
                    if( entry._value === null ) {
                        return true;
                    }
                }
            }

            return false;
        },

        clone: function () {
            /** @type jsava.util.HashMap */
            var result = null;
            try {
                result = this.base( arguments );
            } catch( e ) {
                if( !qx.Class.isSubClassOf( e.constructor, jsava.lang.CloneNotSupportedException ) ) {
                    throw e;
                }
            }

            result._table = jsava.JsavaUtils.emptyArrayOfGivenSize( this._table.length, null );
            result.__entrySet = null;
            result._modCount = 0;
            result._size = 0;
            result._init();
            result.__putAllForCreate( this );

            return result;
        },

        _addEntry: function (hash, key, value, bucketIndex) {
            var entry = this._table[bucketIndex];
            this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
            if( this._size++ >= this._threshold ) {
                this._resize( 2 * this._table.length );
            }
        },

        _createEntry: function (hash, key, value, bucketIndex) {
            var entry = this._table[bucketIndex];
            this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
            this._size++;
        },

        keySet: function () {
            var keySet = this._keySet;
            return keySet !== null ? keySet : ( this._keySet = new this.KeySet( this ) );
        },

        values: function () {
            var values = this._values;
            return values !== null ? values : ( this._values = new this.Values( this ) );
        },

        entrySet: function () {
            return this.__entrySet0();
        },

        __entrySet0: function () {
            var entrySet = this.__entrySet;
            return entrySet !== null ? entrySet : ( this.__entrySet = new this.EntrySet( this ) );
        },

        /** @private */
        HashIterator: qx.Class.define( 'jsava.util.HashMap.HashIterator', {
            extend: jsava.lang.Object,
            implement: [jsava.util.Iterator],

            type: 'abstract',

            /** @protected */
            construct: function (thisHashMap) {
                this.__thisHashMap = thisHashMap;
                this._expectedModCount = this.__thisHashMap._modCount;
                if( this.__thisHashMap._size > 0 ) {
                    var table = this.__thisHashMap._table;
                    while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
                        // do nothing
                    }
                }
            },

            members: {
                __thisHashMap: null,

                /** @type jsava.util.HashMap.Entry */
                _next: null,
                /** @type Number */
                _expectedModCount: 0,
                /** @type Number */
                _index: 0,
                /** @type jsava.util.HashMap.Entry */
                _current: null,

                hasNext: function () {
                    return this._next !== null;
                },

                _nextEntry: function () {
                    if( this.__thisHashMap._modCount !== this._expectedModCount ) {
                        throw new jsava.lang.ConcurrentModificationException();
                    }

                    var entry = this._next;
                    if( entry === null ) {
                        throw new jsava.lang.NoSuchElementException();
                    }

                    if( (this._next = entry._next) === null ) {
                        var table = this.__thisHashMap._table;
                        while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
                            // do nothing
                        }
                    }

                    this._current = entry;
                    return entry;
                },

                remove: function () {
                    if( this._current === null ) {
                        throw new jsava.lang.IllegalStateException();
                    }

                    if( this.__thisHashMap._modCount !== this._expectedModCount ) {
                        throw new jsava.lang.ConcurrentModificationException();
                    }

                    var key = this._current._key;
                    this._current = null;
                    this.__thisHashMap._removeEntryForKey( key );
                    this._expectedModCount = this.__thisHashMap._modCount;
                }
            }
        } ),

        _newKeyIterator: function () {
            return new this.KeyIterator( this );
        },

        _newValueIterator: function () {
            return new this.ValueIterator( this );
        },

        _newEntryIterator: function () {
            return new this.EntryIterator( this );
        },

        /** @private */
        ValueIterator: qx.Class.define( 'jsava.util.HashMap.ValueIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry()._value;
                }
            }
        } ),

        /** @private */
        KeyIterator: qx.Class.define( 'jsava.util.HashMap.KeyIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry().getKey();
                }
            }
        } ),

        /** @private */
        EntryIterator: qx.Class.define( 'jsava.util.HashMap.EntryIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry();
                }
            }
        } ),

        /** @private */
        KeySet: qx.Class.define( 'jsava.util.HashMap.KeySet', {
            extend: jsava.util.AbstractSet,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newKeyIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    return this.__thisHashMap.containsKey( obj );
                },

                remove: function (obj) {
                    return this.__thisHashMap._removeEntryForKey( obj ) !== null;
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } ),

        /** @private */
        Values: qx.Class.define( 'jsava.util.HashMap.Values', {
            extend: jsava.util.AbstractCollection,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newValueIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    return this.__thisHashMap.containsValue( obj );
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } ),

        /** @private */
        EntrySet: qx.Class.define( 'jsava.util.HashMap.EntrySet', {
            extend: jsava.util.AbstractSet,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newEntryIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
                        return false;
                    }

                    /** @implements jsava.util.Map.Entry */
                    var entry = obj,
                        candidate = this.__thisHashMap._getEntry( entry.getKey() );
                    return candidate !== null && candidate.equals( entry );
                },

                remove: function (obj) {
                    return this.__thisHashMap._removeMapping( obj ) !== null;
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } )
    }
} );
Ingo Bürk
fonte
Hmm abordagem interessante .. você já pensou em experimentar uma abordagem automatizada? isto é, executando um compilador Java para javascript no código-fonte da implementação java atual?
19413 Claudiu
Não. :) Este é apenas um projeto divertido para mim e havia algumas coisas em que eu não podia simplesmente "copiar" o código. Não estou ciente dos compiladores Java para Javascript, apesar de acreditar que eles existem. Não tenho certeza de como eles traduziriam isso. Estou bastante certo de que eles não produziriam código de boa qualidade em nenhum caso.
Ingo Bürk
Ah, peguei. Eu estava pensando em no compilador Google Web Toolkit , mas parece que eles acabaram fazendo o que você está fazendo aqui pelas bibliotecas principais: "O compilador GWT suporta a grande maioria da própria linguagem Java. A biblioteca de tempo de execução GWT emula um subconjunto relevante do Biblioteca de tempo de execução Java ". Talvez algo para olhar para ver como os outros resolveram o mesmo problema!
19413 Claudiu
Sim. Tenho certeza de que a solução do Google está muito além da minha, mas, novamente, estou me divertindo um pouco. Infelizmente, o código fonte parece ter sido revogado (?), Pelo menos não consigo navegar nele e os links interessantes parecem estar mortos. Que pena, eu adoraria olhar para isso.
Ingo Bürk
Divertir-se brincando é a melhor maneira de aprender =). obrigado por compartilhar
Claudiu
0

Mais uma implementação de mapa por mim. Com o randomizador, 'genéricos' e 'iterador' =)

var HashMap = function (TKey, TValue) {
    var db = [];
    var keyType, valueType;

    (function () {
        keyType = TKey;
        valueType = TValue;
    })();

    var getIndexOfKey = function (key) {
        if (typeof key !== keyType)
            throw new Error('Type of key should be ' + keyType);
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return i;
        }
        return -1;
    }

    this.add = function (key, value) {
        if (typeof key !== keyType) {
            throw new Error('Type of key should be ' + keyType);
        } else if (typeof value !== valueType) {
            throw new Error('Type of value should be ' + valueType);
        }
        var index = getIndexOfKey(key);
        if (index === -1)
            db.push([key, value]);
        else
            db[index][1] = value;
        return this;
    }

    this.get = function (key) {
        if (typeof key !== keyType || db.length === 0)
            return null;
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return db[i][1];
        }
        return null;
    }

    this.size = function () {
        return db.length;
    }

    this.keys = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.push(db[i][0]);
        }
        return result;
    }

    this.values = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.push(db[i][1]);
        }
        return result;
    }

    this.randomize = function () {
        if (db.length === 0)
            return this;
        var currentIndex = db.length, temporaryValue, randomIndex;
        while (0 !== currentIndex) {
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex--;
            temporaryValue = db[currentIndex];
            db[currentIndex] = db[randomIndex];
            db[randomIndex] = temporaryValue;
        }
        return this;
    }

    this.iterate = function (callback) {
        if (db.length === 0)
            return false;
        for (var i = 0; i < db.length; i++) {
            callback(db[i][0], db[i][1]);
        }
        return true;
    }
}

Exemplo:

var a = new HashMap("string", "number");
a.add('test', 1132)
 .add('test14', 666)
 .add('1421test14', 12312666)
 .iterate(function (key, value) {console.log('a['+key+']='+value)});
/*
a[test]=1132
a[test14]=666
a[1421test14]=12312666 
*/
a.randomize();
/*
a[1421test14]=12312666
a[test]=1132
a[test14]=666
*/
ovnia
fonte