¿Qué son las tablas hash y los mapas hash y sus casos de uso típicos?

Question

Recientemente he encontrado estos términos varias veces, pero estoy bastante confundido sobre cómo funcionan y cuándo se implementan habitualmente.

Answer 1

Bueno, piénsalo de esta manera.

Si usa una matriz, una estructura de datos basada en un índice simple, y la llena con elementos aleatorios, encontrar una entrada en particular se convierte en una operación cada vez más costosa a medida que la llena con datos, ya que básicamente tiene que comience a buscar desde un extremo hacia el otro, hasta que encuentre el que desea.

Si desea obtener un acceso más rápido a los datos, puede recurrir a la ordenación de la matriz y utilizar una búsqueda binaria. Sin embargo, mientras aumenta la velocidad de búsqueda de un valor existente, la inserción de nuevos valores es lenta, ya que necesita mover los elementos existentes cuando necesita insertar un elemento en el medio.

Una tabla hash, por otro lado, tiene una función asociada que toma una entrada y la reduce a un número, una clave hash. Este número se usa luego como un índice en la matriz, y aquí es donde almacena la entrada.

Una tabla hash gira alrededor de una matriz, que inicialmente comienza vacía. Vacío no significa longitud cero, la matriz comienza con un tamaño, pero todos los elementos de la matriz no contienen nada.

Cada elemento tiene dos propiedades, datos y una clave que identifica los datos. Por ejemplo, una lista de códigos postales de los EE. UU. Sería un código postal - > nombre tipo de asociación. La función reduce la clave, pero no tiene en cuenta los datos.

Entonces, cuando inserta algo en la tabla hash, la función reduce la clave a un número, que se usa como un índice en esta matriz (vacía), y aquí es donde almacena los datos, tanto la clave como los asociados. datos.

Luego, más adelante, querrá encontrar una entrada particular para la que sepa la clave, así que ejecute la clave a través de la misma función, obtenga su clave hash, y vaya a ese lugar en particular en la tabla hash y recupere los datos. allí.

La teoría dice que la función que reduce su clave a una clave hash, ese número, es computacionalmente mucho más barata que la búsqueda lineal.

Una tabla hash típica no tiene un número infinito de elementos disponibles para el almacenamiento, por lo que el número se reduce típicamente más a un índice que se ajusta al tamaño de la matriz. Una forma de hacer esto es simplemente tomar el módulo del índice en comparación con el tamaño de la matriz. Para una matriz con un tamaño de 10, el índice 0-9 se asignará directamente a un índice, y el índice 10-19 se asignará de nuevo a 0-9, y así sucesivamente.

Algunas claves se reducirán al mismo índice que una entrada existente en la tabla hash. En este punto, las claves reales se comparan directamente, con todas las reglas asociadas con la comparación de los tipos de datos de la clave (es decir, la comparación de cadenas normal, por ejemplo). Si hay una coincidencia completa, o bien ignora los datos nuevos (ya existen) o sobrescribe (reemplaza los datos antiguos de esa clave), o los agrega (tabla hash multivalor). Si no hay ninguna coincidencia, lo que significa que aunque las claves hash eran idénticas, las claves reales no lo eran, generalmente se encuentra una nueva ubicación para almacenar esa clave + datos.

La resolución de colisiones tiene muchas implementaciones, y la más simple es ir al siguiente elemento vacío de la matriz. Sin embargo, esta solución simple tiene otros problemas, por lo que encontrar el algoritmo de resolución correcto también es un buen ejercicio para las tablas hash.

Las tablas hash también pueden crecer, si se llenan completamente (o casi), y esto generalmente se hace creando una nueva matriz del nuevo tamaño y calculando todos los índices una vez más, y colocando los elementos en la nueva matriz. en sus nuevas ubicaciones.

La función que reduce la clave a un número no produce un valor lineal, es decir. " AAA " se convierte en 1, luego " AAB " se convierte en 2, por lo que la tabla hash no está ordenada por ningún valor típico.

También hay un buen artículo de wikipedia disponible sobre el tema, aquí .

Answer 2

la respuesta de lassevk es muy buena, pero puede contener demasiados detalles. Aquí está el resumen ejecutivo. Estoy omitiendo intencionalmente cierta información relevante que puedes ignorar de manera segura el 99% del tiempo.

No hay una diferencia importante entre las tablas hash y los mapas hash el 99% del tiempo.

Las tablas hash son mágicas

En serio. Es una estructura de datos mágica que todos menos garantizan tres cosas . (Hay excepciones. Puede ignorarlas en gran medida, aunque aprenderlas algún día podría ser útil para usted).

1) Todo en la tabla hash es parte de un par: hay una clave y un valor . Usted ingresa y saca datos especificando la clave con la que está operando.

2) Si está haciendo algo con una sola tecla en una tabla hash, es increíblemente rápido . Esto implica que put (clave, valor) , get (key) , contiene (key) y remove (key) son todos muy rápidos.

3) ¡Las tablas hash genéricas no pueden hacer nada que no esté en la lista del # 2 ! (Por " error " ;, queremos decir que son increíblemente lentos.)

¿Cuándo usamos tablas hash?

Usamos tablas hash cuando su magia encaja en nuestro problema.

Por ejemplo, almacenamiento en caché con frecuencia termina usando una tabla hash; por ejemplo, digamos que tenemos 45,000 estudiantes en una universidad y que algún proceso debe conservar los registros de todos ellos. Si rutinariamente se refiere al estudiante por número de ID, entonces un ID = > estudiante caché tiene excelente sentido. La operación que está optimizando para este caché es búsqueda rápida .

Los elementos hash también son extraordinariamente útiles para almacenar relaciones entre datos cuando no quiere volverse loco y alterar los objetos en sí. Por ejemplo, durante el registro del curso, podría ser una buena idea poder relacionar a los estudiantes con las clases que están tomando. Sin embargo, por el motivo que sea, es posible que no desee que el Objeto del estudiante sepa sobre eso. Use un hash de studentToClassRegistration y manténgalo cerca mientras hace lo que necesita hacer.

También son una primera opción bastante buena para una estructura de datos , excepto cuando necesitas hacer una de las siguientes acciones:

Cuándo no usar tablas hash

Iterar sobre los elementos . Las tablas hash típicamente no hacen muy bien la iteración. (Las genéricas, es decir. Las implementaciones particulares a veces contienen listas vinculadas que se utilizan para hacer que la iteración sobre ellas sea menos importante. Por ejemplo, en Java, LinkedHashMap le permite iterar sobre claves o valores rápidamente).

Clasificación. Si no puedes iterar, la clasificación también es un dolor real.

Pasando de valor a clave . Utilice dos tablas hash. Confía en mí, acabo de ahorrarte mucho dolor.

Answer 3

si está hablando en términos de Java, ambas son colecciones que permiten la adición, eliminación y actualización de objetos y el uso de algoritmos de control interno.

La diferencia significativa, sin embargo, si hablamos en referencia a Java, es que las tablas hash están inherentemente sincronizadas y, por lo tanto, son seguras para subprocesos, mientras que los mapas hash no son una colección segura para subprocesos.

Además de la sincronización, el mecanismo interno para almacenar y recuperar objetos es el hash en ambos casos.

Si necesita ver cómo funciona el Hashing, recomendaría un poco de googlear en los Estructuradores de datos y las técnicas de hashing.

Answer 4

Hashtables / hashmaps asocian un valor (llamado 'clave' para propósitos de desambiguación) con otro valor. Puede pensarlos como una especie de diccionario (palabra: definición) o un registro de base de datos (clave: datos).