algorithm - una - tipos de funciones hash
¿Encontrar elementos en una tabla hash universal? (3)
Si los elementos están organizados al azar, ¿cómo sabe la tabla dónde comenzar a buscar?
En una tabla no aleatoria, los elementos se organizan de acuerdo con alguna característica. (es decir, nombre). Así que si la tabla necesita buscar información arbitraria sobre "John", puede comenzar a buscar en el cubo ''J''.
Sin embargo, en una tabla hash universal, los elementos se organizan de forma aleatoria. No hay una característica definitoria. Por lo tanto, para encontrar información arbitraria sobre "John", ¿no tendría que mirar la mesa a través de cada cubo?
¿No es eso una enorme pérdida de tiempo? Es como mirar a través de cada gabinete en tu casa para encontrar una cuchara.
Si bien las respuestas anteriores son esencialmente correctas, no abordan directamente la parte aleatoria de un algoritmo de hash universal. Los algoritmos de hash universal no usan aleatoriedad al calcular un hash para una clave. Los números aleatorios solo se utilizan durante la inicialización de la tabla hash para elegir una función hash de una familia de funciones hash. Esto evita que un adversario con acceso a los detalles de la función hash cree un conjunto de claves en el peor de los casos.
En otras palabras, durante la vida útil de la tabla hash, el depósito para una clave dada es consistente. Sin embargo, una instancia diferente (como la próxima vez que se ejecute el programa) puede colocar esa misma clave en un grupo diferente.
Un hash parece más o menos aleatorio, pero es determinista, es decir, una entrada particular siempre produce el mismo valor de hash.
En función de eso, cuando desee insertar un elemento en una tabla hash, comience generando el hash para esa entrada. Luego lo usa para indexar en la tabla e inserte su artículo en ese lugar de la tabla. En un caso típico, tiene una parte que se trata como la clave, y tiene más información asociada con eso (por ejemplo, puede buscar personas por su nombre y con cada nombre que tenga información sobre esa persona).
Más adelante, cuando desee buscar (la información asociada con) una clave en particular (en este caso, la persona), ingrese y presione la clave para encontrar el lugar correcto en la tabla hash para buscar esa información.
Eso omite algunos detalles cruciales, como la forma en que maneja las dos o más entradas que se producen para producir el mismo valor hash (que es inevitable a menos que coloque algunos límites en las entradas permitidas). Hay varias formas de manejar esto, como mirar la tabla de forma secuencial para encontrar el siguiente lugar libre, volver a escribir para encontrar otro punto en la tabla o crear algo así como una lista enlazada de elementos que tienen el mismo valor.
En cualquier caso, probablemente debería agregarse que hay casos de uso para los cuales una tabla hash termina un poco como usted ha supuesto. Solo por un ejemplo, cuando desea ver todo el contenido de una tabla hash (en lugar de solo buscar un elemento a la vez), normalmente escanea toda la tabla. Incluso si su tabla hash está casi vacía, normalmente tiene que escanear de un extremo a otro, buscando todas las entradas que realmente estén en uso. Cuando haces eso, obtienes artículos en un orden que parece bastante aleatorio.
Esto apunta a otra deficiencia de las tablas hash: generalmente necesita una coincidencia precisa con un único registro original para que funcionen bien. Por ejemplo, consideremos algunas consultas basadas en mi apellido. Suponiendo que haya indexado el apellido completo, sería trivial encontrar "Coffin", pero al menos con la mayoría de las funciones de hash normales, buscar "algo que comience con" Cof "sería mucho más lento, como" encontrar todos los nombres entre "Coffin" y "Demming".
Como tal, es casi correcto a medias, mientras que las tablas hash suelen ser muy rápidas en algunos casos específicos (principalmente en busca de una coincidencia exacta), la idea general que describió (explorando toda la tabla para encontrar los datos). Es casi la única opción disponible para algún otro propósito, por lo que si desea admitir algo que no sea una coincidencia exacta, puede ser preferible una estructura de datos diferente.
Se trata principalmente de los usos / tipos más comunes de tablas hash. Es posible crear funciones hash que al menos doblen (si no se rompen) esas reglas en diversos grados. En la mayoría de los casos estos implican algunos compromisos sin embargo. Por ejemplo, dada la información geográfica como entrada, puede crear un hash (de tipo) simplemente truncando las coordenadas (o una de ellas, de todos modos) para obtener la misma información con menor precisión. Esto organiza la información al menos hasta un grado, de modo que las cosas que están juntas terminan con valores hash similares, lo que facilita la búsqueda de datos adyacentes. Sin embargo, esto a menudo conducirá a más colisiones (por ejemplo, obtendrás muchos artículos con el mismo valor para el centro de una ciudad grande).
Al observar específicamente el hash universal, esto agrega un elemento adicional al rompecabezas: en lugar de una función de hash única, tiene una familia de funciones de hash de las que elige "al azar". Cuando se utiliza el hash universal para implementar una tabla de hash (que no siempre es así, también se usa para cosas como los códigos de autenticación de mensajes), por lo general, no se elige la función de hash de forma aleatoria cada vez que se inserta un elemento. Más bien, normalmente elige un hash y continúa usándolo hasta que encuentra un número fijo de colisiones. Luego eliges aleatoriamente otra función hash.
Por ejemplo, en el hash de cuco (probablemente el hash universal más utilizado), hash tu clave para encontrar una ubicación. Si ya está ocupado, "expulsas" el elemento existente allí y lo vuelves a encontrar para encontrar una ubicación alternativa para él. Se inserta allí. Si esa ranura ya está ocupada, "expulsa" el elemento que ya está en esa ranura y el patrón se repite.
Cuando buscas un artículo, lo hash y miras esa ubicación. Si está vacío, inmediatamente sabes que tu artículo no está presente. Si esa ranura está ocupada, pero no contiene su elemento, debe volver a buscar para encontrar la ubicación alternativa. Continúe con este patrón para tantas funciones hash como esté utilizando (normalmente solo dos en el caso del hash cuco, pero obviamente podría usar un algoritmo similar con otras funciones).
Es posible que esto falle: entrar en un bucle infinito, o (casi de manera equivalente) construir una cadena que exceda una cierta cantidad de longitud preestablecida. En este caso, comienza de nuevo, reconstruyendo la tabla con un par diferente de funciones hash.
Cuando se utiliza el hashing abierto (de los cuales el hashing universal es una forma), la eliminación tiende a ser no trivial. En particular, debemos asegurarnos de que cuando eliminamos un artículo en una ubicación, no fue el comienzo de una cadena de artículos que colisionaron en esa ubicación. En muchos casos, es más eficiente simplemente agregar un tercer estado para una ranura: si nunca se ha ocupado, simplemente está vacío. Si está ocupado actualmente, está en uso. Si un elemento se ha eliminado allí, se elimina. De esta manera, cuando busca un elemento, si encuentra una ranura "eliminada", continúa buscando su elemento (mientras que, si llega a una ranura que nunca se ha utilizado, puede detener la búsqueda de inmediato: su elemento es evidente). nunca fue insertado).
Una tabla hash no está organizada al azar. Está organizado por valor hash. La tabla se busca por valor de hash para recuperar el grupo de hash correcto.