Wygeneruj skrót z ciągu w JavaScript

585

Muszę przekonwertować ciągi znaków na jakąś formę skrótu. Czy jest to możliwe w JavaScript?

Nie używam języka po stronie serwera, więc nie mogę tego zrobić w ten sposób.

Freesnöw
źródło
7
MD5 nie jest bezpieczny, więc nie szukaj go.
henrikstroem
166
@henrikstroem Zależy od tego, co hashed; nie ma nic złego w używaniu md5 do utworzenia skrótu do celów innych niż bezpieczeństwo.
Brad Koch
7
@BradKoch Zależy od tego, co robisz; nie ma nic złego w korzystaniu z md5 do celów bezpieczeństwa. Z pewnością istnieją lepsze metody mieszania haseł, ale md5 jest w porządku do robienia rzeczy takich jak podpisywanie adresu URL.
Paul Ferrett,
81
Zabawne jest to, że podczas gdy MD5 jest krytykowany w komentarzach tutaj, prawie wszystkie odpowiedzi zalecają znacznie gorsze algorytmy mieszające i uzyskują wiele pozytywnych opinii.
domen
38
Użycie MD5 do sprawdzenia, czy pobieranie zostało nienaruszone, w magiczny sposób nie wyśle ​​haseł pocztą elektroniczną do wszystkich współpracowników.
James M. Lay

Odpowiedzi:

787
Object.defineProperty(String.prototype, 'hashCode', {
  value: function() {
    var hash = 0, i, chr;
    for (i = 0; i < this.length; i++) {
      chr   = this.charCodeAt(i);
      hash  = ((hash << 5) - hash) + chr;
      hash |= 0; // Convert to 32bit integer
    }
    return hash;
  }
});

Źródło: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/

esmiralha
źródło
22
To jest to samo, co używane w Javie. To hash << 5 - hashjest to samo, hash * 31 + charale dużo DUŻO. Fajnie, bo jest tak szybki, a 31 to mała liczba pierwsza. Wygraj tam, wygraj.
corsiKa
41
Zrobiłem kilka testów na jsperf ( jsperf.com/hashing-strings ) i funkcja bitowa jest w rzeczywistości wolniejsza niż funkcja oparta na liczbach .
skerit
17
@PeterAronZentai Dlaczego jest to „bezużyteczne”? Dane wyjściowe wygenerowane przez kod oparty na liczbach (hash * 31) + charsą identyczne z danymi wyjściowymi wygenerowanymi przez kod oparty na przesunięciu ((hash<<5)-hash)+char, nawet dla bardzo długich ciągów (przetestowałem to z ciągami zawierającymi ponad milion znaków), więc nie jest to „bezużyteczne” pod względem dokładności. Złożoność wynosi O (n) zarówno dla wersji opartych na liczbach, jak i wersji z przesunięciem, więc nie jest „bezużyteczna” pod względem złożoności.
TachyonVortex,
13
Czy ktoś może komentować unikalność (lub nie) wyniku? W szczególności, jeśli używam tego skrótu tylko dla ciągów o długości mniejszej niż n, to jaki jest największy, ndla którego nie mogę mieć kolizji?
Don McCurdy
34
Czy jest jakiś powód, dla którego to (lub powinno) być na prototypie String? Czy byłoby mniej efektywne / wydajne mieć np.; var hashCode = function hashCode (str) {etc...}? A następnie użyć jako hashCode("mystring")?
grzechotka
146

EDYTOWAĆ

na podstawie moich testów jsperf, zaakceptowana odpowiedź jest w rzeczywistości szybsza: http://jsperf.com/hashcodelordvlad

ORYGINALNY

jeśli ktoś jest zainteresowany, oto ulepszona (szybsza) wersja, która zawiedzie w starszych przeglądarkach, które nie mają reducefunkcji tablicowej.

hashCode = function(s){
  return s.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);              
}

wersja z funkcją strzałki w jednym wierszu:

hashCode = s => s.split('').reduce((a,b)=>{a=((a<<5)-a)+b.charCodeAt(0);return a&a},0)
Lordvlad
źródło
3
czy istnieje sposób na uzyskanie skrótu, który jest tylko liczbą dodatnią?
Prosto Trader
45
dziwne. właśnie go przetestowałem i okazało się, że jest o wiele wolniejszy niż zaakceptowana odpowiedź. jsperf.com/hashcodelordvlad
lordvlad
112
Dobry facet @lordvlad, faktycznie testuje swoją odpowiedź, a następnie zgłasza, kiedy jest wolniejsza.
mikemaccana
9
Właśnie zdałem sobie sprawę: to ma sens, że zaakceptowana odpowiedź jest szybsza, ponieważ moja wersja musi najpierw przekształcić ciąg w tablicę, przydzielając nową pamięć i kopiując każdą postać ...
lordvlad
5
[] .reduce.call (str, (p, c, i, a) => (p << 5) - p + a.charCodeAt (i), 0);
Dizzy
108

Uwaga: nawet przy najlepszym 32-bitowym skrócie kolizje będą występować prędzej czy później.

Prawdopodobieństwo zderzenia skrótu można obliczyć jako 1 - e ^ (-k (k-1) / 2Nprzybliżone jako k ^ 2 / 2N ( patrz tutaj ). Może to być więcej niż sugeruje intuicja: przy
założeniu, że 32-bitowy skrót i k = 10 000 elementów, nastąpi kolizja z prawdopodobieństwem 1,2%. Dla 77 163 próbek prawdopodobieństwo wynosi 50%! ( kalkulator ).
Sugeruję obejście na dole.

W odpowiedzi na to pytanie Który algorytm mieszania jest najlepszy dla wyjątkowości i szybkości? Ian Boyd opublikował dobrą dogłębną analizę . Krótko mówiąc (jak to interpretuję), dochodzi do wniosku, że Murmur jest najlepszy, a następnie FNV-1a.
Algorytm String.hashCode () Javy zaproponowany przez esmiralha wydaje się być wariantem DJB2.

  • FNV-1a ma lepszą dystrybucję niż DJB2, ale jest wolniejszy
  • DJB2 jest szybszy niż FNV-1a, ale zwykle powoduje więcej kolizji
  • MurmurHash3 jest lepszy i szybszy niż DJB2 i FNV-1a (ale zoptymalizowana implementacja wymaga więcej wierszy kodu niż FNV i DJB2)

Niektóre testy porównawcze z dużymi ciągami wejściowymi tutaj: http://jsperf.com/32-bit-hash
Po skróceniu krótkich ciągów wejściowych wydajność szmeru spada, w porównaniu do DJ2B i FNV-1a: http://jsperf.com/32- bit-hash / 3

Ogólnie więc polecam murmur3.
Zobacz tutaj implementację JavaScript: https://github.com/garycourt/murmurhash-js

Jeśli ciągi wejściowe są krótkie, a wydajność jest ważniejsza niż jakość dystrybucji, użyj DJB2 (zgodnie z propozycją przyjętą przez esmiralha).

Jeśli jakość i mały rozmiar kodu są ważniejsze niż szybkość, używam tej implementacji FNV-1a (na podstawie tego kodu ).

/**
 * Calculate a 32 bit FNV-1a hash
 * Found here: https://gist.github.com/vaiorabbit/5657561
 * Ref.: http://isthe.com/chongo/tech/comp/fnv/
 *
 * @param {string} str the input value
 * @param {boolean} [asString=false] set to true to return the hash value as 
 *     8-digit hex string instead of an integer
 * @param {integer} [seed] optionally pass the hash of the previous chunk
 * @returns {integer | string}
 */
function hashFnv32a(str, asString, seed) {
    /*jshint bitwise:false */
    var i, l,
        hval = (seed === undefined) ? 0x811c9dc5 : seed;

    for (i = 0, l = str.length; i < l; i++) {
        hval ^= str.charCodeAt(i);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }
    if( asString ){
        // Convert to 8 digit hex string
        return ("0000000" + (hval >>> 0).toString(16)).substr(-8);
    }
    return hval >>> 0;
}

Popraw prawdopodobieństwo kolizji

Jak wyjaśniono tutaj , możemy zwiększyć rozmiar bitu skrótu za pomocą tej sztuczki:

function hash64(str) {
    var h1 = hash32(str);  // returns 32 bit (as 8 byte hex string)
    return h1 + hash32(h1 + str);  // 64 bit (as 16 byte hex string)
}

Używaj go ostrożnie i nie oczekuj jednak zbyt wiele.

mar10
źródło
Dlaczego to robisz ("0000000" + (hval >>> 0).toString(16)).substr(-8);? Czy to nie to samo co (hval >>> 0).toString(16)?
Manuel Meurer
3
dodaje to wiodące „0”, dzięki czemu wynikowy skrót zawsze ma 8 znaków. Łatwiej jest je odczytać i rozpoznać w wynikach, ale taka jest moja osobista opinia
marca
Ach ok, rozumiem. Za mały hval, (hval >>> 0).toString(16)może być mniejsza niż 8 znaków, więc pad to zerami. Byłem po prostu zdezorientowany, ponieważ (hval >>> 0).toString(16)zawsze skutkowało to ciągiem dokładnie 8 znaków.
Manuel Meurer
3
Uwielbiam tę odpowiedź, ponieważ tworzy ona znacznie lepiej rozproszony skrót: inne zaproponowane tutaj funkcje spowodują konsekwentne wartości skrótu. Np. `Hash („ example1 ”) - hash („ example2 ”) == 1”, podczas gdy ten jest znacznie bardziej nieprzewidywalny.
GavinoGrifoni
1
W odpowiedzi na „FNV-1a ma lepszą dystrybucję niż DJB2, ale jest wolniejszy” - myślę, że należy powiedzieć, że FNV1a może być niezwykle szybki, gdy jest implementowany za pomocą Math.imulfunkcji ES6 . Już samo to czyni go najlepszymi wzorcami, a ostatecznie lepszym wyborem na dłuższą metę niż DJB2.
bryc,
64

Na podstawie zaakceptowanej odpowiedzi w ES6. Mniejszy, łatwy w utrzymaniu i działa w nowoczesnych przeglądarkach.

function hashCode(str) {
  return str.split('').reduce((prevHash, currVal) =>
    (((prevHash << 5) - prevHash) + currVal.charCodeAt(0))|0, 0);
}

// Test
console.log("hashCode(\"Hello!\"): ", hashCode('Hello!'));

EDYCJA (04.11.2019) :

wersja z funkcją strzałki w jednym wierszu:

const hashCode = s => s.split('').reduce((a,b) => (((a << 5) - a) + b.charCodeAt(0))|0, 0)

// test
console.log(hashCode('Hello!'))

deekshith
źródło
1
Dziękuję za udostępnienie, które dodałem str += ""przed mieszaniem, aby uniknąć wyjątku str.split is not a function
zgłaszanego,
4
Ale znacznie, znacznie wolniej niż którykolwiek z nich: https://jsperf.com/hashing-strings
AndyO
Zauważyłem też, że najszybsze „retro” rozwiązanie jest tak naprawdę mniejsze, jeśli usuniesz źródła linii, tak że mają tylko 3 linie.
AndyO
2
W jakikolwiek sposób, aby przyniosło to tylko pozytywne, ale wciąż wyjątkowe wyniki?
Dids
3
@deekshith Zaakceptowana odpowiedź służy hash |= 0do konwersji na 32-bitową liczbę int. Ta implementacja nie. Czy to błąd?
Sukima
48

Prawie połowa odpowiedzi to implementacje Javy String.hashCode, które nie są ani wysokiej jakości, ani superszybkie. Nie jest to nic specjalnego, po prostu mnożą się przez 31 dla każdej postaci. Można go wdrożyć w prosty i wydajny sposób w jednej linii i jest znacznie szybszy dzięki Math.imul:

hashCode=s=>{for(var i=0,h;i<s.length;i++)h=Math.imul(31,h)+s.charCodeAt(i)|0;return h}

Poza tym jest coś lepszego - cyrb53 , prosty, ale wysokiej jakości 53-bitowy skrót. Jest dość szybki, zapewnia bardzo dobrą dystrybucję skrótu i ​​ma znacznie niższe współczynniki kolizji w porównaniu do dowolnego skrótu 32-bitowego.

const cyrb53 = function(str, seed = 0) {
    let h1 = 0xdeadbeef ^ seed, h2 = 0x41c6ce57 ^ seed;
    for (let i = 0, ch; i < str.length; i++) {
        ch = str.charCodeAt(i);
        h1 = Math.imul(h1 ^ ch, 2654435761);
        h2 = Math.imul(h2 ^ ch, 1597334677);
    }
    h1 = Math.imul(h1 ^ h1>>>16, 2246822507) ^ Math.imul(h2 ^ h2>>>13, 3266489909);
    h2 = Math.imul(h2 ^ h2>>>16, 2246822507) ^ Math.imul(h1 ^ h1>>>13, 3266489909);
    return 4294967296 * (2097151 & h2) + (h1>>>0);
};

Podobnie jak w dobrze znanych algorytmach MurmurHash / xxHash, wykorzystuje kombinację mnożenia i Xorshift do generowania skrótu, ale nie jest tak dokładny. W rezultacie jest szybszy niż w JavaScript i znacznie łatwiejszy do wdrożenia.

Osiąga lawinę (nie ścisłą), co w zasadzie oznacza, że ​​małe zmiany na wejściu mają duże zmiany na wyjściu, dzięki czemu powstały skrót jest losowy:

0xc2ba782c97901 = cyrb53("a")
0xeda5bc254d2bf = cyrb53("b")
0xe64cc3b748385 = cyrb53("revenge")
0xd85148d13f93a = cyrb53("revenue")

Możesz także podać źródło dla alternatywnych strumieni tego samego wejścia:

0xee5e6598ccd5c = cyrb53("revenue", 1)
0x72e2831253862 = cyrb53("revenue", 2)
0x0de31708e6ab7 = cyrb53("revenue", 3)

Technicznie jest to 64-bitowy skrót (dwa nieskorelowane 32-bitowe skróty równolegle), ale JavaScript jest ograniczony do 53-bitowych liczb całkowitych. W razie potrzeby można nadal korzystać z pełnego 64-bitowego wyjścia, zmieniając wiersz zwrotny dla łańcucha szesnastkowego lub tablicy.

Należy pamiętać, że tworzenie ciągów szesnastkowych może drastycznie spowolnić przetwarzanie wsadowe w sytuacjach krytycznych pod względem wydajności.

return (h2>>>0).toString(16).padStart(8,0)+(h1>>>0).toString(16).padStart(8,0);
// or
return [h2>>>0, h1>>>0];

I dla zabawy, oto minimalny 32-bitowy skrót w 89 znakach o wyższej jakości niż nawet FNV lub DJB2:

TSH=s=>{for(var i=0,h=9;i<s.length;)h=Math.imul(h^s.charCodeAt(i++),9**9);return h^h>>>9}
bryc
źródło
4
Wow, jest to o wiele lepsze niż zwykle * 31 dla krótkich (lub podobnych) danych wejściowych. :)
lapo
2
Gdzie jest chinicjowany?
hellowill89
3
@ hellowill89 woops, zapomniałem to ogłosić i wykrwawiłem się na globalny zasięg. naprawione teraz, dzięki: ')
bryc
Niepowodzenie dla IE 11: Obiekt nie obsługuje właściwości ani metody 'imul'.
BachT
2
@BachT Możesz użyć podkładki wypełniającej lub pełnej podkładki ES6 . Ale IE11 jest tragicznie zamrożony w 2009 roku bez aktualizacji.
bryc
28

Jeśli to komukolwiek pomaga, połączyłem dwie pierwsze odpowiedzi w starszą wersję odporną na przeglądarkę, która używa szybkiej wersji, jeśli reducejest dostępna, i wraca do rozwiązania esmiralha, jeśli nie jest.

/**
 * @see http://stackoverflow.com/q/7616461/940217
 * @return {number}
 */
String.prototype.hashCode = function(){
    if (Array.prototype.reduce){
        return this.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);              
    } 
    var hash = 0;
    if (this.length === 0) return hash;
    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;
}

Użycie jest jak:

var hash = "some string to be hashed".hashCode();
Kyle Falconer
źródło
jak zoptymalizować ten kod, aby działał szybciej w każdej przeglądarce. String.prototype.hashCode = function(){ var hash = 5381; if (this.length === 0) return hash; for (var i = 0; i < this.length; i++) { var character = this.charCodeAt(i); hash = ((hash<<5)+hash)^character; // Convert to 32bit integer } return hash; }
Musakkhir Sayyed
26

To jest wyrafinowany i lepiej działający wariant:

String.prototype.hashCode = function() {
    var hash = 0, i = 0, len = this.length;
    while ( i < len ) {
        hash  = ((hash << 5) - hash + this.charCodeAt(i++)) << 0;
    }
    return hash;
};

Jest to zgodne z implementacją standardu przez Javę object.hashCode()

Oto także taki, który zwraca tylko pozytywne kody skrótu:

String.prototype.hashcode = function() {
    return (this.hashCode() + 2147483647) + 1;
};

A oto pasujący do Java, który zwraca tylko pozytywne kody skrótu:

public static long hashcode(Object obj) {
    return ((long) obj.hashCode()) + Integer.MAX_VALUE + 1l;
}

Cieszyć się!

mmm
źródło
2
świetna odpowiedź, ale jaki jest cel << 0?
koolaang
8
@koolaang to operator lewego gówna, developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
mmm
29
@momomo Czy chodziło Ci o przesunięcie w lewo ?
wdh
2
@momomo Myślę, że pytał, dlaczego to przesunięcie w lewo zerowych bitów.
jpfx1342
3
@Maykonn (2 ^
32-1
24

Jestem trochę zaskoczony, że nikt jeszcze nie mówił o nowym API SubtleCrypto .

Aby uzyskać skrót z ciągu, możesz użyć subtle.digestmetody:

function getHash(str, algo = "SHA-256") {
  let strBuf = new TextEncoder('utf-8').encode(str);
  return crypto.subtle.digest(algo, strBuf)
    .then(hash => {
      window.hash = hash;
      // here hash is an arrayBuffer, 
      // so we'll connvert it to its hex version
      let result = '';
      const view = new DataView(hash);
      for (let i = 0; i < hash.byteLength; i += 4) {
        result += ('00000000' + view.getUint32(i).toString(16)).slice(-8);
      }
      return result;
    });
}

getHash('hello world')
  .then(hash => {
    console.log(hash);
  });

Kaiido
źródło
4
Zgadzam się. Konwersji na hex można dokonać trochę inaczej ...var promise = crypto.subtle.digest({name: "SHA-256"}, Uint8Array.from(data)); promise.then(function(result){ console.log(Array.prototype.map.call(new Uint8Array(result), x => x.toString(16).padStart(2, '0')).join('')); });
Denis Giffeler
3
Kryptograficzna funkcja skrótu dla łańcuchów jest nieco przesadzona .. cryptonie jest dokładnie wydajna.
bryc
Wiarygodna jakość losowa bez konieczności polegania na osobach przeprowadzających testy, wbudowana (nie wymaga niestandardowej implementacji), wysiewalna, a do wygenerowania mapy gry potrzebowałem tylko kilkuset liczb, wydawało się to idealne. Ale okazuje się, że absolutnie nie ma sposobu, aby to zrobić synchronicznie. Konieczność zapewnienia asynchronicznego wywołania zwrotnego za każdym razem, gdy wywołujesz rozstawiony przypadkowy silnik, sprawia, że ​​kod jest bardzo nieczytelny i wygląda śmiesznie. Nie wiem, kto wymyślił ten gówniany interfejs crypto.subtle, więc w końcu musiałem skorzystać z xmur3 + sfc32 z tej odpowiedzi: stackoverflow.com/a/47593316/1201863
Luc
7

Dzięki przykładowi autorstwa mar10 znalazłem sposób na uzyskanie takich samych wyników w C # ORAZ Javascript dla FNV-1a. Jeśli występują znaki Unicode, górna część jest odrzucana ze względu na wydajność. Nie wiem, dlaczego warto utrzymywać je podczas mieszania, ponieważ na razie mam tylko ścieżki adresów URL.

Wersja C #

private static readonly UInt32 FNV_OFFSET_32 = 0x811c9dc5;   // 2166136261
private static readonly UInt32 FNV_PRIME_32 = 0x1000193;     // 16777619

// Unsigned 32bit integer FNV-1a
public static UInt32 HashFnv32u(this string s)
{
    // byte[] arr = Encoding.UTF8.GetBytes(s);      // 8 bit expanded unicode array
    char[] arr = s.ToCharArray();                   // 16 bit unicode is native .net 

    UInt32 hash = FNV_OFFSET_32;
    for (var i = 0; i < s.Length; i++)
    {
        // Strips unicode bits, only the lower 8 bits of the values are used
        hash = hash ^ unchecked((byte)(arr[i] & 0xFF));
        hash = hash * FNV_PRIME_32;
    }
    return hash;
}

// Signed hash for storing in SQL Server
public static Int32 HashFnv32s(this string s)
{
    return unchecked((int)s.HashFnv32u());
}

Wersja JavaScript

var utils = utils || {};

utils.FNV_OFFSET_32 = 0x811c9dc5;

utils.hashFnv32a = function (input) {
    var hval = utils.FNV_OFFSET_32;

    // Strips unicode bits, only the lower 8 bits of the values are used
    for (var i = 0; i < input.length; i++) {
        hval = hval ^ (input.charCodeAt(i) & 0xFF);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }

    return hval >>> 0;
}

utils.toHex = function (val) {
    return ("0000000" + (val >>> 0).toString(16)).substr(-8);
}
djabraham
źródło
@mathiasrw Możliwe jest, że znaki Unicode przekraczają 8 bitów w pamięci, więc zakładam, że 0xFF po prostu maskuje wszystko poza tym zakresem. Zobacz więcej o charCodeAt () tutaj: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
djabraham
Jeśli ES6 jest dostępny (obsługują go wszystkie nowoczesne silniki), Math.imulmożna go użyć do pomnożenia, co znacznie poprawia wydajność . Jedynym problemem jest to, że nie będzie działać w IE11 bez podkładki .
bryc 10.01.19
6

Szybki i zwięzły, który został dostosowany stąd :

String.prototype.hashCode = function() {
  var hash = 5381, i = this.length
  while(i)
    hash = (hash * 33) ^ this.charCodeAt(--i)
  return hash >>> 0;
}
soulmachine
źródło
5

Potrzebowałem podobnej (ale innej) funkcji do wygenerowania unikalnego identyfikatora na podstawie nazwy użytkownika i aktualnego czasu. Więc:

window.newId = ->
  # create a number based on the username
  unless window.userNumber?
    window.userNumber = 0
  for c,i in window.MyNamespace.userName
    char = window.MyNamespace.userName.charCodeAt(i)
    window.MyNamespace.userNumber+=char
  ((window.MyNamespace.userNumber + Math.floor(Math.random() * 1e15) + new Date().getMilliseconds()).toString(36)).toUpperCase()

Produkuje:

2DVFXJGEKL
6IZPAKFQFL
ORGOENVMG
... etc 

edytuj czerwiec 2015: Do nowego kodu używam shortid: https://www.npmjs.com/package/shortid

jcollum
źródło
2
@ t0r0X no teraz używam modułu o nazwie shortid: npmjs.com/package/shortid
jcollum
1
Jak używasz nazwy użytkownika ze skrótem? Wydaje się, że generuje identyfikatory, ale nie rozumiem, w jaki sposób generujesz skrót z łańcucha
cyberwombat
1
Ta odpowiedź ma 3 głosy negatywne. Dla mojego życia nie mogę sobie wyobrazić, dlaczego. Nikt nic nie powiedział ...: - /
jcollum
1
@jcollum, dlatego prawie nigdy nie odpowiadam na nieaktualne pytania .. uderzenia i biegi pozostają niezauważone. nawet po ustaleniu odpowiedzi nikt nie przychodzi, by ją zrównoważyć.
bryc
5

Moja szybka (bardzo długa) jedna wkładka oparta na Multiply+Xormetodzie FNV :

my_string.split('').map(v=>v.charCodeAt(0)).reduce((a,v)=>a+((a<<7)+(a<<3))^v).toString(16);
John Smith
źródło
5

SubtleCrypto.digest

Nie używam języka po stronie serwera, więc nie mogę tego zrobić w ten sposób.

Czy na pewno nie możesz tego zrobić w ten sposób ?

Czy zapomniałeś, że używasz Javascript, języka ciągle ewoluującego?

Spróbować SubtleCrypto. Obsługuje funkcje skrótu SHA-1, SHA-128, SHA-256 i SHA-512.


async function hash(message/*: string */) {
	const text_encoder = new TextEncoder;
	const data = text_encoder.encode(message);
	const message_digest = await window.crypto.subtle.digest("SHA-512", data);
	return message_digest;
} // -> ArrayBuffer

function in_hex(data/*: ArrayBuffer */) {
	const octets = new Uint8Array(data);
	const hex = [].map.call(octets, octet => octet.toString(16).padStart(2, "0")).join("");
	return hex;
} // -> string

(async function demo() {
	console.log(in_hex(await hash("Thanks for the magic.")));
})();

Константин Ван
źródło
Czym różni się to od odpowiedzi Kaiido sprzed dwóch lat ?
Luc
@Luc Nie jest, najwyraźniej.
Константин Ван
3

Jestem trochę spóźniony na imprezę, ale możesz użyć tego modułu: crypto :

const crypto = require('crypto');

const SALT = '$ome$alt';

function generateHash(pass) {
  return crypto.createHmac('sha256', SALT)
    .update(pass)
    .digest('hex');
}

Wynikiem tej funkcji jest zawsze 64ciąg znaków; coś takiego:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"

Ariel Jiménez
źródło
2

Połączyłem oba rozwiązania (użytkownicy esmiralha i lordvlad), aby uzyskać funkcję, która powinna być szybsza w przeglądarkach obsługujących funkcję js redukuj () i nadal kompatybilnych ze starymi przeglądarkami:

String.prototype.hashCode = function() {

    if (Array.prototype.reduce) {
        return this.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);   
    } else {

        var hash = 0, i, chr, len;
        if (this.length == 0) return hash;
        for (i = 0, len = this.length; i < len; i++) {
        chr   = this.charCodeAt(i);
        hash  = ((hash << 5) - hash) + chr;
        hash |= 0; // Convert to 32bit integer
        }
        return hash;
    }
};

Przykład:

my_string = 'xyz';
my_string.hashCode();
Szczery
źródło
2

Jeśli chcesz uniknąć kolizji, możesz użyć bezpiecznego skrótu, takiego jak SHA-256 . Istnieje kilka implementacji JavaScript SHA-256.

Napisałem testy, aby porównać kilka implementacji skrótu, patrz https://github.com/brillout/test-javascript-hash-implementations .

Lub przejdź do http://brillout.github.io/test-javascript-hash-implementations/ , aby uruchomić testy.

brillout
źródło
1
Korzystanie z bezpiecznego skrótu kryptograficznego może być bardzo powolne. Unikanie kolizji jest wynikiem szerokości bitu, a nie bezpieczeństwa. 128-bitowy niekryptograficzny skrót, a nawet 64-bitowy powinien być wystarczający do większości celów. MurmurHash3_x86_128 jest dość szybki i ma bardzo małą szansę kolizji.
bryc
2

Powinien to być nieco bezpieczniejszy skrót niż niektóre inne odpowiedzi, ale w funkcji, bez żadnego wstępnie załadowanego źródła

Stworzyłem w zasadzie zminimalizowaną uproszczoną wersję sha1.
Bierzesz bajty ciągu i grupujesz je według 4 do 32-bitowych „słów”.
Następnie rozszerzamy każde 8 słów do 40 słów (dla większego wpływu na wynik).
To odnosi się do funkcji skrótu (ostatnie zmniejszenie), gdzie robimy matematykę z bieżącym stanem i danymi wejściowymi. Zawsze dostajemy 4 słowa.
Jest to prawie jedna wersja z jednym poleceniem / jedna linia, korzystająca z mapowania, zmniejszania ... zamiast pętli, ale wciąż jest dość szybka

String.prototype.hash = function(){
    var rot = (word, shift) => word << shift | word >>> (32 - shift);
    return unescape(encodeURIComponent(this.valueOf())).split("").map(char =>
            char.charCodeAt(0)
        ).reduce((done, byte, idx, arr) =>
            idx % 4 == 0 ? [...done, arr.slice(idx, idx + 4)] : done
        , []).reduce((done, group) =>
            [...done, group[0] << 24 | group[1] << 16 | group[2] << 8 | group[3]]
        , []).reduce((done, word, idx, arr) =>
            idx % 8 == 0 ? [...done, arr.slice(idx, idx + 8)] : done
        , []).map(group => {
            while(group.length < 40)
                group.push(rot(group[group.length - 2] ^ group[group.length - 5] ^ group[group.length - 8], 3));
            return group;
        }).flat().reduce((state, word, idx, arr) => {
            var temp = ((state[0] + rot(state[1], 5) + word + idx + state[3]) & 0xffffffff) ^ state[idx % 2 == 0 ? 4 : 5](state[0], state[1], state[2]);
            state[0] = rot(state[1] ^ state[2], 11);
            state[1] = ~state[2] ^ rot(~state[3], 19);
            state[2] = rot(~state[3], 11);
            state[3] = temp;
            return state;
        }, [0xbd173622, 0x96d8975c, 0x3a6d1a23, 0xe5843775,
            (w1, w2, w3) => (w1 & rot(w2, 5)) | (~rot(w1, 11) & w3),
            (w1, w2, w3) => w1 ^ rot(w2, 5) ^ rot(w3, 11)]
        ).slice(0, 4).map(p =>
            p >>> 0
        ).map(word =>
            ("0000000" + word.toString(16)).slice(-8)
        ).join("");
};

konwertujemy również dane wyjściowe na hex, aby uzyskać ciąg zamiast tablicy słów.
Użycie jest proste. na przykład "a string".hash()wróci"88a09e8f9cc6f8c71c4497fbb36f84cd"

Franartur Čech
źródło
1

Poszedłem do prostej konkatenacji kodów char przekonwertowanych na ciągi szesnastkowe. Służy to względnie wąskiemu celowi, a mianowicie potrzebie wymiany skrótu w postaci ciągu KRÓTKIEGO (np. Tytułów, znaczników) do wymiany po stronie serwera, który z nieistotnych powodów nie może łatwo wdrożyć zaakceptowanego portu Java hashCode. Oczywiście nie ma tutaj aplikacji zabezpieczającej.

String.prototype.hash = function() {
  var self = this, range = Array(this.length);
  for(var i = 0; i < this.length; i++) {
    range[i] = i;
  }
  return Array.prototype.map.call(range, function(i) {
    return self.charCodeAt(i).toString(16);
  }).join('');
}

Dzięki Underscore można to uczynić bardziej zwięzłym i bardziej tolerancyjnym dla przeglądarki. Przykład:

"Lorem Ipsum".hash()
"4c6f72656d20497073756d"

Podejrzewam, że jeśli chcesz mieszać większe ciągi w podobny sposób, możesz po prostu zmniejszyć kody znaków i heksyfikować wynikową sumę, zamiast łączyć poszczególne znaki razem:

String.prototype.hashLarge = function() {
  var self = this, range = Array(this.length);
  for(var i = 0; i < this.length; i++) {
    range[i] = i;
  }
  return Array.prototype.reduce.call(range, function(sum, i) {
    return sum + self.charCodeAt(i);
  }, 0).toString(16);
}

'One time, I hired a monkey to take notes for me in class. I would just sit back with my mind completely blank while the monkey scribbled on little pieces of paper. At the end of the week, the teacher said, "Class, I want you to write a paper using your notes." So I wrote a paper that said, "Hello! My name is Bingo! I like to climb on things! Can I have a banana? Eek, eek!" I got an F. When I told my mom about it, she said, "I told you, never trust a monkey!"'.hashLarge()
"9ce7"

Naturalnie większe ryzyko kolizji z tą metodą, choć możesz manipulować arytmetyką w redukcji, jednak chciałeś urozmaicić i wydłużyć skrót.

swornabsent
źródło
1

Nieco uproszczona wersja odpowiedzi @ esmiralha.

W tej wersji nie zastępuję ciągu znaków, ponieważ może to spowodować niepożądane zachowanie.

function hashCode(str) {
    var hash = 0;
    for (var i = 0; i < str.length; i++) {
        hash = ~~(((hash << 5) - hash) + str.charCodeAt(i));
    }
    return hash;
}
crazy2be
źródło
1

Dodanie tego, ponieważ nikt jeszcze tego nie zrobił, i wydaje się, że o to proszono i zaimplementowano wiele z hashami, ale zawsze robi się to bardzo źle ...

To wymaga wprowadzenia ciągu znaków i maksymalnej liczby, która ma być równa wartości skrótu, i tworzy unikalną liczbę na podstawie wejścia ciągu.

Możesz użyć tego do stworzenia unikalnego indeksu w tablicy obrazów (jeśli chcesz zwrócić określony awatar dla użytkownika, wybrany losowo, ale także wybrany na podstawie jego nazwiska, więc zawsze będzie przypisany do osoby o tej nazwie ).

Możesz również użyć tego, oczywiście, aby zwrócić indeks do tablicy kolorów, na przykład do generowania unikalnych kolorów tła awatara na podstawie czyjegoś imienia.

function hashInt (str, max = 1000) {
    var hash = 0;
    for (var i = 0; i < str.length; i++) {
      hash = ((hash << 5) - hash) + str.charCodeAt(i);
      hash = hash & hash;
    }
    return Math.round(max * Math.abs(hash) / 2147483648);
}
Nick Steele
źródło
-1

Nie widzę powodu, aby używać tego skomplikowanego kodu kryptograficznego zamiast gotowych rozwiązań, takich jak biblioteka skrótów obiektowych itp. Poleganie na dostawcy jest bardziej wydajne, oszczędza czas i zmniejsza koszty utrzymania.

Wystarczy użyć https://github.com/puleos/object-hash

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

hash({foo: 'bar'}) // => '67b69634f9880a282c14a0f0cb7ba20cf5d677e9'
hash([1, 2, 2.718, 3.14159]) // => '136b9b88375971dff9f1af09d7356e3e04281951'
Oleg Abrazhaev
źródło
Kod źródłowy tej biblioteki jest nawet nieczytelny. Tylko 50 000 zminimalizowanego kodu.
bryc
1
@bryc tak powinien wyglądać kod dostawcy :), a źródła można sprawdzić na github.com/puleos/object-hash/blob/master/index.js
Oleg Abrazhaev
Zminimalizowany kod to 35,4 KB, a pełne źródło to 14,2 KB? To nie ma sensu.
bryc
2
@bryc Czy rozważałeś tę linię? var crypto = require('crypto');. Myślę, że dodaje ten kod zależności od dostawcy w wersji zminimalizowanej podczas kompilacji.
Oleg Abrazhaev
Jeśli naprawdę potrzebujesz haszować obiekty, napisałem any-serialize, aby serializować KAŻDY obiekt za pomocą kluczy sortowania, a następnie cyrb53, aby wygenerować hash bazy36.
Polv