A menudo he escuchado a la gente hablar sobre el hash y el hash de mapas y tablas hash. Yo quería saber qué son y cuál es el mejor uso de ellos.

InformationsquelleAutor Saif Bechan | 2010-04-07

4 Comentarios

  1. 45

    Primero que debes quizá a leer este artículo.

    Cuando se utilizan listas y usted está buscando un artículo especial que normalmente tiene que iterar sobre la lista completa. Esto es muy costoso cuando se tienen grandes listas.

    Una tabla hash puede ser mucho más rápido, bajo las mejores circunstancias, podrá obtener el elemento que está buscando con un solo access.

    ¿Cómo es el trabajo? Como un diccionario … cuando usted está buscando la palabra «hashtable» en un diccionario, no está comenzando con la primera palabra en ‘una’. Pero en lugar de ir directamente hacia adelante a la letra ‘h’. Luego ‘ha’, ‘tiene’, y así sucesivamente, hasta que encontró su palabra. Usted está utilizando un índice dentro de su diccionario para acelerar la búsqueda.

    Una tabla hash que hace básicamente el mismo. Cada elemento se obtiene un índice único (el llamado hash). Utilice este hash para las búsquedas. El hash puede ser un índice normal de la lista enlazada. Por ejemplo, el hash podría ser un número como 2130 lo que significa que usted debe buscar en la posición 2130 en su lista. Una búsqueda en un conocido índice dentro de una lista normal es muy fácil y rápido.

    El problema de todo el enfoque es el llamado hash function que asigna este índice para cada elemento. Cuando usted está buscando un artículo, usted debería ser capaz de calcular el índice de antemano. Al igual que en un diccionario real, donde vemos que la palabra ‘hash’ comienza con la letra ‘h’ y por lo tanto conocer la posición aproximada.

    Una buena función hash proporciona hashcodes que son uniformemente distrubuted, en el espacio de todas las posibles hashcodes. Y, por supuesto, se intenta evitar collisions. Una colisión se produce cuando dos elementos diferentes de obtener el mismo hashcode.

    En C# por ejemplo, cada objeto tiene un GetHashcode() método que proporciona un hash (no necesariamente único). Esto puede ser usado para las búsquedas y de la clasificación con el en su diccionario.

    Cuando empiece a usar tablas de hash debe tener siempre en mente, que usted manejar colisiones correctamente. Puede suceder muy fácilmente en grandes tablas de hash que dos objetos tienen el mismo hash (tal vez su sobrecarga de GetHashcode() es defectuoso, tal vez, algo más sucedió).

    • Un bien explicado respuesta
    • ¿Qué quiere decir «usted (debe) manejar colisiones correctamente»? Como fas, como yo sé, simplemente debemos tratar de minimizar las colisiones por escribir buenas funciones de hash (para un mejor rendimiento). Pero, no hay necesidad de «manejar colisiones». Si los hash chocan, se acaba de recurrir al siguiente nivel de control haciendo es igual comparación.
    • Las funciones de Hash acaba de hacer la mezcla. No existe el «siguiente nivel». Que es lo que quiero decir por «tomar el cuidado de las colisiones». Cuando hay más de una coincidencia, usted tiene que seleccionar, por ejemplo en igual comparación.
    • Quiero decir que el intrínseca de la colección de HashMap utiliza hashCode función como primer nivel de verificación. Si dos elementos tienen el mismo hashCode, HashMap se continúe con el siguiente nivel de comprobar que es igual de verificación. Así, nuestro trabajo es escribir un decente implementación de hashCode para nuestro objeto personalizado.
    • HashMap es Java específico, no sé el comportamiento exacto. Pero la pregunta que en general no es Java específico. Pero tienes razón, algunas implementaciones pueden diferir y ya tiene un built-en el siguiente nivel de verificación.
  2. 9

    Básicamente, un HashMap permite almacenar elementos con los identificadores. Se almacenan en un formato de tabla con el identificador del algoritmo hash utilizando un algoritmo de hash.

    Por lo general, son más eficientes para recuperar los elementos de búsqueda de árboles, etc.

    Puede que encuentre útil esta información: http://www.relisoft.com/book/lang/pointer/8hash.html

    La esperanza de que esto ayude,

    Chris

  3. 6

    Hash (en el noncryptographic sentido) es una manta de plazo para tomar una entrada y, a continuación, produciendo una salida de identificar con. Un ejemplo trivial de un hash es la adición de la suma de las letras de una cadena, yo.e:

    f(abc) = 6
    

    Tenga en cuenta que este trivial hash de plan de crear una colisión entre las cuerdas abc, bca, ae, etc. Un efectivo de hash esquema de producir diferentes valores para cada cadena, naturalmente.

    Hashmaps y tablas de hash son datastructures (como los arrays y listas), que utiliza el hash para almacenar datos. En una tabla hash, un hash es producido, ya sea de una clave, o desde el objeto en sí mismo) que determina el lugar en la tabla se almacena el objeto. Esto significa que mientras el usuario de la tabla hash es consciente de la clave, recuperar el objeto es extremadamente rápido.

    En una lista, en comparación, sería necesario que de alguna manera la búsqueda por la lista para encontrar su objeto buscado. Esto también representa en la parte trasera de tablas de hash, que es que es muy complicado encontrar un objeto sin conocer la clave, debido a que cuando el objeto se almacena en la tabla no tiene relevancia a su valor ni cuando fue inputed.

    Hashmaps son similares a las tablas de hash, pero sólo un ejemplo de cada objeto está almacenado en él (por lo tanto no tiene que ser siempre, el objeto en sí mismo es la clave).

    Esto es, por supuesto, una explicación muy simple, así que le sugiero que lea en profundidad a partir de este punto. Espero no hacer ninguna tontería errores. =)

  4. 1

    Hashmap es utilizado para almacenar datos en los principales pares de valores. Podemos utilizar un hashmap para el almacenamiento de objetos en una aplicación y uso en la misma aplicación para almacenar, actualizar, eliminar valores. Hashmap clave y los valores se almacenan en un depósito para una entrada específica, esta entrada la ubicación se determina mediante la función Hash. Este hashcode función determina el hash donde se almacena el valor. La detallada explanantion de cómo hashmap obras se describe en este vídeo: https://youtu.be/iqYC1odZSNo

Dejar respuesta

Please enter your comment!
Please enter your name here