Al leer el pigeonhole principle en Wikipedia, me doy cuenta de que "las colisiones son inevitables en una tabla hash porque el número de claves posibles supera el número de índices en la matriz. Ningún algoritmo hash, por inteligente que sea, puede evitar estas colisiones" . Pero no es gperf haciendo esto exactamente?¿Función hash perfecta?
Por favor ilumine.
gperf crea la función hash y la tabla hash basándose en una lista de cadenas predefinida.
Por lo tanto, me parece que gperf crea los hashes el tiempo suficiente para que haya suficientes posibilidades.
Eso es lo que puedes hacer solo si conoces todas las claves posibles por adelantado, una suposición que no era válida para la descripción en la entrada de la wikipedia, que aparentemente estaba relacionada con una tabla hash "no constante".
Desde el sitio web del gperf: "Para una lista dada de cadenas, produce una función hash y tabla hash, ..." - lo que significa que tiene que conocer todas las cadenas previamente para preparar una función, eso funciona sin colisiones
Las funciones hash usuales que está utilizando en los lenguajes de programación generales son capaces de manejar cualquier cadena como entrada una tras otra (la lista no se entrega al mismo tiempo) y, por lo tanto, pueden producir colisiones.
Esta es una buena pregunta. – sharptooth