¿Cuál es la diferencia entre un hash y un diccionario?

41

¿Cuál es la diferencia entre Hash y Dictionary ?

Desde un fondo de scripting, siento que son similares, pero quería descubrir las diferencias exactas. Googlear no me ayudó mucho.

    
pregunta Sairam 28.12.2010 - 08:33

4 respuestas

86

Hash es una estructura de datos con un nombre muy deficiente donde el programador ha confundido la interfaz con la implementación ( y era demasiado vago para escribir el nombre completo, es decir, HashTable en lugar de recurrir a una abreviatura, Hash ).

Dictionary es el nombre "correcto" de la interfaz (= ADT ), es decir, un contenedor asociativo que asigna claves (generalmente únicas) a (no necesariamente necesariamente únicas) ) valores.

Una tabla hash es una posible implementación de un diccionario de este tipo que proporciona características de acceso bastante buenas (en términos de tiempo de ejecución) y, por lo tanto, a menudo es la implementación predeterminada.

Tal implementación tiene dos propiedades importantes:

  1. las claves deben ser hashable y igualdad comparable .
  2. las entradas no aparecen en ningún orden en particular en el diccionario.

(Para que una clave sea hashable significa que podemos calcular un valor numérico a partir de una clave que luego se usa como un índice en una matriz).

Existen implementaciones alternativas de la estructura de datos del diccionario que imponen un ordenamiento en las claves; a menudo se denomina diccionario ordenado (y generalmente se implementa en términos de árbol de búsqueda, aunque existen otras implementaciones eficientes).

Para resumir: un diccionario es un ADT que asigna claves a valores. Hay varias implementaciones posibles de este ADT, de las cuales la tabla hash es una. Hash es un nombre inapropiado, pero en contexto es equivalente a un diccionario que se implementa en términos de una tabla hash.

    
respondido por el Konrad Rudolph 28.12.2010 - 11:09
7

"Diccionario" es el nombre del concepto. Una tabla hash es una posible implementación.

    
respondido por el dan_waterworth 28.12.2010 - 08:39
7

Un diccionario es el término colectivo dado para cualquier implementación de estructura de datos utilizada para búsquedas / inserciones rápidas. Esto se puede lograr / implementar utilizando una variedad de estructuras de datos como tabla hash, listas de salto, árbol rb, etc. Una tabla hash es una estructura de datos específica útil para muchos propósitos, incluida la implementación de un diccionario.

    
respondido por el aufather 28.12.2010 - 08:42
5

Un diccionario usa una clave para hacer referencia al valor directamente dentro de una matriz asociativa .

es decir, (KEY => VALUE)

Un hash se describe más a menudo como una hash table que utiliza una función hash para calcular la posición en la memoria (o más fácilmente una array) donde estará el valor. El hash tomará la CLAVE como entrada y le dará un valor como salida. Luego inserte ese valor en el índice de memoria o matriz.

es decir, KEY => HASH FUNCTION => VALUE

Supongo que uno es directo mientras que el otro no lo es. Las funciones de hash tampoco pueden ser perfectas y, en ocasiones, pueden proporcionar un índice que haga referencia al valor incorrecto. Pero eso se puede corregir.

El mejor lugar para mirar: Wikipedia ( matriz asociativa y tabla hash )

    
respondido por el Ross 28.12.2010 - 10:51

Lea otras preguntas en las etiquetas

Comentarios Recientes

Son cosas diferentes ... a menos que pertenezcan al mismo sistema. A lo sumo, son sistemas diferentes que comparten llamadas de función comunes. La razón por la que son diferentes es porque no nos gusta golpear algo que aún no hemos evaluado. Entonces no nos gusta cuando se bloquea. Eso es todo. La matemática regex es ligeramente diferente. El tipo Hash en realidad tiene que ser inicializado, así: typedef Hash {int nIndex, char * width, int len; regexstring ByModule, Módulo; } HKeyChainRoot; Y luego se ejecuta... Lee mas