Rápido de la Cadena de Algoritmo de Hash con la baja de las tasas de colisión con 32 bits entero [cerrado]
https://stackoverflow.com/questions/114085
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo un montón de la relación de nombre las cosas que me gustaría hacer búsquedas rápidas a la contra.Un "oso hormiguero" es siempre un "oso hormiguero" en todas partes, así hash de la cadena y la reutilización de los entero de que iba a funcionar bien para acelerar las comparaciones.El conjunto de nombres que se desconoce (y los cambios en el tiempo).¿Qué es una rápida cadena de algoritmo de hash que se generan pequeños (de 32 o 16) los valores de los bits y tiene una baja tasa de colisión?
Me gustaría ver una óptima aplicación específica para C/C++.
Solución
Uno de los FNV variantes debe cumplir con sus requisitos.Son rápidos, y producir una distribución bastante homogénea de las salidas.
Otros consejos
Soplo De Hash es bastante agradable.
Para una cadena fija-el uso del conjunto gperf.
Si la cadena de conjunto de cambios que tienen para elegir una función de hash.Ese tema ha sido discutido antes:
¿Cuál es el mejor algoritmo de hash para su uso en un stl cadena cuando se utiliza hash_map?
También hay un buen artículo en eternallyconfuzzled.com.
Jenkins " Uno-en-un-Tiempo de hash para las cadenas debe ser algo como esto:
#include <stdint.h>
uint32_t hash_string(const char * s)
{
uint32_t hash = 0;
for(; *s; ++s)
{
hash += *s;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Otra solución que podría ser aún mejor, dependiendo de su caso de uso es las internadas de cadenas.Esto es como los símbolos de trabajo por ejemploen Lisp.
Un interno de la cadena es un objeto string cuyo valor es la dirección real de la cadena de bytes.Por lo que se crea un internado de la cadena objeto de comprobación en una tabla global:si la cadena está ahí, puede inicializar el internado de la cadena a la dirección de la cadena.Si no, que se inserta, y luego inicializar el internado de la cadena.
Esto significa que dos internadas de cadenas construido a partir de la misma cadena, tienen el mismo valor, que es una dirección.Así que, si N es el número de internados cadenas en su sistema, las características son:
- Lenta construcción (necesidades de búsqueda y, posiblemente, la asignación de memoria)
- Requiere global de datos y la sincronización en el caso de los subprocesos simultáneos
- Comparar es O(1), debido a que usted está comparando las direcciones, no la real cadena de bytes (esto significa clasificación funciona bien, pero no va a ser una clasificación alfabética).
Saludos,
Carl
Por qué no simplemente usar Impulso de las bibliotecas? Su función hash es simple de usar y la mayoría de las cosas en Impulsar pronto será parte del estándar de C++.Algunos de lo que ya es.
Impulsar el hash es tan fácil como
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
Usted puede encontrar impulsar en boost.org
Nunca es tarde para un buen tema y estoy seguro de que la gente estaría interesada en mis conclusiones.
Yo necesitaba una función de hash, y después de leer este post y hacer un poco de investigación sobre los vínculos que se dan aquí, me encontré con esta variación de Daniel J Bernstein del algoritmo, que he utilizado para hacer una prueba interesante:
unsigned long djb_hashl(const char *clave)
{
unsigned long c,i,h;
for(i=h=0;clave[i];i++)
{
c = toupper(clave[i]);
h = ((h << 5) + h) ^ c;
}
return h;
}
Esta variación de los hash de las cadenas de ignorar el caso, que se adapte a mi necesidad de hash usuarios credenciales de inicio de sesión.'clave' es 'clave' en español.Lo siento por los españoles, pero es mi lengua materna y el programa que está escrito en ella.
Bueno, escribí un programa que va a generar los nombres de usuario de 'test_aaaa' a 'test_zzzz', y -para hacer las cadenas más largas - he añadido un dominio aleatorio en esta lista:'cloud-nueve.com', 'yahoo.com', 'gmail.com' y 'hotmail.com'.Por lo tanto, cada uno de ellos, se vería así:
test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, test_aaac@gmail.com, test_aaad@hotmail.com and so on.
Aquí está la salida de la prueba de'Colision entre XXX y XXX' significa 'Choque de XXX y XXX'.'palabras' significa 'palabras' y 'Total' es la misma en ambos idiomas-.
Buscando Colisiones...
Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
Total de Colisiones: 11
Total de Palabras : 456976
Que no es malo, 11 de colisiones de 456,976 (fuera de curso con el de 32 bits como de la tabla de longitud).
La ejecución del programa de uso de 5 caracteres, que es de 'test_aaaaa' a 'test_zzzzz', en realidad se ejecuta fuera de la memoria de creación de la tabla.Abajo está la salida."No hay memoria para insertar XXXX (insertadas XXX) "significa" no Hay suficiente memoria para insertar XXX (XXX insertada)'.Básicamente malloc() error en ese punto.
No hay memoria para insertar 'test_epjcv' (insertadas 2097701).
Buscando Colisiones...
...451 'colision' strings...
Total de Colisiones: 451
Total de Palabras : 2097701
Lo que significa que sólo 451 colisiones en 2,097,701 cadenas.Tenga en cuenta que en ninguna de las ocasiones, hubo más de 2 colisiones por código.Que puedo confirmar que es un gran hash para mí, ya que lo que necesito es convertir el ID de inicio de sesión a un 40 bits de identificador único para la indización.Así que la uso para convertir las credenciales de inicio de sesión para una de 32 bits hash y el uso de la extra de 8 bits para controlar hasta 255 de colisiones por código, que lookign en los resultados de la prueba sería casi imposible generar.
Espero que esto sea útil a alguien.
EDITAR:
Como la caja de la prueba es de AIX, me encuentro usando LDR_CNTRL=MAXDATA=0x20000000 para darle más memoria y de largo plazo, los resultados están aquí:
Buscando Colisiones...Total de Colisiones:2908 Total de Palabras :5366384
Que es 2908 después de 5,366,384 intenta!!
MUY IMPORTANTE:Compilar el programa con -maix64 (así unsigned long es de 64 bits), el número de colisiones es 0 para todos los casos!!!
Eche un vistazo a GNU gperf.
Bob Jenkins tiene muchas de las funciones de hash disponible, todos los cuales son rápidos y tienen bajas las tasas de colisión.
Usted puede ver lo que .NET que se utiliza en la Cadena.GetHashCode() método que utiliza un Reflector.
Me gustaría aventurar una conjetura que Microsoft pasado un tiempo considerable optimización de este.Se han impreso en toda la documentación de MSDN demasiado que está sujeto a cambios todo el tiempo.Así que claramente es en su rendimiento "afinando" radar ;-)
Sería bastante trivial para el puerto a de C++ también yo habría pensado.
Hay una buena discusión en este la pregunta anterior
Y una buena visión general de cómo recoger las funciones de hash, así como estadísticas sobre la distribución de varios de los más comunes aquí
Se describe aquí es una manera simple de implementar a sí mismo: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html
Un fragmento de el post:
si dicen que tenemos un conjunto de caracteres de capital letras en inglés, entonces la longitud del conjunto de caracteres es de 26, donde a puede ser representado por el número 0, B por el número 1, C por el número 2 y así hasta la Z por el número 25.Ahora, cada vez que desee asignar una cadena de este conjunto de caracteres para un único número , podemos realizar la misma conversión, como hicimos en el caso de que el formato binario
CRC-32.Hay alrededor de un billón de enlaces en google.
