Generowanie Hasha z ciągu znaków w Javascript

EDIT

Na podstawie moich testów jsperf, zaakceptowana odpowiedź jest rzeczywiście szybsza: http://jsperf.com/hashcodelordvlad

Oryginalny

Jeśli ktoś jest zainteresowany, oto ulepszona (szybsza ) wersja, która zawiedzie na starszych przeglądarkach, które nie mają funkcji tablicy reduce.

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

Uwaga: nawet z najlepszym 32-bitowym Hashem, będziesz musiał poradzić sobie z faktem że kolizje nastąpią prędzej czy później. Czyli dwa różne ciągi wejściowe zwróci tę samą wartość skrótu z prawdopodobieństwem co najmniej 1: 2^32.

W odpowiedzi na to pytanie który algorytm haszujący jest najlepszy dla wyjątkowości i szybkości?, Ian Boyd opublikował dobre w dogłębnej analizie . Krótko mówiąc (Jak to interpretuję) dochodzi do wniosku, że szmery najlepiej, po którym następuje FNV-1a.
Stringi Javy.algorytm hashCode() 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 ma tendencję do generowania większej liczby kolizji.]} MurmurHash3 jest lepszy i szybszy od DJB2 i FNV-1A (ale zoptymalizowana implementacja wymaga więcej linii kodu niż FNV i DJB2)

Niektóre benchmarki z dużymi ciągami wejściowymi tutaj: http://jsperf.com/32-bit-hash
Kiedy krótkie ciągi wejściowe są haszowane, wydajność murmura spada w stosunku 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ą odpowiedź 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;
}

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

Jeśli to komuś pomoże, połączyłem dwie najlepsze odpowiedzi w starszą wersję tolerującą przeglądarkę, która używa szybkiej wersji, jeśli reduce jest 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 = new String("some string to be hashed").hashCode();

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

To pasuje do implementacji standardu Java object.hashCode()

Tutaj jest również taki, który zwraca tylko pozytywne hashcodes:

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

A tutaj jest pasujący do Javy, który zwraca tylko pozytywne hashcody:

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

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

Aby uzyskać hash z ciągu znaków, możesz użyć subtle.digest "metoda": {]}

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

Dzięki przykładowi mar10, znalazłem sposób, aby uzyskać takie same wyniki w C# i Javascript dla FNV-1a. jeśli znaki unicode są obecne, górna część jest odrzucana ze względu na wydajność. Nie wiem, dlaczego warto je zachować podczas haszowania, ponieważ na razie tylko haszowanie ścieżek 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);
}

Potrzebowałem podobnej funkcji (ale innej) do wygenerowania unikalnego identyfikatora na podstawie nazwy użytkownika i bieżącego 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 

Edycja Czerwiec 2015: dla nowego kodu używam shortid: https://www.npmjs.com/package/shortid

Szybki i zwięzły, który został zaadaptowany z Tutaj :

String.prototype.hashCode = function() {
  var hash = 5381, i = this.length
  while(i)
    hash = (hash * 33) ^ this.charCodeAt(--i)
  return hash >>> 0;
}

Mój szybki (bardzo długi) jeden liner oparty na metodzie FNV Multiply+Xor:

my_string.split('').map(v=>v.charCodeAt(0)).reduce((a,v)=>a+((a<<7)+(a<<3))^v).toString(16);

Jeśli chcesz uniknąć kolizji, możesz użyć secure hash Jak SHA-256 . Istnieje kilka implementacji JavaScript SHA-256.

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

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

Połączyłem dwa rozwiązania (użytkownicy esmiralha i lordvlad), aby uzyskać funkcję, która powinna być szybsza dla przeglądarek obsługujących funkcję js reduce () i nadal kompatybilna 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();

Poszedłem na prostą konkatenację kodów znaków przekonwertowanych na ciągi szesnastkowe. Służy to stosunkowo wąskiemu celowi, a mianowicie po prostu potrzeba reprezentacji skrótu krótkiego ciągu (np. tytułów, tagów) do wymiany z serwerem, który z nieistotnych powodów nie może łatwo zaimplementować akceptowanego portu Java hashCode. Oczywiście nie ma tu żadnych zabezpieczeń.

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

Może to być bardziej zwięzłe i tolerancyjne dla przeglądarki z podkreśleniem. Przykład:

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

Przypuszczam, że gdybyś chciał aby hashować większe ciągi znaków w podobny sposób, można po prostu zmniejszyć kody znaków i hexify wynikającej sumy, 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"

Oczywiście większe ryzyko kolizji z tą metodą, choć można było się bawić arytmetyką w redukcji, jednak chciał się urozmaicić i wydłużyć hash.

Nieco uproszczona wersja odpowiedzi @esmiralha.

Nie nadpisuję ciągu znaków w tej wersji, 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;
}

Oto prosty, dobrze rozprowadzony 53-bitowy hash. Jest dość szybki i ma niski współczynnik kolizji.

var cyrb53 = function(str) {
    var p1 = 2654435761, p2 = 1597334677, h1 = 0xdeadbeef | 0, h2 = 0x41c6ce57 | 0;
    for (var i = 0; i < str.length; i++)
        ch = str.charCodeAt(i), h1 = Math.imul(h1 + ch, p1), h2 = Math.imul(h2 + ch, p2);
    h1 = Math.imul(h1 ^ h1 >>> 16, p2), h2 = Math.imul(h2 ^ h2 >>> 15, p1);
    return (h2 & 2097151) * 4294967296 + h1;
};

Osiąga lawinowe (nieostre), więc małe zmiany mają duże zmiany w wyjściu, co sprawia, że wydaje się losowe:

0xe00c44e568f86 = "a"
0x893099dbedf04 = "b"
0x98f3f59367810 = "revenge"
0x45f880d099bbf = "revenue"

53-bitowe to limit liczb całkowitych JS i ma znacznie mniejszą szansę na kolizję niż 32-bitowe skróty. Ale jeśli 53 bity to za mało, nadal możesz użyć wszystkich 64 bitów, konstruując łańcuch szesnastkowy lub tablicę:

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

Haczyk polega na konstruowaniu łańcuch szesnastkowy staje się wąskim gardłem wydajności, a tablica wymaga dwóch operatorów porównania zamiast jednego, co nie jest tak wygodne.

Za pomocą tego rozwiązania możemy określić zestaw znaków, aby uniknąć pewnych problemów, gdy wartości są przechowywane lub wysyłane między warstwami aplikacji, na przykład: gdy łańcuch wynikowy (hash) wytwarza kodowanie procentowe i ten łańcuch jest wysyłany do kontrolera za pomocą metody GET z warstwy widoku.

function doHashCode() {
    String.prototype.hashCode = function () {
        var text = "";
        var possible = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

        for (var i = 0; i < 15; i++)
            text += possible.charAt(Math.floor(Math.random() * possible.length));
        return text;
    }

    var hash = new String().hashCode();
    $('#input-text-hash').val(hash); // your html input text

}

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 64 łańcuch znaków; coś takiego: "aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"