Cómo hacer una matriz asociativa / hashing en JavaScript

574

Necesito almacenar algunas estadísticas usando JavaScript de una manera como lo haría en C #:

Dictionary<string, int> statistics;

statistics["Foo"] = 10;
statistics["Goo"] = statistics["Goo"] + 1;
statistics.Add("Zoo", 1);

¿Hay Hashtablealgo o algo así Dictionary<TKey, TValue>en JavaScript?
¿Cómo podría almacenar valores de tal manera?

George2
fuente
1
js se escribe libremente, por lo que no hay forma de declarar una cadena o int, solo puede declarar una var y asignarle una cadena o int. : D
Gordon Gustafson el
Es posible que desee ver xDict. jsfiddle.net/very/MuVwd Es una cadena de diccionario => cualquier cosa escrita en Javascript.
Robert
Este artículo tiene una excelente explicación de cómo las matrices asociativas se implementan bajo el capó en Javascript jayconrod.com/posts/52/a-tour-of-v8-object-representation
Shuklaswag
La respuesta aceptada se escribió en 2009, solo admite claves de cadena . Para claves que no son cadenas, use Map o WeakMap, como en la respuesta de Vitalii .
ToolmakerSteve

Respuestas:

565

Use objetos JavaScript como matrices asociativas .

Matriz asociativa: en palabras simples, las matrices asociativas usan cadenas en lugar de números enteros como índice.

Crea un objeto con

var dictionary = {};

Javascript le permite agregar propiedades a los objetos mediante la siguiente sintaxis:

Object.yourProperty = value;

Una sintaxis alternativa para el mismo es:

Object["yourProperty"] = value;

Si también puede crear claves para asignar mapas de objetos con la siguiente sintaxis

var point = { x:3, y:2 };

point["x"] // returns 3
point.y // returns 2

Puede iterar a través de una matriz asociativa utilizando la construcción de bucle for..in de la siguiente manera

for(var key in Object.keys(dict)){
  var value = dict[key];
  /* use key/value for intended purpose */
}
Alek Davis
fuente
36
Tenga en cuenta que el enfoque del autor de inicializar una "matriz asociativa" new Array()está mal visto. El artículo finalmente menciona sus inconvenientes y sugiere new Object()o {}como alternativas preferidas, pero eso está cerca del final y me temo que la mayoría de los lectores no llegarán tan lejos.
Daniel Lubarov
24
Fallar. JavaScript no admite referencias de objetos como claves, mientras que algo como Diccionario Flash / AS3 sí. En JavaScript, var obj1 = {}; var obj2 = {}; var table= {}; table[obj1] = "A"; table[obj2] = "B"; alert(table[obj1]); //displays Bporque no puede diferenciar entre las claves obj1 y obj2; ambos se convierten en cadenas y se convierten en algo así como "Objeto". Fallo total, y hace que la serialización de tipo seguro con referencias y referencias cíclicas intactas sea difícil o no tenga rendimiento en JavaScript. Es fácil en Flash / AS3.
Triynko
Bueno, la única forma en JS que podemos validar verificando la igualdad o definiendo un método igual por algo como esto: Point.prototype.equals = function(obj) { return (obj instanceof Point) && (obj.x === this.x) && (obj.y === this.y); };
Nadeem
1
@Leo console.log ({A: 'B', C: 'D'} [foo]) debería darle A B.
ychaouche
2
@Leo El ejemplo parece incorrecto. for... inporque un diccionario recorrerá sus teclas, por lo que Object.keysparece mal ubicado allí. Object.keysdevuelve una matriz de las claves del diccionario y, for... inpara una matriz, recorre sus "claves", que para una matriz son sus índices, no sus valores.
JHH
434
var associativeArray = {};
associativeArray["one"] = "First";
associativeArray["two"] = "Second";
associativeArray["three"] = "Third";

Si viene de un lenguaje orientado a objetos, debería consultar este artículo .

Dani Cricco
fuente
38
También puede hacer esto en menos líneas: var associativeArray = {"one": "First", "two": "second", "three": "Third"}; Luego, asociativeArray ["one"] devuelve "First" y assocativeArray ["four"] devuelve nulo.
Tony Wickham
2
Lo siento @JuusoOhtonen, escribí la publicación hace 6 años (es increíble lo rápido que pasa el tiempo). He actualizado el enlace. Por favor
verifíquelo
145

Todos los navegadores modernos admiten un objeto Map de JavaScript . Hay un par de razones que hacen que usar un Mapa sea mejor que un Objeto:

  • Un objeto tiene un prototipo, por lo que hay claves predeterminadas en el mapa.
  • Las claves de un objeto son cadenas, donde pueden ser cualquier valor para un mapa.
  • Puede obtener el tamaño de un Mapa fácilmente mientras tiene que hacer un seguimiento del tamaño de un Objeto.

Ejemplo:

var myMap = new Map();

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

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

myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"

Si desea que las claves a las que no se hace referencia desde otros objetos se recojan como basura, considere usar un WeakMap en lugar de un Mapa.

Vitalii Fedorenko
fuente
55
Esperemos que en unos años esta sea la respuesta más votada.
Cameron Lee
1
@CameronLee seguramente lo hará
Loïc Faure-Lacroix
1
Esto Mapes apenas útil cuando su clave es un objeto, pero debe compararse por valor, no por referencia.
Siyuan Ren
77
Más de un año después de que se escribió esta respuesta, todavía NO es cierto que "todos los navegadores modernos admiten Map". Solo en el escritorio puede contar con al menos soporte básico de mapas. No en dispositivos móviles. Por ejemplo, el navegador de Android no tiene soporte para mapas. Incluso en el escritorio, algunas implementaciones están incompletas. Por ejemplo, IE11 todavía no admite la enumeración a través de "para ... de ...", por lo que si desea compatibilidad con IE, debe usar el repugnante .forEach kludge. Además, JSON.stringify () no funciona para Map en ningún navegador que haya probado. Además, los inicializadores no funcionan en IE o Safari.
Dave Burton
3
Hay un excelente soporte para el navegador. Revisar otra vez. En cualquier caso, esto es bastante fácil de rellenar, por lo que el soporte nativo del navegador no es un problema.
Brad
132

A menos que tenga una razón específica para no hacerlo, simplemente use un objeto normal. Se puede hacer referencia a las propiedades de objeto en Javascript utilizando la sintaxis de estilo hashtable:

var hashtable = {};
hashtable.foo = "bar";
hashtable['bar'] = "foo";

Ambos elementos fooy barahora pueden ser referenciados como:

hashtable['foo'];
hashtable['bar'];
// or
hashtable.foo;
hashtable.bar;

Por supuesto, esto significa que sus claves deben ser cadenas. Si no son cadenas, se convierten internamente en cadenas, por lo que aún puede funcionar, YMMV.

roryf
fuente
1
Las claves como enteros no me causaron ningún problema. stackoverflow.com/questions/2380019/…
Jonas Elfström
10
Jonas: tenga en cuenta que sus enteros se convierten en cadenas cuando se establece la propiedad: var hash = {}; hash[1] = "foo"; alert(hash["1"]);alerta "foo".
Tim Down
17
¿Qué pasa si una de sus claves es " proto " o " padre "?
favor
55
Tenga en cuenta que los objetos no se pueden usar como claves en JavaScript. Bueno, pueden, pero se convierten a sus representaciones de cadena, por lo que cualquier objeto terminará exactamente como la misma clave. Vea la sugerencia jshashtable de @ TimDown a continuación.
ericsoco
21
Este ejemplo es confuso porque estás usando foo y bar como clave y valor en dos instancias. Mucho más claro para mostrar que var dict = {}; dict.key1 = "val1"; dict["key2"] = "val2";el elemento key1 de dict puede ser referenciado de manera equivalente por ambos dict["key1"]y dict.key1.
Jim
49

Dado que cada objeto en JS se comporta como, y generalmente se implementa como, una tabla hash, simplemente sigo con eso ...

var hashSweetHashTable = {};
Shog9
fuente
26
Vota abajo porque no muestra cómo acceder realmente a los valores en la "tabla hash".
IQAndreas
Llego 9 años tarde (no sabía mucho sobre programación, y mucho menos este sitio en ese entonces), pero ... ¿Qué pasa si estás tratando de almacenar puntos en un mapa y necesitas ver si ya hay algo? en un punto en un mapa? En ese caso, sería mejor usar HashTable para esto, buscando coordenadas (un objeto , no una cadena ).
Mike Warren
@MikeWarren if (hashSweetHashTable.foo)debería ingresar el bloque if si fooestá configurado.
Koray Tugay
21

entonces en C # el código se ve así:

Dictionary<string,int> dictionary = new Dictionary<string,int>();
dictionary.add("sample1", 1);
dictionary.add("sample2", 2);

o

var dictionary = new Dictionary<string, int> {
    {"sample1", 1},
    {"sample2", 2}
};

en JavaScript

var dictionary = {
    "sample1": 1,
    "sample2": 2
}

El objeto del diccionario C # contiene métodos útiles, como dictionary.ContainsKey() en JavaScript, podríamos usar el hasOwnPropertylike

if (dictionary.hasOwnProperty("sample1"))
    console.log("sample1 key found and its value is"+ dictionary["sample1"]);
Raj
fuente
1
Voto para mí no tener que escribir una respuesta sobrehasOwnProperty
brichins
18

Si necesita que sus claves sean cualquier objeto en lugar de solo cadenas, puede usar mi jshashtable .

Tim Down
fuente
3
¿Cuántas horas pasé tropezando con el hecho de que los objetos realmente no se pueden usar como claves para las matrices JS-style-Object-as-asociative-arrays antes de encontrar esto? Gracias Tim.
ericsoco
1
Flash / AS3 Dictionary, junto con la mayoría de los otros idiomas, admiten referencias de objetos como claves. JavaScript todavía no lo ha implementado todavía, pero creo que está en una especificación futura como un tipo de clase de Mapa. De nuevo con los polyfills mientras tanto; tanto para los estándares. Oh, espera ... finalmente en 2015, el mapa parece haber llegado: stackoverflow.com/a/30088129/88409 , y es compatible con navegadores "modernos", jajaja: kangax.github.io/compat-table/es6/# Mapa (y realmente no es ampliamente compatible). Solo una década detrás de AS3.
Triynko
Tim, quizás deberías actualizar jshashtable para usar Map () cuando esté disponible.
Dave Burton
1
@DaveBurton: Buen plan. Lo haré tan pronto como tenga algo de tiempo.
Tim Down
6
function HashTable() {
    this.length = 0;
    this.items = new Array();
    for (var i = 0; i < arguments.length; i += 2) {
        if (typeof (arguments[i + 1]) != 'undefined') {
            this.items[arguments[i]] = arguments[i + 1];
            this.length++;
        }
    }

    this.removeItem = function (in_key) {
        var tmp_previous;
        if (typeof (this.items[in_key]) != 'undefined') {
            this.length--;
            var tmp_previous = this.items[in_key];
            delete this.items[in_key];
        }

        return tmp_previous;
    }

    this.getItem = function (in_key) {
        return this.items[in_key];
    }

    this.setItem = function (in_key, in_value) {
        var tmp_previous;
        if (typeof (in_value) != 'undefined') {
            if (typeof (this.items[in_key]) == 'undefined') {
                this.length++;
            } else {
                tmp_previous = this.items[in_key];
            }

            this.items[in_key] = in_value;
        }

        return tmp_previous;
    }

    this.hasItem = function (in_key) {
        return typeof (this.items[in_key]) != 'undefined';
    }

    this.clear = function () {
        for (var i in this.items) {
            delete this.items[i];
        }

        this.length = 0;
    }
}
Birey
fuente
1
Para las personas que están votando por esto, ¿pueden comentar por qué? Esta respuesta fue publicada en 2011 y no en la fecha actual.
Birey
2
No voté en contra pero ... no deberías usar una matriz como objeto. No estoy 100% seguro si esta fue tu intención. Use la división en matrices que no se eliminan para volver a indexar; eliminar está bien pero se establecerá en indefinido; mejor ser explícito; use = undefined en un objeto también b / c es más rápido (pero más memoria). En resumen: siempre use un objeto: {}no una matriz: []o new Array()si tiene la intención de tener claves de cadena, de lo contrario, el motor js tiene un problema: verá 2 tipos para 1 variable, lo que significa que no hay optimización o se ejecutará con la matriz y se dará cuenta tiene que cambiar a objeto (posible reasignación).
Graeme Wicksted
2
Al igual que con la respuesta de Alex Hawkins, proporcione alguna explicación de por qué este código de aspecto bastante complejo es realmente útil y mejor que las otras respuestas más cortas que se dan aquí.
Thomas Tempelmann
6

Creé esto para lograr algún problema, como el mapeo de clave de objeto, la capacidad de enumeración (con el forEach()método) y el borrado.

function Hashtable() {
    this._map = new Map();
    this._indexes = new Map();
    this._keys = [];
    this._values = [];
    this.put = function(key, value) {
        var newKey = !this.containsKey(key);
        this._map.set(key, value);
        if (newKey) {
            this._indexes.set(key, this.length);
            this._keys.push(key);
            this._values.push(value);
        }
    };
    this.remove = function(key) {
        if (!this.containsKey(key))
            return;
        this._map.delete(key);
        var index = this._indexes.get(key);
        this._indexes.delete(key);
        this._keys.splice(index, 1);
        this._values.splice(index, 1);
    };
    this.indexOfKey = function(key) {
        return this._indexes.get(key);
    };
    this.indexOfValue = function(value) {
        return this._values.indexOf(value) != -1;
    };
    this.get = function(key) {
        return this._map.get(key);
    };
    this.entryAt = function(index) {
        var item = {};
        Object.defineProperty(item, "key", {
            value: this.keys[index],
            writable: false
        });
        Object.defineProperty(item, "value", {
            value: this.values[index],
            writable: false
        });
        return item;
    };
    this.clear = function() {
        var length = this.length;
        for (var i = 0; i < length; i++) {
            var key = this.keys[i];
            this._map.delete(key);
            this._indexes.delete(key);
        }
        this._keys.splice(0, length);
    };
    this.containsKey = function(key) {
        return this._map.has(key);
    };
    this.containsValue = function(value) {
        return this._values.indexOf(value) != -1;
    };
    this.forEach = function(iterator) {
        for (var i = 0; i < this.length; i++)
            iterator(this.keys[i], this.values[i], i);
    };
    Object.defineProperty(this, "length", {
        get: function() {
            return this._keys.length;
        }
    });
    Object.defineProperty(this, "keys", {
        get: function() {
            return this._keys;
        }
    });
    Object.defineProperty(this, "values", {
        get: function() {
            return this._values;
        }
    });
    Object.defineProperty(this, "entries", {
        get: function() {
            var entries = new Array(this.length);
            for (var i = 0; i < entries.length; i++)
                entries[i] = this.entryAt(i);
            return entries;
        }
    });
}


Documentación de clase. Hashtable

Métodos:

  • get(key)
    Devuelve el valor asociado a la clave especificada.
    Parámetros::
    key la clave de la que recuperar el valor.

  • put(key, value)
    Asocia el valor especificado a la clave especificada.
    Parámetros::
    key la clave a la que asocia el valor.
    value: El valor a asociar a la clave.

  • remove(key)
    Elimina la clave especificada con su valor.
    Parámetros::
    key la clave para eliminar.

  • clear()
    Borra toda la tabla hash, eliminando tanto las claves como los valores.

  • indexOfKey(key)
    Devuelve el índice de la clave especificada, en función del orden de adición.
    Parámetros::
    key La clave de la cual obtiene el índice.

  • indexOfValue(value)
    Devuelve el índice del valor especificado, en función del orden de adición.
    Parámetros::
    value el valor del cual se obtiene el índice.
    Notas:
    Esta información se recupera por el indexOf()método de una matriz, por lo que compara el objeto solo con el toString()método.

  • entryAt(index)
    Devuelve un objeto con dos propiedades: clave y valor, que representa la entrada en el índice especificado.
    Parámetros::
    index el índice de la entrada a obtener.

  • containsKey(key)
    Devuelve si la tabla hash contiene la clave especificada.
    Parámetros::
    key La clave para verificar.

  • containsValue(value)
    Devuelve si la tabla hash contiene el valor especificado.
    Parámetros::
    value el valor a verificar.

  • forEach(iterator)
    Itera todas las entradas en el especificado iterator.
    Parámetros:
    value : Un método con 3 parámetros: key, valuey index, donde indexrepresenta el índice de la entrada.

    Propiedades:

  • length ( Solo lectura )
    Obtiene el recuento de las entradas en la tabla hash.

  • keys ( Solo lectura )
    Obtiene una matriz de todas las claves en la tabla hash.

  • values ( Solo lectura )
    Obtiene una matriz de todos los valores en la tabla hash.

  • entries ( Solo lectura )
    Obtiene una matriz de todas las entradas en la tabla hash. Están representados en la misma forma del método entryAt().

Davide Cannizzo
fuente
2

https://gist.github.com/alexhawkins/f6329420f40e5cafa0a4

var HashTable = function() {
  this._storage = [];
  this._count = 0;
  this._limit = 8;
}


HashTable.prototype.insert = function(key, value) {
  //create an index for our storage location by passing it through our hashing function
  var index = this.hashFunc(key, this._limit);
  //retrieve the bucket at this particular index in our storage, if one exists
  //[[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ]  [ [k,v] ] ]
  var bucket = this._storage[index]
    //does a bucket exist or do we get undefined when trying to retrieve said index?
  if (!bucket) {
    //create the bucket
    var bucket = [];
    //insert the bucket into our hashTable
    this._storage[index] = bucket;
  }

  var override = false;
  //now iterate through our bucket to see if there are any conflicting
  //key value pairs within our bucket. If there are any, override them.
  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    if (tuple[0] === key) {
      //overide value stored at this key
      tuple[1] = value;
      override = true;
    }
  }

  if (!override) {
    //create a new tuple in our bucket
    //note that this could either be the new empty bucket we created above
    //or a bucket with other tupules with keys that are different than 
    //the key of the tuple we are inserting. These tupules are in the same
    //bucket because their keys all equate to the same numeric index when
    //passing through our hash function.
    bucket.push([key, value]);
    this._count++
      //now that we've added our new key/val pair to our storage
      //let's check to see if we need to resize our storage
      if (this._count > this._limit * 0.75) {
        this.resize(this._limit * 2);
      }
  }
  return this;
};


HashTable.prototype.remove = function(key) {
  var index = this.hashFunc(key, this._limit);
  var bucket = this._storage[index];
  if (!bucket) {
    return null;
  }
  //iterate over the bucket
  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    //check to see if key is inside bucket
    if (tuple[0] === key) {
      //if it is, get rid of this tuple
      bucket.splice(i, 1);
      this._count--;
      if (this._count < this._limit * 0.25) {
        this._resize(this._limit / 2);
      }
      return tuple[1];
    }
  }
};



HashTable.prototype.retrieve = function(key) {
  var index = this.hashFunc(key, this._limit);
  var bucket = this._storage[index];

  if (!bucket) {
    return null;
  }

  for (var i = 0; i < bucket.length; i++) {
    var tuple = bucket[i];
    if (tuple[0] === key) {
      return tuple[1];
    }
  }

  return null;
};


HashTable.prototype.hashFunc = function(str, max) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    var letter = str[i];
    hash = (hash << 5) + letter.charCodeAt(0);
    hash = (hash & hash) % max;
  }
  return hash;
};


HashTable.prototype.resize = function(newLimit) {
  var oldStorage = this._storage;

  this._limit = newLimit;
  this._count = 0;
  this._storage = [];

  oldStorage.forEach(function(bucket) {
    if (!bucket) {
      return;
    }
    for (var i = 0; i < bucket.length; i++) {
      var tuple = bucket[i];
      this.insert(tuple[0], tuple[1]);
    }
  }.bind(this));
};


HashTable.prototype.retrieveAll = function() {
  console.log(this._storage);
  //console.log(this._limit);
};

/******************************TESTS*******************************/

var hashT = new HashTable();

hashT.insert('Alex Hawkins', '510-599-1930');
//hashT.retrieve();
//[ , , , [ [ 'Alex Hawkins', '510-599-1930' ] ] ]
hashT.insert('Boo Radley', '520-589-1970');
//hashT.retrieve();
//[ , [ [ 'Boo Radley', '520-589-1970' ] ], , [ [ 'Alex Hawkins', '510-599-1930' ] ] ]
hashT.insert('Vance Carter', '120-589-1970').insert('Rick Mires', '520-589-1970').insert('Tom Bradey', '520-589-1970').insert('Biff Tanin', '520-589-1970');
//hashT.retrieveAll();
/* 
[ ,
  [ [ 'Boo Radley', '520-589-1970' ],
    [ 'Tom Bradey', '520-589-1970' ] ],
  ,
  [ [ 'Alex Hawkins', '510-599-1930' ],
    [ 'Rick Mires', '520-589-1970' ] ],
  ,
  ,
  [ [ 'Biff Tanin', '520-589-1970' ] ] ]
*/

//overide example (Phone Number Change)
//
hashT.insert('Rick Mires', '650-589-1970').insert('Tom Bradey', '818-589-1970').insert('Biff Tanin', '987-589-1970');
//hashT.retrieveAll();

/* 
[ ,
  [ [ 'Boo Radley', '520-589-1970' ],
    [ 'Tom Bradey', '818-589-1970' ] ],
  ,
  [ [ 'Alex Hawkins', '510-599-1930' ],
    [ 'Rick Mires', '650-589-1970' ] ],
  ,
  ,
  [ [ 'Biff Tanin', '987-589-1970' ] ] ]

*/

hashT.remove('Rick Mires');
hashT.remove('Tom Bradey');
//hashT.retrieveAll();

/* 
[ ,
  [ [ 'Boo Radley', '520-589-1970' ] ],
  ,
  [ [ 'Alex Hawkins', '510-599-1930' ] ],
  ,
  ,
  [ [ 'Biff Tanin', '987-589-1970' ] ] ]


*/

hashT.insert('Dick Mires', '650-589-1970').insert('Lam James', '818-589-1970').insert('Ricky Ticky Tavi', '987-589-1970');
hashT.retrieveAll();


/* NOTICE HOW HASH TABLE HAS NOW DOUBLED IN SIZE UPON REACHING 75% CAPACITY ie 6/8. It is now size 16.
 [,
  ,
  [ [ 'Vance Carter', '120-589-1970' ] ],
  [ [ 'Alex Hawkins', '510-599-1930' ],
    [ 'Dick Mires', '650-589-1970' ],
    [ 'Lam James', '818-589-1970' ] ],
  ,
  ,
  ,
  ,
  ,
  [ [ 'Boo Radley', '520-589-1970' ],
    [ 'Ricky Ticky Tavi', '987-589-1970' ] ],
  ,
  ,
  ,
  ,
  [ [ 'Biff Tanin', '987-589-1970' ] ] ]




*/
console.log(hashT.retrieve('Lam James'));  //818-589-1970
console.log(hashT.retrieve('Dick Mires')); //650-589-1970
console.log(hashT.retrieve('Ricky Ticky Tavi')); //987-589-1970
console.log(hashT.retrieve('Alex Hawkins')); //510-599-1930
console.log(hashT.retrieve('Lebron James')); //null
Alex Hawkins
fuente
3
Se ve bien. Ahora, explique también POR QUÉ esto es útil y puede ser más adecuado que todas las otras respuestas aquí.
Thomas Tempelmann
1

Puede crear uno usando lo siguiente:

var dictionary = { Name:"Some Programmer", Age:24, Job:"Writing Programs"  };

//Iterate Over using keys
for (var key in dictionary) {
  console.log("Key: " + key + " , " + "Value: "+ dictionary[key]);
}

//access a key using object notation:
console.log("Her Name is: " + dictionary.Name)

Ali Ezzat Odeh
fuente