Estoy buscando una función hash especial. Digamos que tengo una gran lista de cadenas, si las ordeno por sus valores de hash, deben ordenarse de forma casi aleatoria.Buscando una rápida función hash
El punto más importante es: debe ser superrápido. He probado md5 y sha1 y están usando mucha potencia de la CPU.
Los enfrentamientos no son un problema.
Estoy usando javascript, por lo que no debería ser demasiado complicado de implementar.
Parece que desea el tipo de función hash utilizada en una tabla hash, no el tipo utilizado para detectar duplicados o alteración.
Google le proporcionará una gran cantidad de información sobre funciones hash alternativas. Para empezar, aléjese de los algoritmos hash de firma criptográfica (como MD-5 o SHA-1), resuelven otro problema. Para comenzar, lea this o this, o this.
Eche un vistazo a Murmur hash. Tiene un bonito espacio/colisión disyuntiva:
Olvidé esa. – bmargulies
Si la velocidad es lo más importante, se puede implementar un sencillo de hash ad-hoc, por ejemplo, toma la primera y la última letra y ordena tu cadena por la última y luego la primera letra. El resultado se vería, como dices, "cuasi aleatorio" y sería rápido. Por ejemplo, parte de mi respuesta ordenadas de esa manera se vería así:
ca ad-hoc
el like
es simple
gt taking
hh hash
nc can
ti implement
uy you
Si el hash no hace un buen trabajo para evitar colisiones, la velocidad que ganes durante el hashing se perderá debido a las colisiones. El truco es encontrar un equilibrio entre los dos. –
Julian dijo explícitamente en su pregunta que los choques/colisiones no son un problema y puedo entender por qué. Un hash simple como este proporcionará un orden de palabras cuasialeatorio no obvio: si varias palabras tienen el mismo valor hash, puede que no le interese ordenarlas más y simplemente tomarlas como vienen sin ningún golpe de rendimiento. Obviamente, esta función hash específica no funcionaría bien con todo tipo de conjuntos de datos, pero parece que no hablas de casos de esquina. –
Hsieh, Murmur, Bob Jenkin's viene a la mente.
A nice page about hash functions que tiene algunas pruebas de calidad y un simple hash S-box también.
Parece que es mejor alejarse de SuperFastHash. (1er enlace arriba) http://www.team5150.com/~andrew/blog/2007/03/breaking_superfasthash.html – Matt
@Matt Bueno, basándote en eso, debes evitar todos los hash mencionados en esta página en cualquiera de las respuestas , ya que no son hash de cifrado, a cambio, son mucho más rápidos que, por ejemplo SHA, y - tal como lo preguntó OP - se puede implementar en JS con poco esfuerzo. ;-). Tenga en cuenta la diferencia entre cifrado vs hash "estándar": http://security.stackexchange.com/questions/11839/what-is-the-difference-between-a-hash-function-and-a-cryptographic -función hash –
ver también http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed – rogerdpack