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

Sé que un mapa es una estructura de datos que asigna claves a valores. ¿No es un diccionario igual? ¿Cuál es la diferencia entre un mapa y un diccionario ¹ ?

_{1. No estoy preguntando cómo se definen en el lenguaje X o Y (que parece ser lo que generalmente la gente pregunta aquí en SO), quiero saber cuál es su diferencia en teoría.}

Dos términos para la misma cosa:

• "Mapa" es utilizado por Java, C ++
• "Diccionario" es utilizado por .Net, Python
• PHP utiliza la "matriz asociativa"

"Mapa" es el término matemático correcto, pero se evita porque tiene un significado separado en la programación funcional .

Algunos idiomas usan otros términos ("Objeto" en Javascript, "Hash" en Ruby, "Tabla" en Lua) , pero todos tienen significados separados en la programación también, así que los evitaría.

Ver aquí para más información.

Uno es un término antiguo para el otro. Típicamente, el término "diccionario" se usaba antes de que el término matemático "mapa" se afianzara. Además, los diccionarios tienden a tener un tipo de cadena clave, pero eso no es 100% cierto en todas partes.

Mis 2 centavos

Dictionary es una clase abstracta en Java, mientras que Map es una interfaz. Dado que Java no admite múltiples herencias, si una clase extiende Diccionario, no puede extender ninguna otra clase.

Por lo tanto, se introdujo la interfaz de Mapa.

La clase de diccionario está obsoleta y se prefiere el uso de Map.

La respuesta a esta pregunta es complicada porque los programadores han visto que los términos tienen significados más específicos en lenguajes o sistemas particulares que han usado, pero la pregunta pide una comparación agnóstica del lenguaje "en teoría", que estoy entendiendo en términos de Ciencias de la Computación .

La terminología explicada

Las listas del Diccionario de Ciencias de la Computación de la Universidad de Oxford :

diccionario de cualquier estructura de datos que represente un conjunto de elementos que puedan admitir la inserción y eliminación de elementos, así como probar la membresía

• Por ejemplo, tenemos un conjunto de elementos {A, B, C, D ...} que hemos podido insertar y podríamos comenzar a eliminar, y podemos preguntar "¿está presente C?" .

Sin embargo, la noción de mapa de Computing Science se basa en el mapeo de términos lingüísticos matemáticos , que el Diccionario de Oxford define como:

mapeo Una operación que asocia cada elemento de un conjunto dado (el dominio) con uno o más elementos de un segundo conjunto (el rango).

• Como tal, una estructura de datos del mapa proporciona una manera de pasar de elementos de un conjunto dado , conocidos como " claves " en el mapa, a uno o más elementos en el segundo conjunto, conocidos como los " valores " asociados .
• El aspecto "... o más elementos en el segundo conjunto" puede ser soportado por una implementación es de dos maneras distintas:
  • Muchas implementaciones de mapas imponen la unicidad de las claves y solo permiten que cada clave se asocie con un valor, pero ese valor podría ser una estructura de datos que contenga muchos valores de un tipo de datos más simple, por ejemplo, {{1, {"uno" , "ichi"}, {2, {"two", "ni"}}} ilustra valores que consisten en pares de cadenas.
  • Otras implementaciones de mapeo permiten claves duplicadas, cada mapeo a los mismos o diferentes valores, lo que satisface funcionalmente el caso de "asocia ... cada elemento [clave] ... con ... más [de un] [valor] elementos". Por ejemplo, {{1, "uno"}, {1, "ichi"}, {2, "dos"}, {2, "ni"}}.

Diccionario y mapa contrastados

Entonces, utilizando la estricta terminología de Comp Sci anterior, un diccionario es solo un mapa si la interfaz admite operaciones adicionales que no se requieren en cada diccionario:

• la capacidad de almacenar elementos con componentes clave y de valor distintos

• la capacidad de recuperar los valores dados solo la clave

Un giro trivial:

• una interfaz de mapa podría no admitir directamente una prueba de si un par {clave, valor} está en el contenedor, lo cual es pedagógicamente un requisito de un diccionario donde los elementos son pares {clave, valor}; Es posible que un mapa ni siquiera tenga una función para probar una clave, pero en el peor de los casos puede ver si un intento de recuperación de valor por clave tiene éxito o falla, luego, si le importa, puede verificar si la clave recuperó un valor esperado.

Comunícate sin ambigüedades a tu audiencia

⚠ A pesar de todo lo anterior, si usa el diccionario en el estricto significado de la Ciencia de la Computación explicado anteriormente, no espere que su audiencia lo siga al principio, o se sorprenda cuando comparta y defienda la terminología. Las otras respuestas a esta pregunta (y sus votos positivos) muestran la probabilidad de que "diccionario" sea sinónimo de "mapa" en la experiencia de la mayoría de los programadores. Trate de elegir la terminología que se entenderá más ampliamente y sin ambigüedades: por ejemplo

• contenedor asociativo : cualquier contenedor que almacene pares clave / valor con recuperación de valor y borrado por clave
• mapa hash : una implementación de tabla hash de un contenedor asociado
• conjunto hash que impone claves únicas : una implementación de tabla hash de un diccionario que almacena elementos / valores sin tratarlos como que contienen componentes clave / valor distintos, en los que no se pueden insertar duplicados de los elementos
• balance del mapa de árbol binario que admite clave duplicada : ...

Referencia cruzada de terminología de ciencia ficción con implementaciones específicas

Biblioteca estándar de C ++

• mapas: map, multimap, unordered_map,unordered_multimap
• otros diccionarios especializados: set, multiset, unordered_set,unordered_multiset
• nota: con iteradores o std::findpuede borrar un elemento de prueba y para ser miembro de array, vector, list, dequeetc, pero las interfaces de contenedores no apoyan directamente que debido a la búsqueda de un elemento es espectacularmente ineficaz en O (N), en algunos casos de inserción / borrado está ineficiente, y el soporte de esas operaciones socava la API deliberadamente limitada que implica el contenedor, por ejemplo, deques solo debe admitir borrar / pop en la parte delantera y trasera y no en términos de alguna tecla. Tener que hacer más trabajo en el código para organizar la búsqueda suavemente alienta al programador a cambiar a una estructura de datos de contenedor con una búsqueda más eficiente.

... puede agregar otros idiomas más tarde / no dude en editar en ...

Por lo general, supongo que un mapa está respaldado por una tabla hash; Connota una tienda desordenada. Los diccionarios connotan una tienda ordenada.

Hay un diccionario basado en árboles llamado Trie .

En Lisp, podría verse así:

(a (n (d t)) n d )

Que encapsula las palabras:

• una
• y
• hormiga
• un
• anuncio

El recorrido desde la parte superior hasta la hoja produce una palabra.

Realmente no es lo mismo. Los mapas son un subconjunto de diccionario. El diccionario se define aquí como tener las funciones insertar, eliminar y buscar. El mapa utilizado por Java (de acuerdo con esto ) es un diccionario con el requisito de que la asignación de teclas a valores se asigne estrictamente como una función uno a uno. Un diccionario puede tener más de un mapa clave a un valor, o un mapa clave a varios valores (como encadenar en una tabla de hasthtable), por ejemplo, búsquedas de hashtag de Twitter.

Como un ejemplo más del "mundo real", buscar una palabra en un diccionario puede darnos varias definiciones para la misma palabra, y cuando encontramos una entrada que nos señala a otra entrada (ver otra palabra), varias palabras para la misma lista de definiciones. En el mundo real, los mapas son mucho más amplios, lo que nos permite tener ubicaciones para nombres o nombres para coordenadas, pero también podemos encontrar un vecino más cercano u otros atributos (poblaciones, etc.), por lo que en mi humilde opinión podría haber argumentos para una mayor expansión de es posible que el tipo de mapa tenga implementaciones basadas en gráficos, pero sería mejor asumir siempre solo el par clave-valor, especialmente porque el vecino más cercano y otros atributos del valor podrían ser solo miembros de datos del valor.

Los mapas de Java, a pesar del requisito uno a uno, pueden implementar algo más parecido a un diccionario generalizado si el valor se generaliza como una colección en sí misma, o si los valores son meramente referencias a colecciones almacenadas en otro lugar.

Recuerde que los mantenedores de Java no son los mantenedores de las definiciones ADT, y que las decisiones de Java son específicamente para Java.

Otros términos para este concepto que son bastante comunes: matriz asociativa y hash.

Sí, son lo mismo, puede agregar "Matriz asociativa" a la mezcla.

el uso Hashtable o una Hashoferta se refiere a la implementación.

así que en un nivel puramente teórico.

Un diccionario es un valor que se puede usar para localizar un valor vinculado. Un mapa es un valor que proporciona instrucciones sobre cómo ubicar otros valores

todas las colecciones que permiten el acceso no lineal (es decir, solo obtener primero o obtener el último) son un Mapa, ya que incluso un Array simple tiene un índice que se asigna al valor correcto. Entonces, mientras que un Diccionario es un Tipo de mapa, los mapas son un rango mucho más amplio de funciones posibles.

En la práctica, generalmente es la función de mapeo que define el nombre, por lo que un HashMap es una estructura de datos mapeada que utiliza un algoritmo de hash para vincular la clave con el valor, mientras que un diccionario no especifica cómo se vinculan las claves con un valor por lo que podría almacenarse a través de una lista vinculada, árbol o cualquier otro algoritmo. desde el final del uso, generalmente no le importa cuál es el algoritmo solo que funcionan, por lo que usa un diccionario genérico y solo cambia a una de las otras estructuras solo cuando necesita prever el tipo de algoritmo

Estos son dos términos diferentes para el mismo concepto.
Hashtabley HashMaptambién se refieren al mismo concepto.

La principal diferencia es que un Mapa requiere que todas las entradas (valor y par de claves) tengan una clave única. Si se producen colisiones, es decir, cuando una nueva entrada tiene la misma clave que una entrada ya en la colección, se requiere el manejo de colisiones.

Por lo general, manejamos las colisiones usando el encadenamiento separado . O sondeo lineal .

Un diccionario permite que varias entradas se vinculen a la misma clave.

Cuando un mapa ha implementado el encadenamiento separado, tiende a parecerse a un diccionario.