Necesito convertir cadenas a alguna forma de hash. ¿Es esto posible en JavaScript?

No estoy utilizando un lenguaje del lado del servidor, así que no puedo hacerlo de esa manera.

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

Fuente: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/

EDITAR

basado en mis pruebas jsperf, la respuesta aceptada es en realidad más rápida: http://jsperf.com/hashcodelordvlad

ORIGINAL

Si alguien está interesado, aquí hay una versión mejorada (más rápida), que fallará en los navegadores más antiguos que carecen de la reducefunción de matriz.

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

versión de función de flecha de una línea:

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

Nota: Incluso con la mejor hash de 32 bits, las colisiones se producirá tarde o temprano.

La probabilidad de colisión de hash se puede calcular como , aproximadamente como ( ver aquí ). Esto puede ser más alto de lo que sugiere la intuición:
suponiendo un hash de 32 bits yk = 10,000 elementos, se producirá una colisión con una probabilidad de 1.2%. ¡Para 77,163 muestras la probabilidad se convierte en 50%! ( calculadora )
Sugiero una solución en la parte inferior.

En una respuesta a esta pregunta, ¿qué algoritmo de hash es mejor para la unicidad y la velocidad? Ian Boyd publicó un buen análisis en profundidad . En resumen (según lo interpreto), llega a la conclusión de que Murmur es el mejor, seguido de FNV-1a.
El algoritmo String.hashCode () de Java que esmiralha propuso parece ser una variante de DJB2.

• FNV-1a tiene una mejor distribución que DJB2, pero es más lento
• DJB2 es más rápido que FNV-1a, pero tiende a producir más colisiones
• MurmurHash3 es mejor y más rápido que DJB2 y FNV-1a (pero la implementación optimizada requiere más líneas de código que FNV y DJB2)

Algunos puntos de referencia con cadenas de entrada grandes aquí: http://jsperf.com/32-bit-hash
Cuando se cortan cadenas de entrada cortas , el rendimiento del murmullo disminuye, en relación con DJ2B y FNV-1a: http://jsperf.com/32- bit-hash / 3

Entonces, en general, recomendaría murmur3.
Vea aquí para una implementación de JavaScript: https://github.com/garycourt/murmurhash-js

Si las cadenas de entrada son cortas y el rendimiento es más importante que la calidad de distribución, use DJB2 (como lo propone la respuesta aceptada por esmiralha).

Si la calidad y el tamaño de código pequeño son más importantes que la velocidad, utilizo esta implementación de FNV-1a (basada en este código ).

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

Mejora la probabilidad de colisión

Como se explica aquí , podemos extender el tamaño de bit hash usando este truco:

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

Úselo con cuidado y no espere demasiado.

Basado en la respuesta aceptada en ES6. Más pequeño, mantenible y funciona en navegadores modernos.

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

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

EDITAR (2019-11-04) :

versión de función de flecha de una línea:

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

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

Casi la mitad de las respuestas son implementaciones de Java String.hashCode, que no son de alta calidad ni súper rápidas. No es nada especial, solo se multiplica por 31 para cada personaje. Se puede implementar de manera simple y eficiente en una línea, y es mucho más rápido con Math.imul:

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

Con eso fuera del camino, aquí hay algo mejor: cyrb53 , un hash de 53 bits simple pero de alta calidad. Es bastante rápido, proporciona una muy buena distribución de hash y tiene tasas de colisión significativamente más bajas en comparación con cualquier hash de 32 bits.

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

Similar a los conocidos algoritmos MurmurHash / xxHash, utiliza una combinación de multiplicación y Xorshift para generar el hash, pero no tan exhaustivo. Como resultado, es más rápido que en JavaScript y significativamente más simple de implementar.

Alcanza una avalancha (no estricta), lo que básicamente significa que pequeños cambios en la entrada tienen grandes cambios en la salida, haciendo que el hash resultante parezca aleatorio:

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

También puede suministrar una semilla para secuencias alternativas de la misma entrada:

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

Técnicamente es un hash de 64 bits (dos hashes de 32 bits no correlacionados en paralelo), pero JavaScript está limitado a enteros de 53 bits. Si es necesario, la salida completa de 64 bits todavía se puede usar alterando la línea de retorno para una cadena o matriz hexadecimal.

Tenga en cuenta que la construcción de cadenas hexadecimales puede ralentizar drásticamente el procesamiento por lotes en situaciones críticas de rendimiento.

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

Y solo por diversión, aquí hay un hash mínimo de 32 bits en 89 caracteres con mayor calidad que incluso FNV o 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}

Si ayuda a alguien, combiné las dos respuestas principales en una versión más antigua tolerante al navegador, que usa la versión rápida si reduceestá disponible y recurre a la solución de esmiralha si no es así.

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

El uso es como:

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

Esta es una variante refinada y de mejor rendimiento:

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

Esto coincide con la implementación de Java del estándar object.hashCode()

Aquí también hay uno que devuelve solo códigos hash positivos:

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

Y aquí hay una coincidencia para Java que solo devuelve códigos hash positivos:

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

¡Disfrutar!

Estoy un poco sorprendido de que nadie haya hablado aún sobre la nueva API SubtleCrypto .

Para obtener un hash de una cadena, puede usar el subtle.digestmétodo:

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

Gracias al ejemplo de mar10, encontré una manera de obtener los mismos resultados en C # Y Javascript para un FNV-1a. Si hay caracteres unicode, la porción superior se descarta por el bien del rendimiento. No sé por qué sería útil mantenerlos cuando se realiza el hashing, ya que solo estoy haciendo hashing en las rutas de URL por ahora.

Versión 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());
}

Versión 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);
}

Una rápida y concisa que fue adaptada desde aquí :

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

Necesitaba una función similar (pero diferente) para generar una identificación única basada en el nombre de usuario y la hora actual. Entonces:

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 

editar junio de 2015: para el nuevo código uso shortid: https://www.npmjs.com/package/shortid

Mi revestimiento rápido (muy largo) basado en el Multiply+Xormétodo de FNV :

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

SubtleCrypto.digest

No estoy utilizando un lenguaje del lado del servidor, así que no puedo hacerlo de esa manera.

¿Estás seguro de que no puedes hacerlo de esa manera ?

¿Olvidaste que estás usando Javascript, el lenguaje en constante evolución?

Tratar SubtleCrypto. Es compatible con las funciones hash SHA-1, SHA-128, SHA-256 y 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.")));
})();

Llego un poco tarde a la fiesta, pero puedes usar este módulo: crypto :

const crypto = require('crypto');

const SALT = '$ome$alt';

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

El resultado de esta función es siempre una 64cadena de caracteres; algo como esto:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"

He combinado las dos soluciones (usuarios esmiralha y lordvlad) para obtener una función que debería ser más rápida para los navegadores que admiten la función js reduce () y aún compatible con los navegadores antiguos:

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

Ejemplo:

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

Si desea evitar colisiones, puede usar un hash seguro como SHA-256 . Hay varias implementaciones de JavaScript SHA-256.

Escribí pruebas para comparar varias implementaciones de hash, consulte https://github.com/brillout/test-javascript-hash-implementations .

O vaya a http://brillout.github.io/test-javascript-hash-implementations/ , para ejecutar las pruebas.

Esto debería ser un hash un poco más seguro que algunas otras respuestas, pero en una función, sin ninguna fuente precargada

Básicamente, creé una versión simplificada simplificada de sha1.
Toma los bytes de la cadena y los agrupa por "palabras" de 4 a 32 bits.
Luego, ampliamos cada 8 palabras a 40 palabras (para un mayor impacto en el resultado).
Esto va a la función hash (la última reducción) donde hacemos algunos cálculos con el estado actual y la entrada. Siempre sacamos 4 palabras.
Esta es casi una versión de un comando / una línea usando map, reduce ... en lugar de bucles, pero sigue siendo bastante rápido

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

También convertimos la salida a hexadecimal para obtener una cadena en lugar de una matriz de palabras.
El uso es simple. para expandir "a string".hash()regresará"88a09e8f9cc6f8c71c4497fbb36f84cd"

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("");
};
let str = "the string could even by empty";
console.log(str.hash())//9f9aeca899367572b875b51be0d566b5

Fui por una simple concatenación de códigos char convertidos en cadenas hexadecimales. Esto tiene un propósito relativamente limitado, es decir, solo necesita una representación hash de una cadena CORTA (por ejemplo, títulos, etiquetas) para intercambiar con un lado del servidor que por razones no relevantes no puede implementar fácilmente el puerto Java hashCode aceptado. Obviamente no hay aplicación de seguridad aquí.

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

Esto se puede hacer más conciso y tolerante al navegador con Underscore. Ejemplo:

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

Supongo que si quisieras cortar cadenas más grandes de manera similar, podrías reducir los códigos de caracteres y hexadecimal la suma resultante en lugar de concatenar los caracteres individuales:

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, existe un mayor riesgo de colisión con este método, aunque podría jugar con la aritmética en la reducción, sin embargo, quería diversificar y alargar el hash.

Versión ligeramente simplificada de la respuesta de @esmiralha.

No anulo String en esta versión, ya que eso podría provocar un comportamiento no deseado.

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

Agregando esto porque nadie lo hizo todavía, y parece que se ha pedido e implementado mucho con hashes, pero siempre se hizo muy mal ...

Esto toma una entrada de cadena y un número máximo que desea que iguale el hash, y produce un número único basado en la entrada de cadena.

Puede usar esto para producir un índice único en una matriz de imágenes (si desea devolver un avatar específico para un usuario, elegido al azar, pero también elegido en función de su nombre, por lo que siempre se asignará a alguien con ese nombre )

También puede usar esto, por supuesto, para devolver un índice en una matriz de colores, como para generar colores de fondo de avatar únicos basados ​​en el nombre de alguien.

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

No veo ninguna razón para usar este código criptográfico demasiado complicado en lugar de soluciones listas para usar, como la biblioteca de hash de objetos, etc. Confiar en el proveedor es más productivo, ahorra tiempo y reduce los costos de mantenimiento.

Simplemente use https://github.com/puleos/object-hash

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

hash({foo: 'bar'}) // => '67b69634f9880a282c14a0f0cb7ba20cf5d677e9'
hash([1, 2, 2.718, 3.14159]) // => '136b9b88375971dff9f1af09d7356e3e04281951'