Y a-t-il une fonction de code de hachage dans JavaScript?

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

set[obj] = true;

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

123
demandé sur Peter Mortensen 2008-10-12 03:45:37

16 réponses

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

vous pouvez, alternativement, maintenir un tableau qui indexe les objets en question, et utiliser sa chaîne d'index comme référence à l'objet. Quelque chose comme ceci:

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

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

évidemment, c'est un peu verbeux, mais vous pourriez écrire un couple de méthodes qui le gèrent et obtenir et mettre tout willy nilly.

Edit:

votre conjecture est fait -- ceci est un comportement défini dans JavaScript -- spécifiquement une conversion toString se produit, ce qui 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 de ToString sur les objets que vous voulez hacher, et qui peut former leur Identificateur de hachage.

31
répondu eyelidlessness 2014-08-09 15:09:02

si vous voulez une fonction hashCode () comme Java en JavaScript, c'est à vous:

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

C'est le mode d'implémentation en Java (opérateur bitwise).

42
répondu KimKha 2017-10-05 23:49:32

la façon la plus simple de faire ceci est de donner à chacun de vos objets sa propre méthode unique toString :

(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 d'agitation, et a été beaucoup plus facile que la ré-implémentation d'un certain style java gras Hashtable et l'ajout de equals() et hashCode() à vos classes d'objet. Assurez-vous juste que vous ne collez pas aussi une chaîne '<#MyObject:12> dans votre hachage ou il effacera l'entrée pour votre sortie de l'objet avec cette identification.

maintenant, tous mes coups sont totalement froids. Je viens également de poster une entrée de blog Il ya quelques jours sur ce sujet exact .

32
répondu Daniel X Moore 2014-08-14 01:24:18

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

Function.prototype.getHashCode = (function(id) {
    return function() {
        if (!this.hashCode) {
            this.hashCode = '<hash|#' + (id++) + '>';
        }
        return this.hashCode;
    }
}(0));
18
répondu theGecko 2013-06-19 02:35:37

ce que vous avez décrit est couvert par Harmony WeakMaps , une partie de la ECMAScript 6 spécification (prochaine version de JavaScript). C'est: un jeu où les touches peuvent être n'importe quoi (y compris indéfini) et est non-énumérable.

cela signifie qu'il est impossible d'obtenir une référence à une valeur à moins que vous ayez une référence directe à la clé (n'importe quel objet!) que des liens vers elle. C'est important pour un tas de raisons de mise en œuvre du moteur relatif à l'efficacité et la collecte des ordures, mais il est aussi super cool pour en ce qu'il permet de nouvelles sémantiques comme les permissions d'accès révocables et de passer des données sans exposer l'expéditeur 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
Les

WeakMaps sont disponibles en Firefox, Chrome et Edge. Ils sont également pris en charge dans le noeud v7 , et dans v6 avec le drapeau --harmony-weak-maps .

17
répondu slezica 2016-12-19 14:36:42

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 était de convertir l'objet en sa représentation JSON et de l'utiliser comme le hachage. Il y a des limites telles que l'ordre de la définition de clé potentiellement incohérente; mais comme je l'ai dit, cela a fonctionné pour moi parce que ces objets étaient tous générés en un seul 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
// }
10
répondu ijmacd 2014-03-11 16:30:17

la spécification JavaScript définit l'accès à une propriété indexée comme effectuant une conversion toString sur le nom d'index. Par exemple,

myObject[myProperty] = ...;

est le même que

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

cela est nécessaire comme dans JavaScript

myObject["someProperty"]

est le même que

myObject.someProperty

et oui, cela me rend triste aussi bien: - (

8
répondu olliej 2014-08-09 12:34:32

j'ai assemblé un petit module JavaScript il y a quelque temps pour produire des hashcodes pour chaînes, objets, tableaux, etc. (J'ai juste commis GitHub :) )

Utilisation:

Hashcode.value("stackoverflow")
// -2559914341
Hashcode.value({ 'site' : "stackoverflow" })
// -3579752159
8
répondu Metalstorm 2014-08-09 15:34:27

dans ECMAScript 6 Il y a maintenant un Set qui fonctionne comme vous voulez: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

il est déjà disponible dans les derniers Chrome, FF, et IE11.

6
répondu Daniel X Moore 2015-01-13 19:48:40

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

vous pouvez utiliser le symbole Es6 pour créer la clé unique et l'objet d'accès. Chaque valeur de symbole renvoyée de Symbol() est unique. Une valeur de symbole peut être utilisée comme Identificateur pour les propriétés de l'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';
3
répondu Khalid Azam 2017-01-29 20:22:32

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

(function() {
    var lastStorageId = 0;

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

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

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

je pense que c'est plus pratique avec D'autres fonctions de manipulation D'objets en JavaScript.

1
répondu Johnny 2013-06-19 02:32:54

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;
}
1
répondu Timothy Perez 2017-04-06 03:41:22

si vous voulez vraiment un comportement défini (je vais par connaissance Java), alors vous aurez du mal à trouver une solution en JavaScript. La plupart des développeurs recommanderont une clé unique pour représenter chaque objet, mais c'est différent de set, en ce que vous pouvez obtenir deux objets identiques chacun avec une clé unique. L'API Java effectue le travail de vérification des valeurs dupliquées en comparant les valeurs du code de hachage, pas les clés, et puisqu'il n'y a pas de représentation de la valeur du code de hachage des objets dans JavaScript, il devient presque impossible de faire de même. Même Le Prototype de la bibliothèque JS admet cette lacune, quand il dit:

"Hash peut être considéré comme un tableau associatif, liaison de clés uniques de valeurs (qui ne sont pas nécessairement unique.).."

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

0
répondu 2008-10-12 01:49:29

en plus de la réponse de eyelidlessness, voici une fonction qui renvoie un ID unique reproductible 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 voir, il utilise une liste de recherche qui est très inefficace, mais c'est le mieux que j'ai pu trouver pour le moment.

0
répondu cburgmer 2012-07-11 20:29:32

si vous voulez utiliser des objets comme clés, vous devez écraser leur méthode de toString, comme certains l'ont déjà mentionné ici. Les fonctions de hachage qui ont été utilisées sont toutes bien, mais elles ne fonctionnent que pour les mêmes objets pas pour des objets égaux.

j'ai écrit une petite bibliothèque qui crée des hachures à partir d'objets, que vous pouvez facilement utiliser à cette fin. Les objets peuvent même avoir un ordre différent, les hachures seront les mêmes. En interne, vous pouvez utiliser différents types pour votre hachage (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 paquet peut être utilisé dans le navigateur et dans Node-Js.

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

0
répondu darthmatch 2013-01-22 22:35:59

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;

Array

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'

c'est similaire à la solution @ijmacd seulement getHashCode n'a pas la dépendance JSON .

0
répondu A1rPun 2016-10-22 13:04:58