En informática , una matriz asociativa , un mapa , una tabla de símbolos o un diccionario es un tipo de datos abstracto que almacena una colección de pares (clave, valor) , de modo que cada clave posible aparece como máximo una vez en la colección. En términos matemáticos, una matriz asociativa es una función con dominio finito . [1] Admite operaciones de 'búsqueda', 'eliminación' e 'inserción'.
El problema del diccionario es el problema clásico de diseñar estructuras de datos eficientes que implementen matrices asociativas. [2] Las dos soluciones principales al problema del diccionario son las tablas hash y los árboles de búsqueda . [3] [4] [5] [6] A veces también es posible resolver el problema utilizando matrices direccionadas directamente , árboles de búsqueda binaria u otras estructuras más especializadas.
Muchos lenguajes de programación incluyen matrices asociativas como tipos de datos primitivos , mientras que muchos otros lenguajes proporcionan bibliotecas de software que admiten matrices asociativas. La memoria direccionable por contenido es una forma de compatibilidad directa a nivel de hardware para matrices asociativas.
Las matrices asociativas tienen muchas aplicaciones, incluidos patrones de programación fundamentales como la memorización y el patrón decorador . [7]
El nombre no proviene de la propiedad asociativa conocida en matemáticas, sino que surge de la asociación de valores con claves. No debe confundirse con los procesadores asociativos .
En una matriz asociativa, la asociación entre una clave y un valor a menudo se conoce como "mapeo"; la misma palabra también puede usarse para referirse al proceso de creación de una nueva asociación.
Las operaciones que normalmente se definen para un array asociativo son: [3] [4] [8]
Las matrices asociativas también pueden incluir otras operaciones, como determinar la cantidad de asignaciones o construir un iterador para recorrer todas las asignaciones. Para tales operaciones, el orden en el que se devuelven las asignaciones suele estar definido por la implementación.
Un mapa múltiple generaliza una matriz asociativa al permitir que múltiples valores se asocien con una sola clave. [9] Un mapa bidireccional es un tipo de datos abstracto relacionado en el que las asignaciones operan en ambas direcciones: cada valor debe estar asociado con una clave única y una segunda operación de búsqueda toma un valor como argumento y busca la clave asociada con ese valor.
Las operaciones de la matriz asociativa deben satisfacer varias propiedades: [8]
lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)lookup(k, new()) = fail, donde failes una excepción o valor predeterminadoremove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))remove(k, new()) = new()donde ky json claves, ves un valor, Des una matriz asociativa y new()crea una nueva matriz asociativa vacía.
Supongamos que el conjunto de préstamos que realiza una biblioteca está representado en una estructura de datos. Cada libro de una biblioteca puede ser prestado por un solo usuario a la vez. Sin embargo, un único usuario puede tener la posibilidad de retirar varios libros. Por lo tanto, la información sobre qué libros se han prestado a qué usuarios puede representarse mediante una matriz asociativa, en la que los libros son las claves y los usuarios son los valores. Utilizando la notación de Python o JSON , la estructura de datos sería:
{ "Orgullo y prejuicio" : "Alice" , "Cumbres borrascosas" : "Alice" , "Grandes esperanzas" : "John" } Una operación de búsqueda en la clave "Grandes esperanzas" devolvería "John". Si John devuelve su libro, eso provocaría una operación de eliminación, y si Pat solicita un libro, eso provocaría una operación de inserción, lo que llevaría a un estado diferente:
{ "Orgullo y prejuicio" : "Alice" , "Los hermanos Karamazov" : "Pat" , "Cumbres borrascosas" : "Alice" } Para diccionarios con muy pocas asignaciones, puede tener sentido implementar el diccionario utilizando una lista de asociación , que es una lista enlazada de asignaciones. Con esta implementación, el tiempo para realizar las operaciones básicas del diccionario es lineal en el número total de asignaciones. Sin embargo, es fácil de implementar y los factores constantes en su tiempo de ejecución son pequeños. [3] [10]
Otra técnica de implementación muy simple, que se puede utilizar cuando las claves están restringidas a un rango estrecho, es el direccionamiento directo a una matriz: el valor de una clave dada k se almacena en la celda A [ k ] de la matriz, o si no hay una asignación para k , entonces la celda almacena un valor centinela especial que indica la falta de una asignación. Esta técnica es simple y rápida, y cada operación de diccionario toma un tiempo constante. Sin embargo, el requisito de espacio para esta estructura es el tamaño de todo el espacio de claves, lo que la hace poco práctica a menos que el espacio de claves sea pequeño. [5]
Los dos enfoques principales para implementar diccionarios son una tabla hash o un árbol de búsqueda . [3] [4] [5] [6]
La implementación de propósito general más utilizada de una matriz asociativa es con una tabla hash : una matriz combinada con una función hash que separa cada clave en un "cubo" separado de la matriz. La idea básica detrás de una tabla hash es que acceder a un elemento de una matriz a través de su índice es una operación simple y de tiempo constante. Por lo tanto, la sobrecarga promedio de una operación para una tabla hash es solo el cálculo del hash de la clave, combinado con el acceso al cubo correspondiente dentro de la matriz. Como tal, las tablas hash generalmente funcionan en tiempo O(1) y generalmente superan las implementaciones alternativas.
Las tablas hash deben ser capaces de manejar colisiones : la asignación por la función hash de dos claves diferentes al mismo contenedor de la matriz. Los dos enfoques más extendidos para este problema son el encadenamiento separado y el direccionamiento abierto . [3] [4] [5] [11] En el encadenamiento separado, la matriz no almacena el valor en sí, sino que almacena un puntero a otro contenedor, normalmente una lista de asociación , que almacena todos los valores que coinciden con el hash. Por el contrario, en el direccionamiento abierto, si se encuentra una colisión de hash, la tabla busca un lugar vacío en una matriz para almacenar el valor de manera determinista, normalmente mirando la siguiente posición inmediata en la matriz.
El direccionamiento abierto tiene una tasa de errores de caché menor que el encadenamiento separado cuando la tabla está casi vacía. Sin embargo, a medida que la tabla se llena con más elementos, el rendimiento del direccionamiento abierto se degrada exponencialmente. Además, el encadenamiento separado utiliza menos memoria en la mayoría de los casos, a menos que las entradas sean muy pequeñas (menos de cuatro veces el tamaño de un puntero).
Otro enfoque común es implementar una matriz asociativa con un árbol de búsqueda binario autoequilibrado , como un árbol AVL o un árbol rojo-negro . [12]
En comparación con las tablas hash, estas estructuras tienen tanto fortalezas como debilidades. El rendimiento en el peor de los casos de los árboles binarios de búsqueda autoequilibrados es significativamente mejor que el de una tabla hash, con una complejidad temporal en notación O grande de O(log n ). Esto contrasta con las tablas hash, cuyo rendimiento en el peor de los casos implica que todos los elementos comparten un solo contenedor, lo que resulta en una complejidad temporal de O( n ). Además, y como todos los árboles binarios de búsqueda, los árboles binarios de búsqueda autoequilibrados mantienen sus elementos en orden. Por lo tanto, recorrer sus elementos sigue un patrón de menor a mayor, mientras que recorrer una tabla hash puede dar como resultado que los elementos estén en un orden aparentemente aleatorio. Debido a que están en orden, los mapas basados en árboles también pueden satisfacer consultas de rango (encontrar todos los valores entre dos límites) mientras que un mapa hash solo puede encontrar valores exactos. Sin embargo, las tablas hash tienen una complejidad temporal de caso promedio mucho mejor que los árboles binarios de búsqueda autoequilibrados de O(1), y su rendimiento en el peor de los casos es altamente improbable cuando se utiliza una buena función hash .
Se puede utilizar un árbol binario de búsqueda autoequilibrado para implementar los contenedores de una tabla hash que utiliza encadenamiento independiente. Esto permite una búsqueda constante en el caso promedio, pero asegura un rendimiento en el peor de los casos de O(log n ). Sin embargo, esto introduce una complejidad adicional en la implementación y puede causar un rendimiento aún peor para tablas hash más pequeñas, donde el tiempo empleado en insertar y equilibrar el árbol es mayor que el tiempo necesario para realizar una búsqueda lineal en todos los elementos de una lista enlazada o una estructura de datos similar. [13] [14]
Las matrices asociativas también se pueden almacenar en árboles binarios de búsqueda no balanceados o en estructuras de datos especializadas para un tipo particular de claves, como árboles de base , tries , matrices de Judy o árboles de van Emde Boas , aunque el rendimiento relativo de estas implementaciones varía. Por ejemplo, se ha descubierto que los árboles de Judy funcionan de manera menos eficiente que las tablas hash, mientras que las tablas hash cuidadosamente seleccionadas generalmente funcionan de manera más eficiente que los árboles de base adaptativos, con restricciones potencialmente mayores en los tipos de datos que pueden manejar. [15] Las ventajas de estas estructuras alternativas provienen de su capacidad para manejar operaciones de matriz asociativa adicionales, como encontrar la asignación cuya clave es la más cercana a una clave consultada cuando la consulta está ausente en el conjunto de asignaciones.
La definición básica de un diccionario no exige un orden. Para garantizar un orden fijo de enumeración, se suelen utilizar versiones ordenadas de la matriz asociativa. Un diccionario ordenado tiene dos sentidos:
<map>contenedor de C++. [16]Este último método es más común. Estos diccionarios ordenados se pueden implementar utilizando una lista de asociación , superponiendo una lista doblemente enlazada sobre un diccionario normal o moviendo los datos reales desde la matriz dispersa (desordenada) a una matriz densa ordenada por inserción.
Las matrices asociativas se pueden implementar en cualquier lenguaje de programación como un paquete y muchos sistemas de lenguaje las proporcionan como parte de su biblioteca estándar. En algunos lenguajes, no solo están integradas en el sistema estándar, sino que tienen una sintaxis especial, que a menudo utiliza subíndices similares a los de las matrices.
El soporte sintáctico integrado para matrices asociativas fue introducido en 1969 por SNOBOL4 , bajo el nombre de "tabla". TMG ofrecía tablas con claves de cadena y valores enteros. MUMPS hizo de las matrices asociativas multidimensionales, opcionalmente persistentes, su estructura de datos clave. SETL las admitía como una posible implementación de conjuntos y mapas. La mayoría de los lenguajes de programación modernos, comenzando con AWK e incluyendo Rexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language , Go y Lua , admiten matrices asociativas como un tipo de contenedor primario. En muchos más lenguajes, están disponibles como funciones de biblioteca sin sintaxis especial.
En Smalltalk , Objective-C , .NET , [20] Python , REALbasic , Swift , VBA y Delphi [21] se denominan diccionarios ; en Perl , Ruby y Seed7 se denominan hashes ; en C++ , C# , Java , Go , Clojure , Scala , OCaml , Haskell se denominan mapas (véase map (C++) , unordered_map (C++) y Map); en Common Lisp y Windows PowerShell , se denominan tablas hash (ya que ambos suelen utilizar esta implementación); en Maple y Lua, se denominan tablas . En PHP y R , todas las matrices pueden ser asociativas, excepto que las claves están limitadas a números enteros y cadenas. En JavaScript (véase también JSON ), todos los objetos se comportan como matrices asociativas con claves con valores de cadena, mientras que los tipos Map y WeakMap toman objetos arbitrarios como claves. En Lua, se utilizan como bloque de construcción primitivo para todas las estructuras de datos. En Visual FoxPro , se denominan colecciones . El lenguaje D también admite matrices asociativas. [22]
Muchos programas que utilizan matrices asociativas necesitarán almacenar esos datos en una forma más permanente, como un archivo de computadora . Una solución común a este problema es un concepto generalizado conocido como archivado o serialización , que produce una representación de texto o binaria de los objetos originales que se pueden escribir directamente en un archivo. Esto se implementa más comúnmente en el modelo de objetos subyacente, como .Net o Cocoa, que incluye funciones estándar que convierten los datos internos en texto. El programa puede crear una representación de texto completa de cualquier grupo de objetos llamando a estos métodos, que casi siempre ya están implementados en la clase de matriz asociativa base. [23]
Para los programas que utilizan conjuntos de datos muy grandes, este tipo de almacenamiento de archivos individuales no es adecuado y se requiere un sistema de gestión de bases de datos (DB). Algunos sistemas de DB almacenan de forma nativa matrices asociativas serializando los datos y luego almacenando esos datos serializados y la clave. Luego, las matrices individuales se pueden cargar o guardar desde la base de datos utilizando la clave para hacer referencia a ellas. Estos almacenamientos de clave-valor se han utilizado durante muchos años y tienen una historia tan larga como la de las bases de datos relacionales (RDB) más comunes, pero la falta de estandarización, entre otras razones, limitó su uso a ciertas funciones de nicho. Las RDB se utilizaron para estas funciones en la mayoría de los casos, aunque guardar objetos en una RDB puede ser complicado, un problema conocido como desajuste de impedancia relacional de objetos .
Después de aproximadamente 2010, la necesidad de bases de datos de alto rendimiento adecuadas para la computación en la nube y que coincidieran más estrechamente con la estructura interna de los programas que las utilizaban condujo a un renacimiento en el mercado de almacenamiento de clave-valor. Estos sistemas pueden almacenar y recuperar matrices asociativas de manera nativa, lo que puede mejorar en gran medida el rendimiento en flujos de trabajo comunes relacionados con la web.
