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

Question

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.

Answer 1

String.prototype.hashCode = function() {
  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;
};

Answer 2

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 tableau reduce .

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

Answer 3

Remarque: Même avec la meilleure 32 bits de hachage, vous aurez à composer avec le fait que les accidents vont se produire tôt ou tard. I. e. deux chaînes d'entrée sera de retour la même valeur de hachage, avec une probabilité d'au moins 1 : 2^32.

Dans une réponse à cette question Qui l'algorithme de hachage est le mieux pour l'unicité et de la vitesse?, Ian Boyd a affiché une bonne analyse en profondeur. En bref (comme je l'interpréter), il en vient à la conclusion que le Souffle est le meilleur, suivi par FNV-1a.
Java de la Chaîne.hashCode() algorithme qui esmiralha proposée semble être une variante de DJB2.

• FNV-1a a une meilleure répartition de DJB2, mais est plus lent
• DJB2 est plus rapide que FNV-1a, mais tend à produire plus de collisions
• MurmurHash3 est mieux et plus vite que DJB2 et de la FNV-1a (mais la optimisé implémentation nécessite plus de lignes de code que FNV et DJB2)

Quelques repères avec de grandes chaînes d'entrée ici: http://jsperf.com/32-bit-hash
Lors de courtes chaînes d'entrée sont hachés, murmure la performance de gouttes, par rapport à DJ2B et de la FNV-1a: http://jsperf.com/32-bit-hash/3

Donc, en général, je recommande murmur3.
Voir ici pour un JavaScript de mise en œuvre: https://github.com/garycourt/murmurhash-js

Si les chaînes d'entrée sont de courte et de la performance est plus importante que la qualité de la répartition, l'utilisation DJB2 (comme proposé par le a accepté de répondre par esmiralha).

Si la qualité et de petite taille de code sont plus importants que la vitesse, j'utilise cette mise en œuvre de la FNV-1a (basé 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;
}

Answer 4

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

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

L'utilisation est comme:

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

Answer 5

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