Hashes: Tablas, listas y mapas, ¿Oh, mi?

Question

He estado tratando de encontrar algunas definiciones de hormigón (no académicos) para los distintos tipos de estructuras de datos hash, específicamente tablas hash, listas hash y mapas hash. Las búsquedas en línea proporcionan muchos enlaces útiles a todos estos, pero nunca dan definiciones claras de cuándo es apropiado usar cada uno sobre los demás.

(1) Desde el punto de vista práctico, ¿cuál es la diferencia entre estos 3?

(2) ¿Cómo difieren los tiempos de ejecución de sus operaciones? ¿Hay instancias claras cuando se debe usar o evitar uno sobre los otros tipos de hash?

(3) ¿Cómo se relaciona cada uno de estos con el ADT del mapa? ¿Son todas implementaciones diferentes de ella, o diferentes bestias en total?

¡Gracias por cualquier idea aquí!

Answer 1

Hay una estructura de datos abstracta que contiene la asignación entre claves y valores. Tiene varios nombres diferentes, incluidos Map, Dictionary, Table, Association Table, y más.

Las operaciones más básicas que deberían ser compatibles con esta estructura de datos son agregar, eliminar y recuperar un valor, dada su clave asociada. Existen variaciones y adiciones en torno a este concepto básico; por ejemplo, algunas estructuras admiten iterar sobre todos los pares clave-valor, algunas estructuras admiten múltiples valores por clave, etc. También existe una diferencia en la complejidad del tiempo y el espacio entre las diversas implementaciones.

De las múltiples implementaciones disponibles para esta estructura de datos, algunas de las más populares utilizan hash functions para tiempos de acceso rápido. Esas implementaciones a veces se llaman con el nombre Hash Table o Hash Map, puede read more about them in Wikipedia. El rendimiento también varía entre las implementaciones de la tabla hash, y algunas alcanzan una amortización O (1) complejidad de inserción y acceso (por el precio de una gran cantidad de espacio utilizado).

Una lista de hash, por otro lado, es una cosa diferente, y es más sobre el uso de una estructura de datos, que sus estructuras reales. Una lista hash suele ser solo una lista regular de valores hash, nada especial al respecto. Se usa al verificar la integridad de una gran cantidad de datos; en ese caso, permite que varios fragmentos de datos se verifiquen de forma independiente, lo que permite corregir o recuperar solo los fragmentos defectuosos. Esto es opuesto al uso de un solo valor hash para analizar toda la información, en cuyo caso una falla significa que todos los datos deben ser reparados o recuperados nuevamente.