¿Qué algoritmo de hashing es el mejor para la unicidad y la velocidad? Los ejemplos de uso (bueno) incluyen los diccionarios de hash.
Sé que hay cosas como SHA-256 y similares, pero estos algoritmos están diseñados para ser seguros, lo que normalmente significa que son más lentos que los algoritmos que son menos únicos. Quiero un algoritmo hash diseñado para ser rápido, pero que siga siendo bastante único para evitar colisiones.
Aquí hay una lista de funciones hash, pero la versión corta es:
Si sólo quieres tener una buena función hash, y no puedes esperar,
djb2
es una de las mejores funciones hash de cadenas que conozco. Tiene una excelente distribución y velocidad en muchos conjuntos diferentes de claves y tamaños de tabla
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
Los algoritmos SHA (incluido SHA-256) están diseñados para ser rápidos.
De hecho, su velocidad puede ser un problema a veces. En particular, una técnica común para almacenar un token derivado de una contraseña es ejecutar un algoritmo de hash rápido estándar 10.000 veces (almacenando el hash del hash del hash de la ... contraseña).
#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'
def run_random_digest(digest, count)
v = SecureRandom.random_bytes(digest.block_length)
count.times { v = digest.digest(v) }
v
end
Benchmark.bmbm do |x|
x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end
Salida:
Rehearsal ------------------------------------
1.480000 0.000000 1.480000 ( 1.391229)
--------------------------- total: 1.480000sec
user system total real
1.400000 0.000000 1.400000 ( 1.382016)
Java utiliza este algoritmo simple de multiplicar y sumar:
El código hash de un objeto String se calcula como
s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]
utilizando la aritmética int, donde
s[i]
es el carácter ia de la cadena,n
es la longitud de la cadena, y^
indica la exponenciación. (El valor hash de la cadena vacía es cero).
Probablemente haya otros mucho mejores, pero éste está bastante extendido y parece ser un buen compromiso entre velocidad y unicidad.