Búsqueda de tablas hash: con hash perfecto, en C

Question

Tengo una aplicación de lenguaje C donde necesito hacer búsquedas en la tabla.

Las entradas son cadenas, Todas se conocen al inicio del tiempo de ejecución. La tabla se inicializa una vez y luego se mira hacia arriba muchas veces. La tabla puede cambiar, pero es básicamente como si la aplicación comenzara de nuevo. Creo que esto significa que puedo usar un hash perfecto. Está bien consumir algo de tiempo para la inicialización del hashtable, como ocurre una sola vez.

Habrá entre 3 y 100.000 entradas, cada una única, y estimo que el 80% de los casos tendrán menos de 100 entradas. Una simple búsqueda ingenua es "lo suficientemente rápida" en esos casos. (== nadie se queja)

Sin embargo, en los casos en que hay más de 10k entradas, la velocidad de búsqueda de un enfoque ingenuo es inaceptable. ¿Cuál es un buen enfoque para entregar un buen rendimiento de búsqueda basado en hashta para cadenas en C? Supongamos que no tengo una biblioteca comercial de terceros como Boost/etc. ¿Qué algoritmo hash debería usar? ¿Cómo decido?

Answer 1

Generar un hash perfecto no es un problema simple. Hay bibliotecas dedicadas a la tarea. En este caso, el más popular es probablemente CMPH. No lo he usado, así que no puedo evitarlo. gperf es otra herramienta, pero requiere que las cadenas se conozcan en tiempo de compilación (se puede solucionar compilando .so y cargando, pero algo así como overkill).

Pero francamente, al menos trataría de ir primero con una búsqueda binaria. Simplemente ordene la matriz usando qsort, luego busque con bsearch (o imprima la suya). Ambos son parte de stdlib.h desde C89.

Answer 2

Si un enfoque ingenuo (supongo que usted quiere decir lineal) está bien para 100 entradas (por lo que se realizan 50 comparaciones en promedio), una búsqueda binaria será más que suficiente para 100.000 entradas (toma como máximo 17 comparaciones).

Así que no me molestaría con hashes pero solo recurro a ordenar su tabla de cadenas al inicio (por ejemplo, usando qsort) y luego usando una búsqueda binaria (por ejemplo, usando bsearch) para buscar entradas.

Answer 3

Si se conoce el tamaño (máximo) de la tabla, una tabla hash simple con encadenamiento es muy fácil de implementar. La sobrecarga de tamaño es solo dos entradas por artículo. Con una función hash razonable, solo se necesitan 1,5 sondeos por búsqueda en promedio, esto para una tabla cargada al 100%.

Construir un hash perfecto solo es posible si sus datos no cambian. Una vez que cambie, tendrá que volver a calcular y volver a generar, lo que es mucho más caro que hacer algunas comparaciones adicionales.