language agnostic - example - ¿Qué son hashtables y hashmaps y sus casos de uso típicos?
hashtable vs hashmap (5)
Recientemente me encontré con estos términos pocas veces, pero estoy bastante confundido sobre cómo funcionan y cuándo se implementan normalmente.
Bueno, piensa en eso de esta manera.
Si usa una matriz, una estructura de datos simple basada en índices y la llena con elementos aleatorios, encontrar una entrada en particular resulta ser una operación cada vez más costosa a medida que la llena de datos, ya que básicamente debe comenzar 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, normalmente recurrirá a ordenar la matriz y utilizar una búsqueda binaria. Esto, sin embargo, mientras aumenta la velocidad de búsqueda de un valor existente, hace que la inserción de nuevos valores sea lenta, ya que necesita mover los elementos existentes cuando necesite 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 como índice en la matriz, y aquí es donde almacena la entrada.
Una tabla hash gira en torno a 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 EE. UU. Sería un código postal -> nombre tipo de asociación. La función reduce la clave, pero no considera los datos.
Por lo tanto, cuando inserta algo en la tabla hash, la función reduce la clave a un número, que se utiliza como índice en esta matriz (vacía), y aquí es donde almacena los datos, tanto la clave como los datos asociados.
Luego, más adelante, desea encontrar una entrada particular para la que conoce la clave, de modo que ejecute la tecla a través de la misma función, obtenga su clave hash y vaya a ese lugar 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 económica que la búsqueda lineal.
Una tabla hash típica no tiene una cantidad infinita de elementos disponibles para el almacenamiento, por lo que el número se reduce generalmente a un índice que se ajusta al tamaño de la matriz. Una forma de hacerlo 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 correlacionará directamente con un índice, y el índice 10-19 se reducirá a 0-9 nuevamente, y así sucesivamente.
Algunas teclas 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 normales, por ejemplo). Si hay una coincidencia completa, desestime los datos nuevos (ya existen) o los sobrescribe (reemplaza los datos anteriores por esa clave) o los agrega (hash multivaluado). Si no hay coincidencia, lo que significa que aunque las claves hash eran idénticas, las claves reales no, por lo general se encuentra una nueva ubicación para almacenar esa clave + datos.
La resolución de colisión tiene muchas implementaciones, y la más simple es ir al siguiente elemento vacío en la matriz. Esta simple solución tiene otros problemas, por lo que encontrar el algoritmo de resolución correcto también es un buen ejercicio para hashtables.
Las tablas también pueden crecer, si se llenan completamente (o cerca de), 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 su nuevo ubicaciones.
La función que reduce la clave de 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.
Hay un buen artículo de wikipedia disponible sobre el tema también, aquí .
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).
La respuesta de Lassevk es muy buena, pero podría contener un poco de detalle. Aquí está el resumen ejecutivo. Estoy omitiendo intencionalmente cierta información relevante que puede ignorar de forma segura el 99% del tiempo.
No hay diferencia importante entre tablas hash y hash maps el 99% del tiempo.
Las tablas Hash son mágicas
Seriamente. Es una estructura de datos mágica que garantiza tres cosas . (Hay excepciones. Puede ignorarlas en gran medida, aunque aprenderlas algún día podría serle útil).
1) Todo en la tabla hash es parte de un par: hay una clave y un valor . Usted ingresa y extrae datos especificando la clave en 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(key,value) , get(key) , contains(key) y remove(key) son todos realmente rápidos.
3) ¡Las tablas hash genéricas fallan al hacer algo que no está en el n. ° 2 ! (Por "fallo", queremos decir que son tremendamente lentos).
¿Cuándo usamos tablas hash?
Usamos tablas hash cuando su magia se ajusta a nuestro problema.
Por ejemplo, el almacenamiento en caché con frecuencia termina usando una tabla hash; por ejemplo, digamos que tenemos 45,000 estudiantes en una universidad y algún proceso necesita conservar los registros de todos ellos. Si rutinariamente se refiere al estudiante por número de identificación, entonces un ID => student caché de ID => student tiene un excelente sentido. La operación que está optimizando para este caché es una búsqueda rápida .
Los hash también son extraordinariamente útiles para almacenar las relaciones entre los datos cuando no quieres ir por completo y alterar los objetos por sí mismos. Por ejemplo, durante el registro del curso, podría ser una buena idea relacionar a los estudiantes con las clases que están tomando. Sin embargo, por la razón que sea, es posible que no desee que el objeto del alumno lo sepa. Use un hash studentToClassRegistration y guárdelo mientras hace lo que necesite hacer.
También constituyen una primera opción bastante buena para una estructura de datos, excepto cuando necesita hacer una de las siguientes cosas:
Cuándo no usar tablas hash
Iteramos sobre los elementos . Las tablas hash normalmente no hacen la iteración muy bien. (Genéricos, es decir. Las implementaciones particulares a veces contienen listas vinculadas que se usan para hacer que iterar sobre ellas aspire menos. Por ejemplo, en Java, LinkedHashMap permite iterar sobre claves o valores rápidamente).
Clasificación. Si no puede iterar, la clasificación también es un dolor real.
Pasando de valor a clave . Use dos tablas hash. Créeme, acabo de ahorrarte mucho dolor.
Puede encontrar aquí toda la información necesaria.
si está hablando en términos de Java, ambas son colecciones que permiten la adición, eliminación y actualización de objetos y usan internamente algoritmos Hasing.
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 libres de subprocesos, mientras que las asignaciones de hash no son seguras.
Además de la sincronización, el mecanismo interno para almacenar y recuperar objetos es hash en ambos casos.
Si necesita ver cómo funciona Hashing, recomendaría un poco de búsqueda en Google en los Structers de datos y técnicas de hash.