En el mundo ideal, supondría que hay una distribución de claves y esto le permitiría analizar un comportamiento de caso promedio. Sin embargo, en el mundo real, esto es extremadamente difícil de hacer por dos razones: (1) no está claro qué distribución usar, (2) sus matemáticas serán muy complejas si es posible.
Entonces, como señaló Daniel Tunkelang, hacemos una suposición simple (SUHA (informática)) y asumimos ciegamente que las cosas van a estar bien: es decir, las llaves se distribuirán milagrosamente de manera uniforme entre los cubos. Esta no es la única suposición simplificadora sobre las funciones hash, hay varias otras. Por ejemplo, en el análisis del hashing sensible a la localidad, suponemos que una función hash se vuelve a seleccionar de forma aleatoria e independiente para cada par de puntos de datos (consulte mis notas aquí: ¿Tiene el análisis de Hashing sensible a la localidad (LSH) un defecto fatal?)
Sin embargo, tenga en cuenta que la suposición SUHA (simple hashing uniforme) no le permite contar nada sobre la peor complejidad del caso (como lo señaló Mark Gritter). Le permite establecer una complejidad de caso promedio (garantía). Si desea optimizar para el peor de los casos, puede optar por utilizar una función hash perfecta. Para un conjunto de valores preespecificados (de un universo estático de posibles claves hash), la función hash perfecta siempre combina diferentes elementos en diferentes cubos. En otras palabras, la función de hash perfecta no tiene colisiones .
- Dados n objetos y p posiciones divididas equitativamente alrededor de una tabla, n <= p, ¿cuántas combinaciones de ubicación existen?
- ¿Ya se resolvió P versus NP? ¿Si es así, cómo?
- ¿Todos los números reales tienen una expansión binaria?
- ¿Aborda problemas difíciles de NP, como el problema de enrutamiento de vehículos, con algoritmos de ruta más corta? ¿Por qué?
- Cómo solucionar problemas y resolver problemas de capa 1
Un inconveniente aquí es que la función hash no está especificada para claves fuera de un dominio dado. Por ejemplo, puede hacer hash perfectamente enteros de 0 a 1000, pero no sabrá cómo lidiar con 1001. Un hash de Cuckoo no tiene esta limitación, al tiempo que permite responder consultas en O (1) en el peor de los casos.
Suena bien, ¿eh? Bueno, en realidad tanto el cuckoo como el hashing perfecto comparten una desventaja común: la indexación es un procedimiento mucho más costoso en comparación con el esquema de hashing clásico. AFAIK, solo hay garantías probabilísticas de un éxito. En la práctica, creo que es muy poco probable que no pueda crear una tabla hash, pero puede llevarle bastante tiempo hacerlo.
Bueno, claramente hay mejores y peores funciones hash. Con mejores funciones hash, las claves se distribuyen entre cubos de manera más o menos uniforme. Esto no es necesariamente cierto si su función hash es mala. En su famoso libro, Donald Knuth considera las pruebas de función hash en detalle. ¿Son completamente inútiles las malas funciones? En mi experiencia, esto no es necesariamente así (pero mejores funciones hash conducen a un rendimiento sustancialmente mejor).
Si bien incluso las malas funciones hash pueden estar bien para muchos fines prácticos, una selección de claves adversas y su orden de inserción pueden causar un problema de rendimiento real . Para muchas funciones hash, un pirata informático que conozca su función hash puede seleccionar una secuencia de teclas de este tipo que resultaría en un tiempo de inserción casi O (N) (N es el número de entradas).
Una solución a este problema (aún no se ha adoptado en todos los idiomas principales) es el hash aleatorio: se puede usar la misma función de hash, pero se seleccionará al azar algún parámetro de hash para cada tabla de hash que cree en su programa (consulte, por ejemplo, ¿Utiliza hashing aleatorio si le preocupa la seguridad?)
