¿Hay algún tipo de función de código hash en JavaScript?

Básicamente, estoy tratando de crear un objeto de objetos únicos, un conjunto. Tuve la brillante idea de usar un objeto JavaScript con objetos para los nombres de propiedad. Como,

set[obj] = true;

Esto funciona, hasta cierto punto. Funciona muy bien con cadenas y números, pero con otros objetos, todos parecen "hash" al mismo valor y acceden a la misma propiedad. ¿Hay algún tipo de forma en que pueda generar un valor hash único para un objeto? ¿Cómo lo hacen las cadenas y los números? ¿Puedo anular el mismo comportamiento?

Los objetos de JavaScript solo pueden usar cadenas como claves (cualquier otra cosa se convierte en una cadena).

Alternativamente, podría mantener una matriz que indexe los objetos en cuestión y usar su cadena de índice como referencia al objeto. Algo como esto:

var ObjectReference = [];
ObjectReference.push(obj);

set['ObjectReference.' + ObjectReference.indexOf(obj)] = true;

Obviamente es un poco detallado, pero podría escribir un par de métodos que lo manejen y obtengan y configuren todo lo contrario.

Editar:

Su suposición es un hecho: este es un comportamiento definido en JavaScript, específicamente se produce una conversión toString, lo que significa que puede definir su propia función toString en el objeto que se utilizará como nombre de propiedad. - olliej

Esto trae a colación otro punto interesante; puede definir un método toString en los objetos que desea hash, y eso puede formar su identificador hash.

Si desea una función hashCode () como Java en JavaScript, es suya:

String.prototype.hashCode = function(){
    var hash = 0;
    for (var i = 0; i < this.length; i++) {
        var character = this.charCodeAt(i);
        hash = ((hash<<5)-hash)+character;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

Esa es la forma de implementación en Java (operador bit a bit).

Tenga en cuenta que hashCode podría ser positivo y negativo, y eso es normal, vea HashCode dando valores negativos . Por lo tanto, podría considerar usar Math.abs()junto con esta función.

La forma más fácil de hacer esto es dar a cada uno de sus objetos su propio toStringmétodo único :

(function() {
    var id = 0;

    /*global MyObject */
    MyObject = function() {
        this.objectId = '<#MyObject:' + (id++) + '>';
        this.toString= function() {
            return this.objectId;
        };
    };
})();

Tuve el mismo problema y esto lo resolvió perfectamente para mí con un mínimo de alboroto, y fue mucho más fácil que volver a implementar algún estilo graso de Java Hashtabley agregar equals()y hashCode()a sus clases de objetos. Solo asegúrese de no pegar una cadena '<#MyObject: 12> en su hash o borrará la entrada de su objeto saliente con esa identificación.

Ahora todos mis hash son totalmente fríos. También publiqué una entrada de blog hace unos días sobre este tema exacto .

Lo que describió está cubierto por Harmony WeakMaps , parte de la especificación ECMAScript 6 (próxima versión de JavaScript). Es decir: un conjunto donde las claves pueden ser cualquier cosa (incluso indefinidas) y no es enumerable.

Esto significa que es imposible obtener una referencia a un valor a menos que tenga una referencia directa a la clave (¡cualquier objeto!) Que lo vincule. Es importante por muchas razones de implementación del motor relacionadas con la eficiencia y la recolección de basura, pero también es genial porque permite nuevas semánticas como permisos de acceso revocables y pasar datos sin exponer al remitente de datos.

De MDN :

var wm1 = new WeakMap(),
    wm2 = 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').

wm1.has(o1);   // True
wm1.delete(o1);
wm1.has(o1);   // False

WeakMaps están disponibles en Firefox, Chrome y Edge actuales. También son compatibles con Node v7, y en v6 con la --harmony-weak-mapsbandera.

La solución que elegí es similar a la de Daniel, pero en lugar de usar una fábrica de objetos y anular toString, agrego explícitamente el hash al objeto cuando se solicita por primera vez a través de una función getHashCode. Un poco desordenado, pero mejor para mis necesidades :)

Function.prototype.getHashCode = (function(id) {
    return function() {
        if (!this.hashCode) {
            this.hashCode = '<hash|#' + (id++) + '>';
        }
        return this.hashCode;
    }
}(0));

Para mi situación específica, solo me importa la igualdad del objeto en lo que respecta a las claves y los valores primitivos. La solución que funcionó para mí fue convertir el objeto a su representación JSON y usarlo como hash. Existen limitaciones, como el orden de definición de clave que posiblemente sea inconsistente; pero como dije, funcionó para mí porque todos estos objetos se generaban en un solo lugar.

var hashtable = {};

var myObject = {a:0,b:1,c:2};

var hash = JSON.stringify(myObject);
// '{"a":0,"b":1,"c":2}'

hashtable[hash] = myObject;
// {
//   '{"a":0,"b":1,"c":2}': myObject
// }

Creé un pequeño módulo de JavaScript hace un tiempo para producir códigos hash para cadenas, objetos, matrices, etc. (lo acabo de enviar a GitHub :))

Uso:

Hashcode.value("stackoverflow")
// -2559914341
Hashcode.value({ 'site' : "stackoverflow" })
// -3579752159

La especificación de JavaScript define el acceso a la propiedad indexada como realizar una conversión toString en el nombre del índice. Por ejemplo,

myObject[myProperty] = ...;

es lo mismo que

myObject[myProperty.toString()] = ...;

Esto es necesario como en JavaScript

myObject["someProperty"]

es lo mismo que

myObject.someProperty

Y sí, me pone triste también :-(

En ECMAScript 6 ahora hay una Setque funciona como le gustaría: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

Ya está disponible en los últimos Chrome, FF e IE11.

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

puede usar el símbolo Es6 para crear una clave única y un objeto de acceso. Cada valor de símbolo devuelto por Symbol () es único. Se puede usar un valor de símbolo como identificador para las propiedades del objeto; Este es el único propósito del tipo de datos.

var obj = {};

obj[Symbol('a')] = 'a';
obj[Symbol.for('b')] = 'b';
obj['c'] = 'c';
obj.d = 'd';

Aquí está mi solución simple que devuelve un número entero único.

function hashcode(obj) {
    var hc = 0;
    var chars = JSON.stringify(obj).replace(/\{|\"|\}|\:|,/g, '');
    var len = chars.length;
    for (var i = 0; i < len; i++) {
        // Bump 7 to larger prime number to increase uniqueness
        hc += (chars.charCodeAt(i) * 7);
    }
    return hc;
}

Según el título, podemos generar hashes fuertes con js, se puede usar para generar un hash único a partir de un objeto, una matriz de parámetros, una cadena o lo que sea.

Más adelante para indexar esto, evite posibles errores de coincidencia, mientras permite recuperar un índice de los parámetros (evite buscar / recorrer el objeto, etc.):

async function H(m) {
  const msgUint8 = new TextEncoder().encode(m)                       
  const hashBuffer = await crypto.subtle.digest('SHA-256', msgUint8)          
  const hashArray = Array.from(new Uint8Array(hashBuffer))                    
  const hashHex = hashArray.map(b => b.toString(16).padStart(2, '0')).join('')
  console.log(hashHex)
}

/* Examples ----------------------- */
H("An obscure ....")
H(JSON.stringify( {"hello" : "world"} ))
H(JSON.stringify( [54,51,54,47] ))

El resultado anterior en mi navegador, también debería ser igual para usted ( ¿es realmente? ):

bf1cf3fe6975fe382ab392ec1dd42009380614be03d489f23601c11413cfca2b
93a23971a914e5eacbf0a8d25154cda309c3c1c72fbb9914d47c60f3cb681588
d2f209e194045604a3b15bdfd7502898a0e848e4603c5a818bd01da69c00ad19

https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/digest#Converting_a_digest_to_a_hex_string

Mi solución introduce una función estática para el Objectobjeto global .

(function() {
    var lastStorageId = 0;

    this.Object.hash = function(object) {
        var hash = object.__id;

        if (!hash)
             hash = object.__id = lastStorageId++;

        return '#' + hash;
    };
}());

Creo que esto es más conveniente con otras funciones de manipulación de objetos en JavaScript.

Intentaré ir un poco más profundo que otras respuestas.

Incluso si JS tuviera un mejor soporte de hash, no lo haría mágicamente todo perfectamente, en muchos casos tendrá que definir su propia función de hash. Por ejemplo, Java tiene un buen soporte de hashing, pero aún tiene que pensar y hacer algo de trabajo.

Un problema es con el término hash / hashcode ... hay hashing criptográfico y hash no criptográfico. El otro problema es que debes entender por qué el hashing es útil y cómo funciona.

Cuando hablamos de hashing en JavaScript o Java, la mayoría de las veces hablamos de hash no criptográfico, generalmente de hashmap para hashmap / hashtable (a menos que estemos trabajando en autenticación o contraseñas, lo que podrías estar haciendo en el lado del servidor usando NodeJS. ..).

Depende de los datos que tenga y de lo que quiera lograr.

Sus datos tienen alguna singularidad natural "simple":

• El hash de un entero es ... el entero, ya que es único, ¡qué suerte!
• El hash de una cadena ... depende de la cadena, si la cadena representa un identificador único, puede considerarlo como un hash (por lo que no se necesita hashing).
• Cualquier cosa que sea indirectamente un entero único es el caso más simple.
• Esto respetará: hashcode igual si los objetos son iguales

Sus datos tienen una singularidad natural "compuesta":

• Por ejemplo, con un objeto persona, puede calcular un hash usando el nombre, el apellido, la fecha de nacimiento, ... vea cómo lo hace Java: buena función de hash para cadenas , o use otra información de identificación que sea lo suficientemente barata y única para su caso de uso

No tienes idea de cuáles serán tus datos:

• Buena suerte ... podría serializar en cadena y mezclarlo al estilo Java, pero eso puede ser costoso si la cadena es grande y no evitará colisiones, además de decir el algoritmo hash de un entero (self).

No existe una técnica de hash mágicamente eficiente para datos desconocidos, en algunos casos es bastante fácil, en otros casos puede que tenga que pensar dos veces. Entonces, incluso si JavaScript / ECMAScript agrega más soporte, no hay una solución mágica para este problema.

En la práctica, necesitas dos cosas: suficiente singularidad, suficiente velocidad

Además de eso, es genial tener: "hashcode igual si los objetos son iguales"

• https://en.wikipedia.org/wiki/Hash_table#Collision_resolution
• Relación entre hashCode y método igual en Java

Si realmente desea establecer un comportamiento (me refiero al conocimiento de Java), tendrá dificultades para encontrar una solución en JavaScript. La mayoría de los desarrolladores recomendarán una clave única para representar cada objeto, pero esto es diferente al conjunto, ya que puede obtener dos objetos idénticos, cada uno con una clave única. La API de Java hace el trabajo de verificar valores duplicados al comparar valores de código hash, no claves, y dado que no hay representación de valores de código hash de objetos en JavaScript, se hace casi imposible hacer lo mismo. Incluso la biblioteca Prototype JS admite esta deficiencia, cuando dice:

"Hash se puede considerar como una matriz asociativa, que vincula claves únicas a valores (que no son necesariamente únicos) ..."

http://www.prototypejs.org/api/hash

Además de la respuesta de la falta de párpados, aquí hay una función que devuelve una identificación única y reproducible para cualquier objeto:

var uniqueIdList = [];
function getConstantUniqueIdFor(element) {
    // HACK, using a list results in O(n), but how do we hash e.g. a DOM node?
    if (uniqueIdList.indexOf(element) < 0) {
        uniqueIdList.push(element);
    }
    return uniqueIdList.indexOf(element);
}

Como puede ver, utiliza una lista de búsqueda que es muy ineficiente, sin embargo, eso es lo mejor que pude encontrar por ahora.

Si desea utilizar objetos como claves, debe sobrescribir su Método toString, como algunos ya se mencionaron aquí. Las funciones hash que se utilizaron están bien, pero solo funcionan para los mismos objetos, no para objetos iguales.

He escrito una pequeña biblioteca que crea hashes a partir de objetos, que puede usar fácilmente para este propósito. Los objetos pueden incluso tener un orden diferente, los hash serán los mismos. Internamente puede usar diferentes tipos para su hash (djb2, md5, sha1, sha256, sha512, ripemd160).

Aquí hay un pequeño ejemplo de la documentación:

var hash = require('es-hash');

// Save data in an object with an object as a key
Object.prototype.toString = function () {
    return '[object Object #'+hash(this)+']';
}

var foo = {};

foo[{bar: 'foo'}] = 'foo';

/*
 * Output:
 *  foo
 *  undefined
 */
console.log(foo[{bar: 'foo'}]);
console.log(foo[{}]);

El paquete se puede usar en el navegador y en Node-Js.

Repositorio: https://bitbucket.org/tehrengruber/es-js-hash

Si desea tener valores únicos en un objeto de búsqueda, puede hacer algo como esto:

Crear un objeto de búsqueda

var lookup = {};

Configurar la función de código hash

function getHashCode(obj) {
    var hashCode = '';
    if (typeof obj !== 'object')
        return hashCode + obj;
    for (var prop in obj) // No hasOwnProperty needed
        hashCode += prop + getHashCode(obj[prop]); // Add key + value to the result string
    return hashCode;
}

Objeto

var key = getHashCode({ 1: 3, 3: 7 });
// key = '1337'
lookup[key] = true;

Formación

var key = getHashCode([1, 3, 3, 7]);
// key = '01132337'
lookup[key] = true;

Otros tipos

var key = getHashCode('StackOverflow');
// key = 'StackOverflow'
lookup[key] = true;

Resultado final

{ 1337: true, 01132337: true, StackOverflow: true }

Tenga en cuenta que getHashCodeno devuelve ningún valor cuando el objeto o la matriz está vacía

getHashCode([{},{},{}]);
// '012'
getHashCode([[],[],[]]);
// '012'

Esto es similar a la solución @ijmacd solo getHashCodeque no tiene la JSONdependencia.

Combiné las respuestas de los párpados y KimKha.

El siguiente es un servicio angularjs y admite números, cadenas y objetos.

exports.Hash = () => {
  let hashFunc;
  function stringHash(string, noType) {
    let hashString = string;
    if (!noType) {
      hashString = `string${string}`;
    }
    var hash = 0;
    for (var i = 0; i < hashString.length; i++) {
        var character = hashString.charCodeAt(i);
        hash = ((hash<<5)-hash)+character;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
  }

  function objectHash(obj, exclude) {
    if (exclude.indexOf(obj) > -1) {
      return undefined;
    }
    let hash = '';
    const keys = Object.keys(obj).sort();
    for (let index = 0; index < keys.length; index += 1) {
      const key = keys[index];
      const keyHash = hashFunc(key);
      const attrHash = hashFunc(obj[key], exclude);
      exclude.push(obj[key]);
      hash += stringHash(`object${keyHash}${attrHash}`, true);
    }
    return stringHash(hash, true);
  }

  function Hash(unkType, exclude) {
    let ex = exclude;
    if (ex === undefined) {
      ex = [];
    }
    if (!isNaN(unkType) && typeof unkType !== 'string') {
      return unkType;
    }
    switch (typeof unkType) {
      case 'object':
        return objectHash(unkType, ex);
      default:
        return stringHash(String(unkType));
    }
  }

  hashFunc = Hash;

  return Hash;
};

Ejemplo de uso:

Hash('hello world'), Hash('hello world') == Hash('hello world')
Hash({hello: 'hello world'}), Hash({hello: 'hello world'}) == Hash({hello: 'hello world'})
Hash({hello: 'hello world', goodbye: 'adios amigos'}), Hash({hello: 'hello world', goodbye: 'adios amigos'}) == Hash({goodbye: 'adios amigos', hello: 'hello world'})
Hash(['hello world']), Hash(['hello world']) == Hash(['hello world'])
Hash(1), Hash(1) == Hash(1)
Hash('1'), Hash('1') == Hash('1')

Salida

432700947 true
-411117486 true
1725787021 true
-1585332251 true
1 true
-1881759168 true

Explicación

Como puede ver, el corazón del servicio es la función hash creada por KimKha. He agregado tipos a las cadenas para que la estructura del objeto también afecte el valor hash final. Las claves se combinan para evitar colisiones de matriz | objeto.

La comparación de objetos sin párpados se utiliza para evitar una recursión infinita mediante objetos de autorreferencia.

Uso

Creé este servicio para poder tener un servicio de error al que se accede con objetos. Para que un servicio pueda registrar un error con un objeto determinado y otro pueda determinar si se encontraron errores.

es decir

JsonValidation.js

ErrorSvc({id: 1, json: '{attr: "not-valid"}'}, 'Invalid Json Syntax - key not double quoted');

UserOfData.js

ErrorSvc({id: 1, json: '{attr: "not-valid"}'});

Esto devolvería:

['Invalid Json Syntax - key not double quoted']

Mientras

ErrorSvc({id: 1, json: '{"attr": "not-valid"}'});

Esto volvería

[]

Simplemente use propiedad secreta oculta con el defineProperty enumerable: false

Funciona muy rápido :

• La primera lectura única ID: 1.257.500 operaciones / s
• Todos los demás: 309,226,485 ops / s

var nextObjectId = 1
function getNextObjectId() {
    return nextObjectId++
}

var UNIQUE_ID_PROPERTY_NAME = '458d576952bc489ab45e98ac7f296fd9'
function getObjectUniqueId(object) {
    if (object == null) {
        return null
    }

    var id = object[UNIQUE_ID_PROPERTY_NAME]

    if (id != null) {
        return id
    }

    if (Object.isFrozen(object)) {
        return null
    }

    var uniqueId = getNextObjectId()
    Object.defineProperty(object, UNIQUE_ID_PROPERTY_NAME, {
        enumerable: false,
        configurable: false,
        writable: false,
        value: uniqueId,
    })

    return uniqueId
}