¿Cuál es el caso patológico del método de división para funciones hash h (k) = k (mod m)?
¿Qué tipo de teclas de entrada hace que este método funcione muy mal en el hash para tablas hash?
Entonces, revisé rápidamente la definición real de la palabra patológica, y voy a suponer que está usando la definición informal que es “compulsiva; obsesionante”.
Lo primero a tener en cuenta es que hay una diferencia entre una función hash y una tabla hash. Permítanme reiterar, una función hash no es una tabla hash. Si lo desea, puede pensarlo como la diferencia entre un automóvil y un motor. El motor es parte del automóvil y la función hash es parte de la tabla hash. El motor se puede cambiar por uno con un rendimiento diferente, y muchas otras cosas pueden usar el mismo motor.
- Cómo resolver esta recurrencia [matemáticas] T (n) = T (n-1) + 2 ^ n [/ matemáticas]
- Cómo resolver esta recurrencia T (n) = T (7n / 10) + n
- Cómo resolver la pregunta 8
- ¿Es posible leer y resolver problemas de CLRS en 1 mes para personas sin título de CS, con promedio. conocimiento en matemáticas y buenas habilidades para resolver problemas
- ¿Hay infinitos números (n) de modo que todos los coprimos menores que n sean números primos?
Para la siguiente parte, voy a suponer que k es la clave hash ym es el número de contenedores en la tabla hash. Esa función, h (k) = k (mod m) , es una función común para determinar qué contenedor usar en una tabla hash, no es la función hash. Se puede usar como una función de hashing, pero luego solo funcionaría para hashing cosas como números. La cuestión es que solo hay tantos contenedores en la tabla hash. Claro, podemos hacer que la tabla sea más grande, pero cuanto más grande la hagamos, más memoria usará (y eso no siempre es una opción). Cada clave hash producida (por la función hash) debe ser única para el elemento para el que fue producida. Dado que cada clave es un número único (ish), entonces no hay razón para que no podamos usar una dirección para el elemento que se almacena. Sin embargo, cuando ese número está fuera del rango de contenedores disponibles, debemos hacer algo para que vuelva a estar dentro del rango.
Ahí es donde entra k (mod m) . Esta función se utiliza para dirigir nuestro artículo a lo que esperamos sea un contenedor vacío. Es la única forma en que no podríamos hacer esto, no, no lo es. Podríamos intentar fijar el número, pero eso causaría muchas colisiones en los extremos de la tabla hash. Podríamos intentar pasar la clave hash a algo Abs (Cos (k)) * m , pero esa es solo otra forma elegante de envolver la clave hash en un valor que se ajuste al número de contenedores y es más matemática. Puede haber mejores formas de asignar una clave hash en un contenedor de tabla hash, pero esta es agradable y simple.
En cuanto a la parte de su pregunta sobre las claves que son malas para el rendimiento de la tabla hash.
Esto depende de la función de crecimiento utilizada para la tabla hash y la previsibilidad de las claves hash. Me di cuenta de que muchos valores numéricos de tipo entero usarán su propio valor como clave hash, por lo que son bastante predecibles. Luego, viene la función de crecimiento de la tabla hash. Hay algunas razones para hacer crecer una tabla hash, una de esas razones son las colecciones de claves hash causadas al intentar ingresar demasiados elementos en un solo contenedor de tabla hash.
Por ejemplo, si sabe que m = 2 ^ i , entonces puede comenzar a ingresar cosas que producirán claves grandes que siempre caerán en el contenedor final a pesar de los múltiples cambios de tamaño. Sí, eventualmente, el contenedor será lo suficientemente grande como para que esos elementos ya no causen colisiones de claves hash, pero puede mantener la tabla hash en alto durante bastante tiempo. Después de todo, es un poco difícil almacenar elementos adicionales en la tabla hash mientras se redimensiona.