¿Cómo harías para diseñar una función para un hash perfecto?

Question

El dominio de interés es la coincidencia de cadenas. Supongamos que tengo una estructura como esta.

typedef struct 
{ 
    char *name, 
    int (*function)(); 

} StringArray 

StringArray s[] = 
{ 
    {"George", func1}, 
    {"Paul", func2}, 
    {"Ringo", func3}, 
    {"John", func4}, 
    {"",  NULL} /* End of list */ 
} 

Hay un número fijo de cadenas en la matriz. Están codificados como en el ejemplo. Si la tabla cambia, sería necesario volver a evaluar la calidad de la función hash.

Quiero aplicar una función hash a una cadena, y si la cadena coincide con una en la matriz, , llame a la función. Se necesita una función hash perfecta para esto. No se permiten colisiones. El propósito de requerir hashing es obtener un rendimiento de O (1) en la búsqueda.

¿Qué ideas tiene sobre el diseño de una función para hacer esto?

Answer 1

Ver la página gperf casa.

Answer 2

Puede utilizar un mapa

std::string foo() { return "Foo"; } 
std::string bar() { return "Bar"; } 

int main() 
{ 
    std::map<std::string, std::string (*)()> m; 
    m["foo"] = &foo; 
    m["bar"] = &bar; 
} 

Answer 3

Ver:

What is a good Hash Function?

Best hashing algorithm in terms of hash collisions and performance

What is a performant string hashing function that results in a 32 bit integer with low collision rates?

Choosing a multiplier for a (string) hash function

Very low cost hash function

What’s the best hashing algorithm to use on a stl string when using hash_map?

Answer 4

Si las colisiones son absolutamente no pueden, su única opción es hacer un seguimiento de cada cadena en la base de datos, lo que probablemente no es una mejor manera de ir.

Lo que yo haría es aplicar uno de los algoritmos hash fuertes comunes existentes, tales como: MD5 o SHA. Hay miríadas de muestras por todas partes, aquí hay una por ejemplo: http://www.codeproject.com/KB/security/cryptest.aspx

Answer 5

Bueno, no hay una función hash perfecta.

Tiene varias que minimizan las colisiones, pero ninguna las elimina.

no puede aconsejar uno sin embargo: P

EDIT: La solución no puede ser encontrar una función hash perfecta. La solución es estar al tanto de las colisiones. Genéricamente una función hash tiene colisiones. Eso obviamente depende del conjunto de datos y del tamaño del código hash resultante.

Answer 6

Utilice un árbol binario equilibrado. Entonces SABER el comportamiento es SIEMPRE O (logn).

No me gustan los hashes. La gente no se da cuenta de cuánto riesgo toman con su algoritmo. Ejecutan algunos datos de prueba y luego se implementan en el campo. NUNCA he visto un algoritmo hash implementado que se verifique el comportamiento en el campo.

O (log n) es casi siempre aceptable en lugar de O (1).

Answer 7

El resumen muestra tanto C como C++. ¿Cuál de ellos estás buscando? C y C++ son dos lenguajes distintos, y difieren mucho en su manejo de cadenas y estructuras de datos (y el hecho de que los C trabajen en C++ no cambia eso).

¿Por qué, específicamente, quieres una función hash perfecta? ¿Es que quieres asociar una cadena con una función y pensaste que sería una buena forma de hacerlo? ¿Es esto una especie de tarea asignada? ¿Tiene alguna razón para no usar el mapa <> en C++? (O unordered_map <> si está disponible?)

Si necesita un hash perfecta, ¿cuáles son las limitaciones de las cuerdas? ¿Habrá un cierto conjunto fijo en el que desea enviar? ¿Qué pasa con las cadenas que no coinciden con uno del conjunto? ¿Estás dispuesto a aceptar hits de cadenas aleatorias o la cantidad de cadenas entrantes es limitada?

Si pudieras editar tu pregunta para incluir información como esa, podríamos ser mucho más útiles.

EDITAR (en respuesta a los dos primeros comentarios):

bien, debemos buscar soluciones C, ya que presumiblemente quiere esto, tanto para su C y C++ trabajo. Es de suponer que quieres el rendimiento, pero has probado? Si se trata de cadenas que entran en el sistema de E/S, es probable que el tiempo disminuya el tiempo de despacho.

Está esperando cadenas arbitrarias. Es mucho esperar una función hash perfecta que evitará todas las colisiones de datos aleatorios, por lo que debe tenerlo en cuenta.

¿Has considerado un trie? Puede ser más eficiente que una función hash perfecta (o no), debería ser bastante fácil de implementar en C y evitará problemas al volver a hacer la lista de cadenas de envío o posibles colisiones.

Answer 8

El resultado final de este ejercicio era

• robar un número de funciones hash orientada cuerda fuera de la red.
• Cree un tipo de clase de fábrica que pruebe cada una de las funciones contra el conjunto de datos con un rango de valores de operador mod, buscando el hash perfecto más pequeño que funcione con esa función.
• Ese constructor predeterminado de la clase de fábrica devuelve una cadena, que representa un conjunto de argumentos que cuando el uso selecciona la función hash correcta, y el tamaño del mod para proporcionar el hash perfecto que requiere la menor cantidad de memoria.
• bajo uso normal, simplemente crea una instancia de la clase con los argumentos devueltos, y la clase se pone en un estado de trabajo con las funciones deseadas.
• Ese constructor valida que no hay colisiones y cancela si hay.
• En el caso de que no se encuentre un hash perfecto, se degrada en una búsqueda binaria en una versión ordenada de la tabla de entrada.

Para el conjunto de matrices que tengo en mi dominio, esto parece funcionar muy bien. Una posible optimización futura sería hacer el mismo tipo de prueba, en subcadenas de la entrada. En el caso de muestra, la primera letra del nombre de cada músico es suficiente para distinguirlos. Entonces uno necesitaría equilibrar el costo de la función de hash real contra la memoria utilizada.

Mi agradecimiento a todos los que contribuyeron ideas.

mal