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

Respuestas:

92

Hashes una estructura de datos con un nombre extremadamente pobre donde el programador ha confundido la interfaz con la implementación ( y era demasiado vago para escribir el nombre completo, es decir, HashTablerecurrió a una abreviatura Hash).

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

Una tabla hash es una posible implementación de dicho diccionario 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 tienen que ser hashable y la igualdad comparable .
  2. las entradas no aparecen en ningún orden particular en el diccionario.

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

Existen implementaciones alternativas de la estructura de datos del diccionario que imponen un orden en las teclas; esto a menudo se denomina diccionario ordenado (y generalmente se implementa en términos de un á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. Hashes un nombre inapropiado pero en contexto es equivalente a un diccionario que se implementa en términos de una tabla hash.

Konrad Rudolph
fuente
44
Para dar un ejemplo en C ++, las plantillas de contenedor asociativo estándar no se podrían implementar como hashes, aunque el siguiente estándar tendrá lo que efectivamente son tablas hash. Están llamados unordered_mapa mostrar lo que hacen en lugar de lo que son.
David Thornley
66
¿"Correcto" según qué autoridad? En algunos idiomas, como Ruby y Perl, el nombre oficial —leído “correcto” para estas estructuras es “hash”.
nohat
11
@nohat: Note mi uso de comillas. Por otra parte, me he explicado por qué el nombre está mal escogida, no tengo yo? Entonces, si necesita una autoridad, le diré que es por la autoridad de la policía teórica de la informática.
Konrad Rudolph
99
Curiosamente, en Ruby 1.9, en realidad es imposible implementar la Hashclase con una tabla hash, ya que Ruby 1.9 Hashpreserva el orden de inserción mientras que una tabla hash no. Entonces, en Ruby 1.9, el nombre Hashya ni siquiera refleja la implementación.
Jörg W Mittag
77
@hippietrail Estás equivocado, primero, esas son descripciones objetivas. Después de todo, califico por qué los nombres son malos y son incorrectos (ver más abajo). "Demasiado vago" es una licencia artística de mi parte, pero el punto sigue siendo que la razón para acortar el nombre es intrínseca, es decir, no hay ninguna razón para usar un nombre corto aquí aparte de acortar el nombre. Y está equivocado acerca del "diccionario": ese es simplemente el nombre oficial de la estructura de datos. Su definición de "diccionario" es incorrecta en el contexto de la informática, y el nombre es anterior a Python por décadas.
Konrad Rudolph el
8

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

dan_waterworth
fuente
1
Hash también es un ADT. HashTable es una implementación de un Hash
Sairam
3
@Sairam Creo que es mucho más común que 'hash' signifique una función hash en lugar de una tabla hash.
jk.
@jk En realidad, el "hash" es el resultado de aplicar una "función / algoritmo hash" a alguna entrada. Una "tabla hash" o un "mapa hash" omehoe relaciona un objeto hashable con algún objeto (objeto en una forma genérica, no limitada a OOP)
johannes
Hay idiomas que usan 'Hash' para referirse a una estructura tipo diccionario en lugar de solo a la operación de la función hash. Ruby, por ejemplo .
Sean Burton el
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 omisión, á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.

aufather
fuente
Hash también es un ADT. ¿Hay alguna diferencia específica entre Hash y Dictionary ADT?
Sairam
2
@Sairam: No, un hash es la salida de un cierto tipo de algoritmo (función hash).
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 tabla hash que usa una función hash para calcular la posición en la memoria (o más fácilmente una matriz) donde estará el valor. El hash tomará la CLAVE como entrada y le dará un valor como salida. Luego conecte ese valor a la memoria o al índice de la matriz.

es decir KEY => HASH FUNCTION => VALUE

Supongo que uno es directo mientras que el otro no. Las funciones de hash pueden no ser perfectas y a veces pueden proporcionar un índice que hace referencia al valor incorrecto. Pero eso se puede corregir.

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

Ross
fuente