Générer un hachage à partir d'une chaîne dans Javascript / jQuery


J'ai besoin de convertir les chaînes en une forme de hachage. Est-ce possible en Javascript / jQuery?

Je n'utilise pas de langage côté serveur, donc je ne peux pas le faire de cette façon.




Answers





MODIFIER

basé sur mes tests jsperf, la réponse acceptée est en fait plus rapide: http://jsperf.com/hashcodelordvlad

ORIGINAL

Si quelqu'un est intéressé, voici une version améliorée (plus rapide), qui échouera sur les anciens navigateurs qui n'ont pas la fonction de reduce matrice.

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



Note: Même avec le meilleur hachage 32 bits, vous devrez faire face au fait que les collisions se produiront tôt ou tard. C'est-à-dire que deux chaînes d'entrée différentes retourneront la même valeur de hachage avec une probabilité d'au moins 1: 2 ^ 32.

Dans une réponse à cette question Quel algorithme de hachage est le meilleur pour l'unicité et la vitesse? Ian Boyd a publié une analyse approfondie . En bref (comme je l'interprète), il arrive à la conclusion que Murmur est le meilleur, suivi de FNV-1a.
L'algorithme String.hashCode () de Java proposé par esmiralha semble être une variante de DJB2.

  • FNV-1a a une meilleure distribution que DJB2, mais est plus lente
  • DJB2 est plus rapide que FNV-1a, mais tend à générer plus de collisions
  • MurmurHash3 est meilleur et plus rapide que DJB2 et FNV-1a (mais l'implémentation optimisée nécessite plus de lignes de code que FNV et DJB2)

Quelques benchmarks avec de grandes chaînes d'entrée ici: http://jsperf.com/32-bit-hash
Lorsque les chaînes d'entrée courtes sont hachées, la performance de murmur chute par rapport à DJ2B et FNV-1a: http://jsperf.com/32-bit-hash/3

Donc, en général, je recommanderais murmur3.
Voir ici pour une implémentation JavaScript: https://github.com/garycourt/murmurhash-js

Si les chaînes d'entrée sont courtes et que la performance est plus importante que la qualité de distribution, utilisez DJB2 (comme proposé par la réponse acceptée par esmiralha).

Si la qualité et la petite taille du code sont plus importantes que la vitesse, j'utilise cette implémentation de FNV-1a (basée sur ce code ).

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



Si cela aide quelqu'un, j'ai combiné les deux premières réponses dans une version plus tolérante pour les navigateurs, qui utilise la version rapide si reduce est disponible et retombe à la solution d'esmiralha si ce n'est pas le cas.

/**
 * @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'utilisation est comme:

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



Basé sur la réponse acceptée dans ES6. Plus petit, maintenable et fonctionne dans les navigateurs modernes.

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

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




C'est une variante raffinée et performante:

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

Cela correspond à l'implémentation Java de l'objet standard object.hashCode()

Voici aussi celui qui ne renvoie que des hashcodes positifs:

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

Et voici un correspondant pour Java qui ne renvoie que des hashcodes positifs:

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

Prendre plaisir!




Grâce à l'exemple de mar10, j'ai trouvé un moyen d'obtenir les mêmes résultats en C # ET Javascript pour un FNV-1a. Si des caractères Unicode sont présents, la partie supérieure est mise au rebut pour des raisons de performance. Je ne sais pas pourquoi il serait utile de les maintenir en hachage, car je ne fais que hacher les chemins d'URL pour le moment.

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

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



J'avais besoin d'une fonction similaire (mais différente) pour générer un ID unique basé sur le nom d'utilisateur et l'heure actuelle. Alors:

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

Produit:

2DVFXJGEKL
6IZPAKFQFL
ORGOENVMG
... etc 

edit juin 2015: Pour le nouveau code j'utilise shortid: https://www.npmjs.com/package/shortid




Je suis un peu surpris que personne n'ait encore parlé de la nouvelle API SubtleCrypto .

Pour obtenir un hachage à partir d'une chaîne, vous pouvez utiliser la méthode 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);
  });




Un rapide et concis qui a été adapté d' ici :

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



J'ai combiné les deux solutions (utilisateurs esmiralha et lordvlad) pour obtenir une fonction qui devrait être plus rapide pour les navigateurs qui supportent la fonction js reduce () et qui sont toujours compatibles avec les anciens navigateurs:

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

Exemple:

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



Je suis allé pour une concaténation simple de codes char transformés en chaînes hexagonales. Cela sert un objectif relativement étroit, à savoir juste avoir besoin d'une représentation de hachage d'une chaîne SHORT (par exemple titres, tags) à échanger avec un serveur qui, pour des raisons non pertinentes, ne peut pas facilement implémenter le port Java hashCode accepté. De toute évidence, aucune application de sécurité ici.

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

Cela peut être rendu plus concis et plus tolérant pour les navigateurs avec Underscore. Exemple:

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

Je suppose que si vous vouliez hacher des chaînes plus grandes d'une manière similaire, vous pourriez simplement réduire les codes char et hexifier la somme résultante plutôt que de concaténer les caractères individuels ensemble:

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"

Naturellement plus de risque de collision avec cette méthode, bien que vous pourriez jouer avec l'arithmétique dans la réduction, mais vous avez voulu diversifier et allonger le hachage.







Version légèrement simplifiée de la réponse de @ esmiralha.

Je ne remplace pas String dans cette version, car cela pourrait entraîner un comportement indésirable.

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



Avec cette solution, nous pouvons spécifier le jeu de caractères pour éviter certains problèmes lorsque les valeurs sont stockées ou envoyées entre couches d'application, par exemple: Lorsque la chaîne de résultat (hash) produit un codage en pourcentage et que cette chaîne est envoyée au contrôleur utilisant la méthode GET couche.

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

}