Existe-t-il une fonction de code de hachage en JavaScript?

Question

En gros, j'essaie de créer un objet d'objets uniques, un ensemble. J'ai eu la brillante idée d'utiliser simplement un objet JavaScript avec des objets pour les noms de propriété. Tels que,

set[obj] = true;

Cela fonctionne, jusqu'à un certain point. Cela fonctionne très bien avec une chaîne et des nombres, mais avec d'autres objets, ils semblent tous & "Hash &"; à la même valeur et accéder à la même propriété. Existe-t-il un moyen de générer une valeur de hachage unique pour un objet? Comment les chaînes et les chiffres font-ils, puis-je remplacer le même comportement?

Answer 1

Les objets JavaScript ne peuvent utiliser que des chaînes en tant que clés (tout le reste est converti en chaîne).

Vous pouvez également gérer un tableau qui indexe les objets en question et utiliser sa chaîne d'index comme référence à l'objet. Quelque chose comme ça:

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

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

Évidemment, c'est un peu prolixe, mais vous pouvez écrire quelques méthodes pour le gérer et obtenir et définir tous les paramètres voulus.

Modifier:

  

Votre hypothèse est la réalité - il s'agit d'un comportement défini dans JavaScript - en particulier, une conversion toString signifie que vous pouvez définir votre propre fonction toString sur l'objet qui sera utilisé comme nom de propriété. - olliej

Cela soulève un autre point intéressant. vous pouvez définir une méthode toString sur les objets que vous souhaitez hacher, et qui peuvent former leur identifiant de hachage.

Answer 2

Si vous voulez une fonction hashCode () comme celle de Java en JavaScript, elle vous appartient:

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

Telle est la méthode d'implémentation en Java (opérateur au niveau du bit).

Answer 3

Pour ce faire, le plus simple consiste à attribuer à chaque objet sa propre et unique toString méthode:

.

(function() {
    var id = 0;

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

J'ai eu le même problème et cela l'a résolu parfaitement pour moi avec un minimum de tracas, et était beaucoup plus facile que de réimplémenter un style Java gras Hashtable et d'ajouter equals() et hashCode() à vos classes d'objet. Assurez-vous simplement de ne pas coller une chaîne '& Lt; #MyObject: 12 & Gt; dans votre hash ou il effacera l'entrée de votre objet sortant avec cet identifiant.

Maintenant, tous mes hash sont totalement froids. Je viens également de publier une entrée de blog il y a quelques jours à propos de ce sujet précis .

Answer 4

La solution que j'ai choisie est similaire à celle de Daniel, mais plutôt que d'utiliser une fabrique d'objets et de remplacer le toString, j'ajoute explicitement le hachage à l'objet lorsqu'il est demandé pour la première fois via une fonction getHashCode. Un peu brouillon, mais mieux pour mes besoins:)

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

Answer 5

Ce que vous avez décrit est couvert par WeakMaps , une partie du Spécification ECMAScript & nbsp; 6 (prochaine version de JavaScript). C’est-à-dire: un ensemble où les clés peuvent être n'importe quoi (y compris les éléments non définis) et sont non énumérables.

Cela signifie qu'il est impossible d'obtenir une référence à une valeur sans une référence directe à la clé (tout objet!) qui la relie. C’est important pour de nombreuses raisons d’implémentation de moteur liées à l’efficacité et à la récupération de place, mais aussi parce qu’il permet de nouvelles sémantiques telles que les autorisations d’accès révocables et la transmission de données sans exposer l’émetteur de données.

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 sont disponibles dans les versions actuelles de Firefox, Chrome et Edge. Ils sont également pris en charge dans Node v7 et dans la v6 avec l'indicateur --harmony-weak-maps.

Answer 6

Pour ma situation spécifique, je ne me soucie que de l'égalité de l'objet en ce qui concerne les clés et les valeurs primitives. La solution qui a fonctionné pour moi consistait à convertir l'objet en sa représentation JSON et à l'utiliser comme hachage. Il existe des limitations telles que l'ordre de définition des clés peut être incohérent; mais comme je l'ai dit, cela a fonctionné pour moi car ces objets étaient tous générés à un endroit.

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

Answer 7

La spécification JavaScript définit l'accès aux propriétés indexées comme une conversion toString sur le nom de l'index. Par exemple,

myObject[myProperty] = ...;

est identique à

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

Ceci est nécessaire comme en JavaScript

myObject["someProperty"]

est identique à

myObject.someProperty

Et oui, cela me rend triste aussi: - (

Answer 8

J’ai mis en place un petit module JavaScript pour produire des codes de hachage pour les chaînes, les objets, les tableaux, etc. l'a engagé à GitHub :))

Utilisation:

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

Answer 9

Dans ECMAScript 6, un Set qui fonctionne comme vous le souhaitez: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

Il est déjà disponible dans les dernières versions de Chrome, FF et IE11.

Answer 10

Référence: https: //developer.mozilla .org / en-US / docs / Web / JavaScript / Référence / Global_Objects / Symbol

vous pouvez utiliser le symbole Es6 pour créer une clé unique et un objet d'accès.     Chaque valeur de symbole renvoyée par Symbol () est unique. Une valeur de symbole peut être utilisée comme identifiant pour les propriétés d'objet; c'est le seul but du type de données.

var obj = {};

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

Answer 11

Voici ma solution simple qui renvoie un entier unique.

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

Answer 12

Ma solution introduit une fonction statique pour l'objet Object global.

(function() {
    var lastStorageId = 0;

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

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

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

Je pense que cela est plus pratique avec d'autres fonctions de manipulation d'objets en JavaScript.

Answer 13

Si vous voulez vraiment définir le comportement (je pars de la connaissance de Java), vous aurez du mal à trouver une solution en JavaScript. La plupart des développeurs recommandent une clé unique pour représenter chaque objet, mais il s'agit d'un ensemble différent, en ce sens que vous pouvez obtenir deux objets identiques ayant chacun une clé unique. L'API Java vérifie les doublons en comparant les valeurs de code de hachage et non les clés. En l'absence de représentation des valeurs de code de hachage en JavaScript, il est presque impossible de faire de même. Même la bibliothèque Prototype JS admet cette lacune quand elle dit:

  

& "; Hash peut être considéré comme un   tableau associatif, reliant des clés uniques   aux valeurs (qui ne sont pas nécessairement   unique) ... & ";

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

Answer 14

En plus de la réponse de eyelidlessness, voici une fonction qui renvoie un identifiant reproductible et unique pour tout objet:

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);
}

Comme vous pouvez le constater, il utilise une liste de recherche très inefficace, mais c'est le meilleur que j'ai pu trouver pour l'instant.

Answer 15

Si vous souhaitez utiliser des objets en tant que clés, vous devez écraser leur méthode toString, comme cela a déjà été mentionné ici. Les fonctions de hachage utilisées sont correctes, mais elles ne fonctionnent que pour les mêmes objets, pas pour les mêmes objets.

J'ai écrit une petite bibliothèque qui crée des hachages à partir d'objets, que vous pouvez facilement utiliser à cette fin. Les objets peuvent même avoir un ordre différent, les hachages seront les mêmes. En interne, vous pouvez utiliser différents types pour votre hash (djb2, md5, sha1, sha256, sha512, ripemd160).

Voici un petit exemple tiré de la documentation:

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[{}]);

Le package peut être utilisé dans le navigateur et dans Node-Js.

Dépôt: https://bitbucket.org/tehrengruber/es-js-hash

Answer 16

Si vous voulez avoir des valeurs uniques dans un objet de recherche, vous pouvez faire quelque chose comme ceci:

Création d'un objet de recherche

var lookup = {};

Configuration de la fonction hashcode

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

Objet

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

Tableau

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

Autres types

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

Résultat final

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

Notez que getHashCode ne renvoie aucune valeur lorsque l'objet ou le tableau est vide

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

Ceci est similaire à la solution @ijmacd, mais seul JSON n'a pas la dépendance <=>.

Answer 17

Je vais essayer d'aller un peu plus loin que les autres réponses.

Même si JS avait un meilleur support de hachage, il ne serait pas tout à fait magique comme par magie. Dans de nombreux cas, vous devrez définir votre propre fonction de hachage. Par exemple, Java supporte bien le hachage, mais vous devez encore réfléchir et travailler.

Un problème concerne le terme hash / hashcode ... il existe un hachage cryptographique et un hachage non cryptographique. L’autre problème est que vous devez comprendre pourquoi le hachage est utile et comment il fonctionne.

Lorsque nous parlons de hachage en JavaScript ou en Java, nous parlons la plupart du temps de hachage non cryptographique, généralement de hachage pour hashmap / hashtable (sauf si nous travaillons sur l'authentification ou les mots de passe, ce que vous pourriez faire côté serveur en utilisant NodeJS ...).

Cela dépend des données que vous possédez et de ce que vous voulez atteindre.

Vos données contiennent des éléments & naturels; simples & "; unicité:

• Le hachage d'un entier est ... l'entier, car il est unique, chanceux!
• Le hachage d'une chaîne ... cela dépend de la chaîne. Si la chaîne représente un identificateur unique, vous pouvez le considérer comme un hachage (aucun hachage n'est donc nécessaire).
• Tout ce qui est indirectement à peu près un entier unique est le cas le plus simple
• Ceci respectera: hashcode égal si les objets sont égaux

Vos données ont des & naturels "composites &" naturels; unicité:

• Par exemple, avec un objet personne, vous pouvez calculer un hachage en utilisant prénom, nom, date de naissance, ... voyez comment Java le fait: Bonne fonction de hachage pour les chaînes , ou utilisez une autre information d'identification suffisamment économique et unique pour votre cas d'utilisation

Vous n'avez aucune idée de ce que seront vos données:

• Bonne chance ... vous pouvez sérialiser en chaîne et le hacher en style Java, mais cela peut coûter cher si la chaîne est grande et évitera les collisions ainsi que le hachage d'un entier (self).

Il n’existe pas de technique de hachage efficace comme par magie pour les données inconnues. Dans certains cas, cela est assez facile, dans d’autres, vous devrez peut-être réfléchir à deux fois. Donc, même si JavaScript / ECMAScript ajoute davantage de support, il n’existe pas de solution magique pour ce problème.

En pratique, vous avez besoin de deux choses: suffisamment d'unicité et de rapidité

En outre, il est bon d’avoir: & "; hashcode égal si les objets sont égaux &";

• https://en.wikipedia.org/wiki/Hash_table#Collision_resolution
• Relation entre hashCode et la méthode equals en Java

Answer 18

J'ai combiné les réponses de eyelidlessness et de KimKha.

Ce qui suit est un service angularjs qui prend en charge les nombres, les chaînes et les objets.

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

Exemple d'utilisation:

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

Sortie

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

Explication

Comme vous pouvez le voir, le cœur du service est la fonction de hachage créée par KimKha.J'ai ajouté des types aux chaînes afin que la structure de l'objet ait également un impact sur la valeur de hachage finale. Les clés sont hachées pour empêcher tableau | collisions d'objets.

la comparaison d’objets eyelidlessness est utilisée pour empêcher la récursion infinit par les objets auto-référencés.

Utilisation

J'ai créé ce service afin d'avoir un service d'erreur auquel on accède avec des objets. Ainsi, un service peut enregistrer une erreur avec un objet donné et un autre peut déterminer si des erreurs ont été trouvées.

c'est-à-dire

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"}'});

Ceci renverrait:

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

Alors que

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

Ceci renverrait

[]