Existe-t-il une fonction de code de hachage acceptant tout type d'objet ?

Question

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

set[obj] = true;

Cela fonctionne, jusqu'à un certain point. Cela fonctionne très bien avec les chaînes et les nombres, mais avec les autres objets, ils semblent tous "hacher" 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 de caractères et les nombres le font-ils ? Puis-je modifier le même comportement ?

Answer 1

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

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

C'est la manière dont elle est mise en œuvre en Java (opérateur bit à bit).

Veuillez noter que hashCode peut être positif et négatif, et c'est normal, voir HashCode donnant des valeurs négatives . Vous pouvez donc envisager d'utiliser Math.abs() avec cette fonction.

Answer 2

Les objets JavaScript ne peuvent utiliser que des chaînes de caractères comme clés (tout autre élément est converti en chaîne de caractères).

Vous pourriez aussi 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 qui obtiennent et définissent tout ça bon gré mal gré.

Editar:

Votre supposition est exacte -- il s'agit d'un comportement défini en JavaScript -- une conversion en toString se produit spécifiquement, 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 toString sur les objets que vous voulez hacher, et cela peut constituer leur identifiant de hachage.

Answer 3

La façon la plus simple de procéder est de donner à chacun de vos objets un caractère unique. toString méthode :

(function() {
    var id = 0;

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

J'avais le même problème et cela l'a résolu parfaitement pour moi avec un minimum d'efforts, et c'était beaucoup plus facile que de réimplémenter un gros style Java. Hashtable et en ajoutant equals() y hashCode() à vos classes d'objets. Assurez-vous simplement que vous ne collez pas également une chaîne '<#MonObjet:12> dans votre hachage ou cela effacera l'entrée de votre objet sortant avec cet id.

Maintenant, tous mes hashs sont totalement froids. J'ai aussi posté un article de blog il y a quelques jours sur ce sujet exact .

Answer 4

Ce que vous avez décrit est couvert par Harmony WeakMaps qui fait partie de la ECMAScript 6 (prochaine version de JavaScript). C'est-à-dire : un ensemble dont les clés peuvent être n'importe quoi (y compris indéfini) et qui n'est pas dénombrable.

Cela signifie qu'il est impossible d'obtenir une référence à une valeur sans avoir une référence directe à la clé (n'importe quel objet !) qui y est liée. C'est important pour un tas de raisons d'implémentation du moteur liées à l'efficacité et à la collecte des déchets, mais c'est aussi super cool car cela permet une nouvelle sémantique comme les permissions d'accès révocables et le passage de données sans exposer l'expéditeur des 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 dans les versions actuelles de Firefox, Chrome et Edge. Elles sont également prises en charge dans Node v7 , et dans la v6 avec l'option "WeakMaps". --harmony-weak-maps drapeau.

Answer 5

La solution que j'ai choisie est similaire à celle de Daniel, mais plutôt que d'utiliser une fabrique d'objets et de surcharger le toString, j'ajoute explicitement le hash à l'objet lorsqu'il est demandé pour la première fois par une fonction getHashCode. C'est un peu compliqué, mais cela répond mieux à mes besoins :)

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