Tablas HASH

Relaciona: TDA. Abstracción de datos.

Relaciona: Clases. Encapsulación. Interfaz o contrato.

Relaciona: Tabla de dispersión (Hash Table o Mapa).

Relaciona: Función Hash o Función de dispersión. Función de Transformación.

Respecto a las tablas hash con encadenamiento (chaining), ¿cuál de las siguientes afirmaciones es correcta?. Las tablas hash con encadenamiento almacenan los elementos directamente en el array, sin usar listas enlazadas. Las listas enlazadas utilizadas en el encadenamiento mejoran el rendimiento de caché en comparación con otras estructuras. Las tablas hash con encadenamiento no son adecuadas para almacenar grandes cantidades de información en memoria secundaria. El encadenamiento permite un crecimiento ilimitado de la tabla, pero tiene la desventaja de un pobre rendimiento de caché debido a las listas enlazadas.

¿Cuál es la complejidad temporal promedio de una búsqueda en una tabla hash bien diseñada?. O(n) - Lineal respecto al tamaño de la tabla. O(log n) - Logarítmica respecto al tamaño de la tabla. O(1) - Constante, independiente del tamaño de la tabla. O(n²) - Cuadrática respecto al tamaño de la tabla.

¿Qué es lo primero que se hace para insertar un elemento en una tabla hash?. Se comprueba si hay espacio disponible en la tabla. Se ordenan alfabéticamente las claves existentes. Se resuelven todas las colisiones anteriores. Se aplica la función hash a la clave del elemento.

¿Qué problema se presenta cuando dos claves diferentes producen el mismo valor al aplicarles la función hash?. Desbordamiento de búfer. Colisión. Corrupción de memoria. Pérdida de datos.

¿Qué papel juega la operación módulo (%) en el proceso de inserción en una tabla hash?. Convierte la clave en una cadena de texto. Garantiza que el índice resultante esté dentro del tamaño de la tabla. Elimina automáticamente las colisiones. Ordena los elementos por valor de hash.

Relaciona: Direccionamiento cerrado, encadenamiento separado o hashing abierto. Colisión. Direccionamiento abierto.

Relaciona: Sondeo lineal. Sondeo cuadrático. Doble Hasheo.

En el encadenamiento separado (separate chaining), ¿dónde se almacenan los registros que colisionan en el mismo índice?. En una nueva tabla hash independiente. En la siguiente casilla vacía del array principal. En una lista enlazada asociada a esa casilla del array. Se descartan y no se almacenan.

¿Cuál es la principal diferencia entre direccionamiento abierto y encadenamiento separado?. En direccionamiento abierto las colisiones se almacenan en listas externas. En direccionamiento abierto todos los registros se almacenan directamente en el array principal. El encadenamiento separado no permite colisiones. El direccionamiento abierto requiere más memoria por el uso de listas.

En sondeo lineal, ¿cómo se determina la siguiente posición a probar cuando hay una colisión?. Se usa una segunda función hash completamente diferente. Se prueba la posición actual más un incremento constante (normalmente 1). Se incrementa cuadráticamente: 1, 4, 9, 16... Se busca en una lista enlazada asociada.

¿Qué indica un factor de carga alto en una tabla hash?. Que la tabla está casi llena y es más probable que ocurran colisiones. Que la función hash es de mala calidad. Que la tabla tiene pocos elementos y muchas posiciones vacías. Que se está usando el método incorrecto de resolución de colisiones.