Czy w JavaScript jest jakaś funkcja kodu skrótu?

Zasadniczo próbuję stworzyć obiekt z unikatowych obiektów, zbiór. Wpadłem na genialny pomysł, aby po prostu użyć obiektu JavaScript z obiektami jako nazwami właściwości. Jak na przykład,

set[obj] = true;

To działa do pewnego momentu. Działa świetnie z ciągami i liczbami, ale w przypadku innych obiektów wszystkie wydają się „mieszać” do tej samej wartości i mają dostęp do tej samej właściwości. Czy istnieje sposób, w jaki mogę wygenerować unikalną wartość skrótu dla obiektu? Jak to robią ciągi i liczby, czy mogę zmienić to samo zachowanie?

Obiekty JavaScript mogą używać tylko łańcuchów jako kluczy (wszystko inne jest konwertowane na łańcuch).

Możesz, alternatywnie, utrzymywać tablicę, która indeksuje dane obiekty i używać jej ciągu indeksowego jako odniesienia do obiektu. Coś takiego:

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

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

Oczywiście jest to trochę rozwlekłe, ale możesz napisać kilka metod, które sobie z tym poradzą i uzyskać i ustawić wszystko, co chcesz.

Edytować:

Twoje przypuszczenie jest faktem - jest to zachowanie zdefiniowane w JavaScript - w szczególności zachodzi konwersja toString, co oznacza, że ​​możesz zdefiniować własną funkcję toString na obiekcie, który będzie używany jako nazwa właściwości. - olliej

To prowadzi do kolejnego interesującego punktu; możesz zdefiniować metodę toString na obiektach, które chcesz haszować, i która może utworzyć ich identyfikator skrótu.

Jeśli potrzebujesz funkcji hashCode (), takiej jak Java w JavaScript, to jest twoja:

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

Taki jest sposób implementacji w Javie (operator bitowy).

Zwróć uwagę, że hashCode może być dodatni i ujemny, i to normalne, zobacz HashCode podający wartości ujemne . Możesz więc rozważyć użycie Math.abs()razem z tą funkcją.

Najłatwiej to zrobić, nadając każdemu obiektowi własną unikalną toStringmetodę:

(function() {
    var id = 0;

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

Miałem ten sam problem i to rozwiązało go doskonale dla mnie przy minimalnym zamieszaniu i było o wiele łatwiejsze niż ponowne zaimplementowanie jakiegoś tłustego stylu Java Hashtablei dodanie equals()i hashCode()do klas obiektów. Po prostu upewnij się, że nie wklejasz również ciągu znaków '<#MyObject: 12> do swojego hasha, bo spowoduje to wyczyszczenie wpisu dla wychodzącego obiektu o tym identyfikatorze.

Teraz wszystkie moje skróty są całkowicie wyluzowane. Kilka dni temu właśnie zamieściłem na blogu wpis na ten temat .

To, co opisałeś, jest objęte Harmony WeakMaps , część specyfikacji ECMAScript 6 (kolejna wersja JavaScript). To znaczy: zestaw, w którym klucze mogą być dowolne (w tym niezdefiniowane) i nie są wyliczalne.

Oznacza to, że niemożliwe jest uzyskanie odniesienia do wartości, jeśli nie masz bezpośredniego odniesienia do klucza (dowolnego obiektu!), Który jest z nią powiązany. Jest to ważne z wielu powodów związanych z implementacją silnika związanych z wydajnością i usuwaniem elementów bezużytecznych, ale jest również super fajne, ponieważ pozwala na nową semantykę, taką jak odwoływalne uprawnienia dostępu i przekazywanie danych bez ujawniania nadawcy danych.

Z 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 są dostępne w aktualnych przeglądarkach Firefox, Chrome i Edge. Są również obsługiwane w Node v7 i v6 z --harmony-weak-mapsflagą.

Rozwiązanie, które wybrałem, jest podobne do rozwiązania Daniela, ale zamiast używać fabryki obiektów i przesłonić toString, jawnie dodaję hash do obiektu, gdy jest on po raz pierwszy żądany przez funkcję getHashCode. Trochę niechlujnie, ale lepiej na moje potrzeby :)

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

W mojej konkretnej sytuacji zależy mi tylko na równości obiektu, jeśli chodzi o klucze i prymitywne wartości. Rozwiązaniem, które zadziałało, było przekonwertowanie obiektu na jego reprezentację JSON i użycie tego jako skrótu. Istnieją ograniczenia, takie jak kolejność definicji kluczy, która może być niespójna; ale jak powiedziałem, to zadziałało, ponieważ wszystkie te obiekty były generowane w jednym miejscu.

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

Stworzyłam małą JavaScript moduł jakiś czas temu do hashcodes produkować dla strun, obiektów, tablic itp (I właśnie popełnił go do GitHub :))

Stosowanie:

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

Specyfikacja JavaScript definiuje dostęp do indeksowanej właściwości jako wykonanie konwersji toString na nazwie indeksu. Na przykład,

myObject[myProperty] = ...;

jest taki sam jak

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

Jest to konieczne, podobnie jak w JavaScript

myObject["someProperty"]

jest taki sam jak

myObject.someProperty

I tak, też mnie to smuci :-(

W ECMAScript 6 jest teraz opcja, Setktóra działa tak, jak chcesz: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

Jest już dostępny w najnowszej wersji Chrome, FF i IE11.

Źródła: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Symbol

możesz użyć symbolu Es6, aby stworzyć unikalny klucz i obiekt dostępu. Każda wartość symbolu zwrócona przez Symbol () jest unikalna. Wartość symbolu może służyć jako identyfikator właściwości obiektu; jest to jedyny cel tego typu danych.

var obj = {};

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

Oto moje proste rozwiązanie, które zwraca unikalną liczbę całkowitą.

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

Na podstawie tytułu możemy wygenerować silne hashe za pomocą js, można go użyć do wygenerowania unikalnego skrótu z obiektu, tablicy parametrów, ciągu lub cokolwiek innego.

Później do indeksowania pozwala to uniknąć ewentualnych błędów dopasowania, jednocześnie umożliwiając pobranie indeksu z parametrów (unikaj wyszukiwania / zapętlania obiektu itp.):

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

Powyższe wyjście w mojej przeglądarce powinno być dla Ciebie równe ( czy to naprawdę? ):

bf1cf3fe6975fe382ab392ec1dd42009380614be03d489f23601c11413cfca2b
93a23971a914e5eacbf0a8d25154cda309c3c1c72fbb9914d47c60f3cb681588
d2f209e194045604a3b15bdfd7502898a0e848e4603c5a818bd01da69c00ad19

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

Moje rozwiązanie wprowadza statyczną funkcję dla Objectobiektu globalnego .

(function() {
    var lastStorageId = 0;

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

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

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

Myślę, że jest to wygodniejsze w przypadku innych funkcji manipulowania obiektami w JavaScript.

Spróbuję pójść trochę głębiej niż inne odpowiedzi.

Nawet gdyby JS miał lepszą obsługę haszowania, nie magicznie haszowałby wszystkiego idealnie, w wielu przypadkach będziesz musiał zdefiniować własną funkcję haszującą. Na przykład Java ma dobrą obsługę mieszania, ale nadal musisz pomyśleć i trochę popracować.

Jeden problem dotyczy terminu hash / hashcode ... jest szyfrowanie kryptograficzne i haszowanie niekryptograficzne. Innym problemem jest to, że musisz zrozumieć, dlaczego haszowanie jest przydatne i jak działa.

Kiedy mówimy o haszowaniu w JavaScript lub Javie, przez większość czasu mówimy o haszowaniu niekryptograficznym, zwykle o haszowaniu dla haszowania / tablicy haszującej (chyba że pracujemy nad uwierzytelnianiem lub hasłami, które możesz wykonywać po stronie serwera za pomocą NodeJS. ..).

To zależy od tego, jakie masz dane i co chcesz osiągnąć.

Twoje dane mają naturalną „prostą” wyjątkowość:

• Skrót liczby całkowitej to ... liczba całkowita, ponieważ jest unikalna, na szczęście!
• Skrót ciągu ... zależy od ciągu, jeśli ciąg reprezentuje unikalny identyfikator, możesz uznać go za hash (więc nie jest potrzebny hasz).
• Najprostszym przypadkiem jest wszystko, co pośrednio jest w zasadzie unikalną liczbą całkowitą
• Będzie to uwzględniać: hashcode równy, jeśli obiekty są równe

Twoje dane mają naturalną wyjątkowość „złożoną”:

• Na przykład w przypadku obiektu osoby możesz obliczyć hash, używając imienia, nazwiska, daty urodzenia, ... zobacz, jak robi to Java: Dobra funkcja skrótu dla ciągów znaków , lub użyj innych informacji identyfikacyjnych, które są tanie i wystarczająco unikalne dla twojego przypadku

Nie masz pojęcia, jakie będą Twoje dane:

• Powodzenia ... możesz serializować do łańcucha i zaszyfrować go w stylu Java, ale może to być kosztowne, jeśli ciąg jest duży i nie pozwoli uniknąć kolizji, a także powiedzieć hash liczby całkowitej (self).

Nie ma magicznie wydajnej techniki haszowania nieznanych danych, w niektórych przypadkach jest to dość łatwe, w innych może być konieczne zastanowienie się dwa razy. Więc nawet jeśli JavaScript / ECMAScript dodaje więcej wsparcia, nie ma magicznego rozwiązania tego problemu.

W praktyce potrzebujesz dwóch rzeczy: wystarczającej unikalności, wystarczającej szybkości

Poza tym świetnie jest mieć: „kod hash jest równy, jeśli obiekty są równe”

• https://en.wikipedia.org/wiki/Hash_table#Collision_resolution
• Związek między hashCode i metodą equals w Javie

Jeśli naprawdę chcesz ustawić zachowanie (idę przez znajomość języka Java), trudno będzie znaleźć rozwiązanie w JavaScript. Większość programistów zaleci unikalny klucz do reprezentowania każdego obiektu, ale jest to odmienne od zestawu, ponieważ można uzyskać dwa identyczne obiekty, każdy z unikalnym kluczem. Interfejs Java API sprawdza zduplikowane wartości, porównując wartości kodu skrótu, a nie kluczy, a ponieważ nie ma reprezentacji wartości kodu skrótu obiektów w JavaScript, wykonanie tego samego staje się prawie niemożliwe. Nawet biblioteka Prototype JS przyznaje się do tego niedociągnięcia, gdy mówi:

„Hash można traktować jako tablicę asocjacyjną, wiążącą unikalne klucze z wartościami (które niekoniecznie są unikalne)…”

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

Oprócz odpowiedzi bez powiek, oto funkcja, która zwraca powtarzalny, unikalny identyfikator dla dowolnego obiektu:

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

Jak widać, używa listy do wyszukiwania, która jest bardzo nieefektywna, jednak to najlepsze, co na razie znalazłem.

Jeśli chcesz używać obiektów jako kluczy, musisz nadpisać ich metodę toString, jak już wspomniano tutaj. Wszystkie użyte funkcje skrótu są w porządku, ale działają tylko dla tych samych obiektów, a nie dla równych obiektów.

Napisałem małą bibliotekę, która tworzy skróty z obiektów, których możesz łatwo użyć do tego celu. Obiekty mogą mieć nawet inną kolejność, skróty będą takie same. Wewnętrznie możesz użyć różnych typów dla swojego skrótu (djb2, md5, sha1, sha256, sha512, ripemd160).

Oto mały przykład z dokumentacji:

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

Pakiet może być używany zarówno w przeglądarce, jak iw Node-Js.

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

Jeśli chcesz mieć unikalne wartości w obiekcie wyszukiwania, możesz zrobić coś takiego:

Tworzenie obiektu wyszukiwania

var lookup = {};

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

Obiekt

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

Szyk

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

Inne rodzaje

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

Ostateczny wynik

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

Zwróć uwagę, że getHashCodenie zwraca żadnej wartości, gdy obiekt lub tablica jest pusta

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

Jest to podobne do rozwiązania @ijmacd, getHashCodeale nie ma JSONzależności.

Połączyłem odpowiedzi z bez powiek i KimKha.

Poniżej znajduje się usługa angularjs, która obsługuje liczby, ciągi znaków i obiekty.

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

Przykładowe zastosowanie:

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

Wynik

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

Wyjaśnienie

Jak widać, sercem usługi jest funkcja skrótu stworzona przez KimKha. Dodałem typy do łańcuchów, aby struktura obiektu również wpłynęła na ostateczną wartość skrótu. Klucze są haszowane, aby zapobiec kolizjom tablic | obiektów.

Porównywanie obiektów bez powiek służy do zapobiegania nieskończonej rekurencji przez obiekty odnoszące się do siebie.

Stosowanie

Utworzyłem tę usługę, aby mieć usługę błędów, do której można uzyskać dostęp za pomocą obiektów. Aby jedna usługa mogła zarejestrować błąd w danym obiekcie, a inna mogła określić, czy znaleziono jakieś błędy.

to znaczy

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

To zwróci:

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

Podczas

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

To wróci

[]

Po prostu użyj ukrytej tajnej właściwości z rozszerzeniem defineProperty enumerable: false

Działa bardzo szybko :

• Pierwszy odczyt uniqueId: 257 operacji / s
• Wszyscy inni: 309 226 485 operacji / 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
}