Tenemos la mejor respuesta que encontramos en internet. Nosotros queremos que te resulte de mucha ayuda y si quieres aportar alguna mejora hazlo con total libertad.
Solución:
String.prototype.hashCode = function()
var hash = 0, i, chr;
if (this.length === 0) return hash;
for (i = 0; i < this.length; i++)
chr = this.charCodeAt(i);
hash = ((hash << 5) - hash) + chr;
hash
return hash;
;
Fuente: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-método-hashcode/
EDITAR
según 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 reduce array función.
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 sola línea:
hashCode = s => s.split('').reduce((a,b)=>a=((a<<5)-a)+b.charCodeAt(0);return a&a,0)
Nota: Incluso con el mejor hash de 32 bits, las colisiones voluntad ocurra tarde o temprano.
La probabilidad de colisión hash se puede calcular como
aproximado como
(mira aquí). Esto puede ser más alto de lo que sugiere la intuición:
Suponiendo un hash de 32 bits y k = 10 000 elementos, se producirá una colisión con una probabilidad del 1,2 %. ¡Para 77,163 muestras la probabilidad se convierte en 50%! (calculadora).
Sugiero una solución en la parte inferior.
En respuesta a esta pregunta ¿Qué algoritmo hash es mejor para la unicidad y la velocidad?, Ian Boyd publicó un buen análisis en profundidad. En resumen (tal como lo interpreto), llega a la conclusión de que Murmur es el mejor, seguido de FNV-1a.
El algoritmo String.hashCode() de Java que propuso esmiralha 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
Cuándo pequeño las cadenas de entrada se procesan, el rendimiento de murmur cae, en relación con DJ2B y FNV-1a: http://jsperf.com/32-bit-hash/3
Entonces, en general, recomendaría murmur3.
Vea aquí 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 pequeño del código son más importantes que la velocidad, uso 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 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;
Mejore la probabilidad de colisión
Como se explica aquí, podemos extender el tamaño del 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)
Úsalo con cuidado y no esperes demasiado.
Sección de Reseñas y Valoraciones
Eres capaz de añadir valor a nuestra información tributando tu veteranía en las críticas.