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

Hash es una estructura de datos extremadamente mal nombrada donde el programador ha confundido la interfaz con la implementación ( y fue demasiado perezoso 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 valores (no necesariamente únicos).

Una tabla hash es una implementación posible 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.

Una implementación de este tipo tiene dos propiedades importantes:

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

(Para una clave para ser hash 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 ordenamiento en las claves – 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 resumen: 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.

Comentarios

• Para dar un ejemplo en C ++, las plantillas de contenedor asociativo estándar no podrían ' t implementarse como hashes, aunque el próximo estándar tendrá lo que son efectivamente tablas hash. Ellos ' se denominan unordered_map para mostrar lo que hacen en lugar de lo que son.
• «corregir» según que autoridad En algunos lenguajes, como Ruby y Perl, el nombre oficial — lea “correcto” para estas estructuras es “hash”.
• @nohat: Note mi uso de comillas. Además, he explicado por qué el nombre está mal elegido, ¿no es así? Entonces, si necesita una autoridad, diré que es por la autoridad de la policía informática teórica.
• Curiosamente, en Ruby 1.9, en realidad es imposible implementar el Hash con una tabla hash, ya que Ruby 1.9 Hash es preserva el orden de inserción mientras que una tabla hash no lo hace. Entonces, en Ruby 1.9, el nombre Hash no ' ni siquiera refleja la implementación.
• @hippietrail Estás equivocado, primero, esas son descripciones objetivas. Después de todo, califico por qué el nombre es deficiente y poco apropiado (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í que no sea acortar el nombre. Y te equivocas con el «diccionario»: 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.

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

Comentarios

• Hash también es un ADT. HashTable es una implementación de Hash
• @Sairam Creo que es mucho más común que ' hash ' signifique una función hash en lugar de una tabla hash.
• @jk En realidad, el " hash " es el resultado de aplicar una " función / algoritmo hash " a alguna entrada. Una " tabla hash " o " mapa hash " omehoe relaciona un objeto hash con algún objeto (objeto en una forma genérica, no limitado a OOP)
• Hay lenguajes que usan ' Hash ' para referirse a una estructura de tipo diccionario en lugar de solo a la operación de la función hash. Ruby, por ejemplo .

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.

Comentarios

• Hash también es un ADT. ¿Existe alguna diferencia específica entre Hash y Dictionary ADT?
• @Sairam: No, un hash es el resultado de un cierto tipo de algoritmo (función hash).

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 tabla hash que utiliza 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 dará un valor como salida. Luego, inserte ese valor en la memoria o en el índice de matriz.

es decir, KEY => HASH FUNCTION => VALUE

Supongo que uno es directo mientras que el otro no es «t. Es posible que las funciones hash tampoco sean perfectas y, a veces, pueden proporcionar un índice que haga referencia al valor incorrecto. Pero eso se puede corregir.

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