Genera un hash da una stringa in Javascript / jQuery


Ho bisogno di convertire stringhe in una qualche forma di hash. È possibile in Javascript / jQuery?

Non sto utilizzando un linguaggio lato server, quindi non posso farlo in quel modo.




Answers





MODIFICARE

basato sui miei test jsperf, la risposta accettata è in realtà più veloce: http://jsperf.com/hashcodelordvlad

ORIGINALE

se qualcuno è interessato, ecco una versione migliorata (più veloce), che fallirà sui browser più vecchi che non hanno la funzione di reduce dell'array.

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



Nota: anche con il miglior hash a 32 bit, dovrai affrontare il fatto che le collisioni si verificheranno prima o poi. Cioè due diverse stringhe di input restituiranno lo stesso valore di hash con una probabilità di almeno 1: 2 ^ 32.

In una risposta a questa domanda Quale algoritmo di hashing è il migliore per unicità e velocità? , Ian Boyd ha pubblicato una buona analisi approfondita . In breve (come lo interpreto), giunge alla conclusione che Murmur è il migliore, seguito da FNV-1a.
L'algoritmo di Java String.hashCode () proposto da esmiralha sembra essere una variante di DJB2.

  • FNV-1a ha una distribuzione migliore di DJB2, ma è più lento
  • DJB2 è più veloce di FNV-1a, ma tende a produrre più collisioni
  • MurmurHash3 è migliore e più veloce di DJB2 e FNV-1a (ma l'implemazione ottimizzata richiede più linee di codice di FNV e DJB2)

Alcuni benchmark con stringhe di input di grandi dimensioni qui: http://jsperf.com/32-bit-hash
Quando le stringhe di input brevi vengono sottoposte a hash, le prestazioni del soffio diminuiscono rispetto a DJ2B e FNV-1a: http://jsperf.com/32-bit-hash/3

Quindi, in generale, consiglierei murmur3.
Vedi qui per un'implementazione JavaScript: https://github.com/garycourt/murmurhash-js

Se le stringhe di input sono brevi e le prestazioni sono più importanti della qualità di distribuzione, utilizzare DJB2 (come proposto dalla risposta accettata da esmiralha).

Se la qualità e le dimensioni ridotte del codice sono più importanti della velocità, io uso questa implementazione di FNV-1a (basata su questo codice ).

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



Se aiuta qualcuno, ho combinato le due risposte principali in una versione tollerante del vecchio browser, che usa la versione veloce se la reduce è disponibile e ricade nella soluzione di esmiralha se non lo è.

/**
 * @see http://.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;
}

L'utilizzo è come:

var hash = new String("some string to be hashed").hashCode();



Basato sulla risposta accettata in ES6. Più piccolo, manutenibile e funziona nei browser moderni.

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

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




Questa è una variante raffinata e migliore:

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

object.hashCode() all'applicazione Java dello standard object.hashCode()

Ecco anche uno che restituisce solo hashcode positivi:

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

Ed ecco un matching per Java che restituisce solo hashcode positivi:

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

Godere!




Grazie all'esempio di mar10, ho trovato un modo per ottenere gli stessi risultati in C # e Javascript per un FNV-1a. Se sono presenti caratteri unicode, la parte superiore viene scartata per motivi di prestazioni. Non so perché sarebbe utile per mantenere quelli quando hashing, come sono solo percorsi di URL hashing per ora.

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

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



Avevo bisogno di una funzione simile (ma diversa) per generare un ID univoco basato sul nome utente e sull'ora corrente. Così:

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

produce:

2DVFXJGEKL
6IZPAKFQFL
ORGOENVMG
... etc 

modifica giugno 2015: per il nuovo codice uso shortid: https://www.npmjs.com/package/shortid




Sono un po 'sorpreso che nessuno abbia ancora parlato della nuova API di SubtleCrypto .

Per ottenere un hash da una stringa, puoi utilizzare il metodo subtle.digest :

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




Uno veloce e conciso che è stato adattato da qui :

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



Ho combinato le due soluzioni (utenti esmiralha e lordvlad) per ottenere una funzione che dovrebbe essere più veloce per i browser che supportano la funzione js reduce () e comunque compatibile con i vecchi browser:

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

Esempio:

my_string = 'xyz';
my_string.hashCode();



Sono andato per una semplice concatenazione di codici char convertiti in stringhe esadecimali. Questo ha uno scopo relativamente ristretto, ovvero richiede solo una rappresentazione hash di una stringa SHORT (ad esempio titoli, tag) da scambiare con un lato server che per motivi non rilevanti non può facilmente implementare la porta Java hashCode accettata. Ovviamente nessuna applicazione di sicurezza qui.

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

Questo può essere reso più conciso e tollerante per il browser con Underscore. Esempio:

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

Suppongo che se volessi stringere stringhe più grandi in modo simile, potresti semplicemente ridurre i codici char ed esagerare la somma risultante piuttosto che concatenare i singoli caratteri insieme:

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"

Naturalmente più rischio di collisione con questo metodo, anche se si potrebbe giocare con l'aritmetica nella riduzione, tuttavia si voleva diversificare e allungare l'hash.







Versione leggermente semplificata della risposta di @ esmiralha.

Non sovrascrivo String in questa versione, poiché ciò potrebbe provocare un comportamento indesiderato.

function hashCode(str) {
    var hash = 0;
    for (var i = 0; i < str.length; i++) {
        hash = ~~(((hash << 5) - hash) + str.charCodeAt(i));
    }
    return hash;
}



Con questa soluzione possiamo specificare il set di caratteri per evitare alcuni problemi quando i valori sono memorizzati o inviati tra i livelli dell'applicazione, ad esempio: Quando la stringa risultato (hash) produce la codifica percentuale e quella stringa viene inviata al controller usando il metodo GET dalla vista strato.

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

}