Hispanopedia Wiki
Articulo de referencia

Matriz asociativa

En informática , un array asociativo , un almacén clave-valor , un mapa , una tabla de símbolos o un diccionario es un tipo de dato abstracto que almacena una colección de pares...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , un array asociativo , un almacén clave-valor , un mapa , una tabla de símbolos o un diccionario es un tipo de dato 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, un array asociativo 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 del diseño de estructuras de datos eficientes que implementan arreglos asociativos. [ 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 arreglos de direccionamiento directo , árboles de búsqueda binaria u otras estructuras más especializadas.

Muchos lenguajes de programación incluyen los arreglos asociativos como tipos de datos primitivos , mientras que otros muchos proporcionan bibliotecas de software que los admiten. La memoria direccionable por contenido es una forma de soporte directo a nivel de hardware para los arreglos asociativos.

Los arreglos asociativos tienen muchas aplicaciones, incluyendo patrones de programación fundamentales como la memorización [ 7 ] y el patrón decorador [ 8 ] . 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 .

Operaciones

En una matriz asociativa, la relación entre una clave y un valor se conoce a menudo como "mapeo"; la misma palabra también puede utilizarse para referirse al proceso de creación de una nueva asociación.

Las operaciones que se suelen definir para un array asociativo son: [ 3 ] [ 4 ] [ 9 ]

Insertar o colocar
agregar uno nuevo(kmiy,valtúmi){\displaystyle (clave,valor)}Agrega un par a la colección, asignando la clave a su nuevo valor. Cualquier asignación existente se sobrescribe. Los argumentos de esta operación son la clave y el valor.
Eliminar o borrar
quitar un(kmiy,valtúmi){\displaystyle (clave,valor)}Extrae un par de claves de la colección, desvinculando una clave dada de su valor. El argumento de esta operación es la clave.
Buscar, encontrar u obtener
Encuentra el valor (si lo hay) asociado a una clave determinada. El argumento de esta operación es la clave, y el valor se devuelve. Si no se encuentra ningún valor, algunas funciones de búsqueda generan una excepción , mientras que otras devuelven un valor predeterminado (como cero, nulo o un valor específico pasado al constructor).

Los arreglos asociativos también pueden incluir otras operaciones, como determinar el número de asignaciones o construir un iterador para recorrer todas las asignaciones. Para dichas operaciones, el orden en que se devuelven las asignaciones suele depender de la implementación.

Un multimapa generaliza un array asociativo al permitir que múltiples valores se asocien con una sola clave. [ 10 ] Un mapa bidireccional es un tipo de dato abstracto relacionado en el que las asignaciones operan en ambas direcciones: cada valor debe asociarse 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.

Propiedades

Las operaciones del arreglo asociativo deben satisfacer varias propiedades: [ 9 ]

  • lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)
  • lookup(k, new()) = faildonde failes una excepción o un valor predeterminado
  • remove(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 un array asociativo y new()crea un nuevo array asociativo vacío.

Ejemplo

Supongamos que el conjunto de préstamos realizados por una biblioteca se representa en una estructura de datos. Cada libro de la biblioteca puede ser prestado por un solo usuario a la vez. Sin embargo, un mismo usuario puede tomar prestados varios libros. Por lo tanto, la información sobre qué libros están prestados a qué usuarios puede representarse mediante un array asociativo, donde 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" : "Alicia" , "Cumbres borrascosas" : "Alicia" , "Grandes esperanzas" : "Juan" }

Una búsqueda en la clave "Grandes esperanzas" devolvería "John". Si John devuelve su libro, se produciría una eliminación, y si Pat toma prestado un libro, se produciría una inserción, lo que daría lugar a un estado diferente:

{ "Orgullo y prejuicio" : "Alicia" , "Los hermanos Karamazov" : "Pat" , "Cumbres borrascosas" : "Alicia" }

Implementación

Para diccionarios con muy pocas relaciones, puede ser conveniente implementar el diccionario utilizando una lista de asociación , que es una lista enlazada de relaciones. Con esta implementación, el tiempo para realizar las operaciones básicas del diccionario es lineal con respecto al número total de relaciones. Sin embargo, es fácil de implementar y los factores constantes en su tiempo de ejecución son pequeños. [ 3 ] [ 11 ]

Otra técnica de implementación muy sencilla, utilizable cuando las claves están restringidas a un rango estrecho, es el direccionamiento directo a un array: el valor de una clave k dada se almacena en la celda A [ k ] del array, o si no hay una correspondencia para k , la celda almacena un valor centinela especial que indica la falta de correspondencia. Esta técnica es simple y rápida, ya que cada operación de diccionario requiere un tiempo constante. Sin embargo, el espacio requerido 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 ]

Implementaciones de tablas hash

Este gráfico compara el número promedio de fallos de caché de la CPU necesarios para buscar elementos en tablas hash grandes (que superan con creces el tamaño de la caché) con el encadenamiento y el sondeo lineal . El sondeo lineal ofrece un mejor rendimiento debido a una mayor localidad de referencia , aunque a medida que la tabla se llena, su rendimiento se degrada drásticamente.

La implementación más común de propósito general para un arreglo asociativo es una tabla hash : un arreglo combinado con una función hash que separa cada clave en un "cubo" independiente del arreglo. La idea básica de una tabla hash es que acceder a un elemento del arreglo mediante su índice es una operación simple y de tiempo constante. Por lo tanto, la sobrecarga promedio de una operación en una tabla hash se limita al cálculo del hash de la clave, junto con el acceso al cubo correspondiente dentro del arreglo. De esta manera, las tablas hash suelen tener una complejidad temporal de O(1) y, por lo general, superan el rendimiento de otras implementaciones.

Las tablas hash deben poder manejar colisiones : el mapeo por la función hash de dos claves diferentes al mismo cubo del array. Los dos enfoques más extendidos para este problema son el encadenamiento separado y el direccionamiento abierto . [ 3 ] [ 4 ] [ 5 ] [ 12 ] En el encadenamiento separado, el array no almacena el valor en sí, sino que almacena un puntero a otro contenedor, generalmente 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 espacio vacío en un array para almacenar el valor de manera determinista, generalmente mirando la siguiente posición inmediata en el array.

El direccionamiento abierto presenta una menor tasa de fallos de caché que el encadenamiento separado cuando la tabla está prácticamente 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).

Implementaciones de árboles

Árboles de búsqueda binaria autoequilibrados

Otro enfoque común es implementar una matriz asociativa con un árbol de búsqueda binaria autoequilibrado , como un árbol AVL o un árbol rojo-negro . [ 13 ]

En comparación con las tablas hash, estas estructuras presentan tanto ventajas como desventajas. El rendimiento en el peor de los casos de los árboles de búsqueda binaria autoequilibrados es significativamente mejor que el de una tabla hash, con una complejidad temporal en notación Big O de O(log n ). Esto contrasta con las tablas hash, cuyo rendimiento en el peor de los casos implica que todos los elementos compartan un único depósito, lo que resulta en una complejidad temporal de O( n ). Además, y al igual que todos los árboles de búsqueda binaria, los árboles de búsqueda binaria 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 resultar en elementos aparentemente en orden aleatorio. Debido a que están ordenados, 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 promedio mucho mejor que los árboles de búsqueda binaria 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 de búsqueda binaria autoequilibrado para implementar los cubetas de una tabla hash que utiliza encadenamiento separado. Esto permite una búsqueda constante en el caso promedio, pero garantiza 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 provocar 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. [ 14 ] [ 15 ]

Otros árboles

Los arreglos asociativos también pueden almacenarse en árboles de búsqueda binaria desequilibrados o en estructuras de datos especializadas para un tipo particular de claves, como árboles radix , tries , arreglos Judy o árboles van Emde Boas , aunque el rendimiento relativo de estas implementaciones varía. Por ejemplo, se ha descubierto que los árboles Judy tienen un rendimiento menos eficiente que las tablas hash, mientras que las tablas hash cuidadosamente seleccionadas generalmente tienen un rendimiento más eficiente que los árboles radix adaptativos, con restricciones potencialmente mayores en los tipos de datos que pueden manejar. [ 16 ] Las ventajas de estas estructuras alternativas provienen de su capacidad para manejar operaciones adicionales de arreglos asociativos, como encontrar el mapeo cuya clave es la más cercana a una clave consultada cuando la consulta no está en el conjunto de mapeos.

Comparación

Diccionario ordenado

La definición básica de un diccionario no impone un orden. Para garantizar un orden fijo de enumeración, a menudo se utilizan versiones ordenadas del array asociativo. Existen dos sentidos de diccionario ordenado:

Esta última opción es más común. Dichos diccionarios ordenados pueden implementarse utilizando una lista de asociación , superponiendo una lista doblemente enlazada sobre un diccionario normal, o moviendo los datos reales del arreglo disperso (no ordenado) a uno denso ordenado por inserción.

Soporte de idiomas

Los arreglos asociativos se pueden implementar en cualquier lenguaje de programación como un paquete, y muchos sistemas de lenguajes los incluyen en su biblioteca estándar. En algunos lenguajes, no solo están integrados en el sistema estándar, sino que tienen una sintaxis especial, que a menudo utiliza índices similares a los de los arreglos.

El soporte sintáctico integrado para matrices asociativas fue introducido en 1969 por SNOBOL4 , bajo el nombre de "tabla". [ 21 ] 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 scripting modernos, comenzando con AWK [ 22 ] e incluyendo Rexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language , Go y Lua , admiten matrices asociativas como un tipo de contenedor principal. En muchos más lenguajes, están disponibles como funciones de biblioteca sin sintaxis especial.

En Smalltalk , Objective-C , .NET , [ 23 ] Python , REALbasic , Swift , VBA y Delphi [ 24 ] se llaman diccionarios ; en Perl y Ruby se llaman hashes ; en C++ , C# , Java , Go , Clojure , Scala , OCaml , Haskell se llaman mapas (ver map (C++) , unordered_map (C++) y Map); en Common Lisp y Windows PowerShell , se llaman tablas hash (ya que ambos suelen usar esta implementación); en Maple y Lua, se llaman tablas . En PHP y R , todos los arrays pueden ser asociativos, excepto que las claves están limitadas a enteros y cadenas. En JavaScript (ver también JSON ), todos los objetos se comportan como arrays asociativos con claves de valor de cadena, mientras que los tipos Map y WeakMap toman objetos arbitrarios como claves. En Lua, se utilizan como el 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. [ 25 ]

Almacenamiento permanente

Muchos programas que utilizan matrices asociativas necesitarán almacenar esos datos de forma más permanente, como en un archivo informático . Una solución común a este problema es un concepto generalizado conocido como archivado o serialización , que produce una representación textual o binaria de los objetos originales que se puede escribir directamente en un archivo. Esto se implementa con mayor frecuencia 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 textual completa de cualquier grupo de objetos llamando a estos métodos, que casi siempre ya están implementados en la clase base de la matriz asociativa. [ 26 ]

Para programas que utilizan conjuntos de datos muy grandes, este tipo de almacenamiento de archivos individuales no es apropiado, y se requiere un sistema de gestión de bases de datos (DB). Algunos sistemas DB almacenan de forma nativa matrices asociativas serializando los datos y luego almacenando esos datos serializados y la clave. Posteriormente, las matrices individuales se pueden cargar o guardar desde la base de datos utilizando la clave para referirse a ellas. Estos almacenes 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 específicas. Las RDB se utilizaban 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 objeto-relacional .

A partir de 2010, la necesidad de bases de datos de alto rendimiento, aptas para la computación en la nube y que se adaptaran mejor a la estructura interna de los programas que las utilizan, impulsó un resurgimiento del mercado de almacenamiento clave-valor. Estos sistemas pueden almacenar y recuperar matrices asociativas de forma nativa, lo que mejora considerablemente el rendimiento en los flujos de trabajo web habituales.

Véase también

Referencias

  1. ↑ Collins, Graham; Syme, Donald (1995). "Una teoría de mapas finitos". En Schubert, E. Thomas; Windley, PJ; Alves-Foss, J. (eds.). Demostración de teoremas en lógica de orden superior y sus aplicaciones . Lecture Notes in Computer Science. Vol. 971. Berlín, Heidelberg: Springer (publicado el 2 de junio de 2005). pp. 122–137 . doi : 10.1007/3-540-60275-5_61 . ISBN   978-3-540-60275-0Consultado el 30 de junio de 2026 .
  2. ↑ Andersson, Arne (1989). "Límites óptimos en el problema del diccionario". Actas del Simposio sobre Algoritmos Óptimos . Lecture Notes in Computer Science. Vol. 401. Springer. pp. 106–114 . doi : 10.1007/3-540-51859-2_10 . ISBN   978-3-540-51859-4.
  3. 1 2 3 4 5 Goodrich, Michael T. ; Tamassia, Roberto (2006), "§9.1 El tipo de datos abstracto Map", Estructuras de datos y algoritmos en Java (4.ª ed.), Wiley, págs. 368–371 , ISBN   978-0-471-73884-8, OCLC 61822092 
  4. 1 2 3 4 Mehlhorn, Kurt ; Sanders, Peter (2008), "4. Tablas hash y matrices asociativas", Algoritmos y estructuras de datos: La caja de herramientas básica (PDF) , Springer, págs. 81–98 , doi : 10.1007/978-3-540-77978-0_4 , ISBN  978-3-540-77977-3, OCLC 272306813 , archivado (PDF) del original el 2 de agosto de 2014 
  5. 1 2 3 4 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "11. Tablas hash", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill , págs. 221–252 , ISBN   0-262-03293-7.
  6. 1 2 Dietzfelbinger, M.; Karlin, A.; Mehlhorn, K.; Meyer auf der Heide, F.; Rohnert, H.; Tarjan, RE (agosto de 1994). "Dynamic Perfect Hashing: Upper and Lower Bounds" (PDF) . SIAM J. Comput . 23 (4): 738–761 . doi : 10.1137/S0097539791194094 . Archivado del original (PDF) el 4 de marzo de 2016.
  7. ↑ Michie, Donald (1968) .Funciones de 'memoria' y aprendizaje automático" (PDF) . Nature . 218 (5136): 19– 22. Bibcode : 1968Natur.218...19M . doi : 10.1038/218019a0 . S2CID 4265138 . 
  8. ↑ Goodrich y Tamassia (2006) , págs. 597–599.
  9. 1 2 Black, Paul E.; Stewart, Rob (2 de noviembre de 2020). "diccionario" . Diccionario de algoritmos y estructuras de datos . Recuperado el 26 de enero de 2022 .
  10. ↑ Goodrich y Tamassia (2006) , págs. 389–397.
  11. ↑ "¿Cuándo debo usar una tabla hash en lugar de una lista de asociación?" . lisp-faq/part2. 1996-02-20.
  12. ↑ Klammer, F. ; Mazzolini, L. (2006), "Pathfinders for associative maps", Ext. Abstracts GIS-l 2006 , GIS-I, pp. 71– 74 .
  13. ↑ Adams, Joel; Nyhoff, Larry (2003). "Árboles en STL" (PDF) . C++ : una introducción a la informática (3.ª ed.). Pearson. ISBN   978-0-13-091426-2. OCLC 959939097 . La biblioteca de plantillas estándar ... algunos de sus contenedores — las plantillas set<T>, map<T1, T2>, multiset<T> y multimap<T1, T2> — generalmente se construyen utilizando un tipo especial de árbol de búsqueda binaria autoequilibrado llamado árbol rojo-negro . 
  14. ↑ Knuth, Donald (1998). "6. Búsqueda §6.4 Hashing". El arte de la programación informática . Vol. 3: Ordenación y búsqueda (2.ª ed.). Addison-Wesley. págs. 513–558 . ISBN    0-201-89685-0.
  15. ↑ Probst, Mark (30 de abril de 2010). "Búsqueda lineal frente a búsqueda binaria" . Recuperado el 20 de noviembre de 2016 .
  16. ↑ Alvarez, Victor; Richter, Stefan; Chen, Xiao; Dittrich, Jens (abril de 2015). "Una comparación de árboles radix adaptativos y tablas hash". 2015 IEEE 31.ª Conferencia Internacional sobre Ingeniería de Datos . Seúl, Corea del Sur: IEEE. págs. 1227–38 . doi : 10.1109/ICDE.2015.7113370 . ISBN  978-1-4799-7964-6. S2CID 17170456 . 
  17. ↑ "std::map" . en.cppreference.com .
  18. ↑ "Clase OrderedDictionary (System.Collections.Specialized)" . Documentación de MS .
  19. ↑ "LinkedHashMap" .
  20. ↑ "Colecciones — Tipos de datos de contenedor — Documentación de Python 3.9.0a3" . docs.python.org .
  21. ↑ Griswold, Ralph E. (agosto de 1978). «Historia de los lenguajes de programación SNOBOL». ACM SIGPLAN Notices . 13 (8): 275–308 , véase pág. 289. doi : 10.1145/960118.808393 . Las tablas, que proporcionaban una especie de estructura de datos asociativa, se habían sugerido en varias ocasiones, en particular por Doug McIlroy y Mike Shapiro. Fue la persistencia de Doug la que dio como resultado su incorporación a SNOBOL4 a mediados de 1969, en una etapa muy avanzada del desarrollo de SNOBOL4...
  22. ↑ "/usr/doc/awk" . Repositorio de Historia de Unix § Investigación-V7 . Líneas 935-9 – vía github. Los elementos de la matriz pueden nombrarse con valores no numéricos, lo que le da a awk una capacidad similar a la memoria asociativa de las tablas Snobol.
  23. ↑ "Clase Dictionary<TKey, TValue>" . MSDN.
  24. ↑ "System.Generics.Collections.TDictionary — Documentación de la API de RAD Studio" . docwiki.embarcadero.com . Consultado el 18 de abril de 2017 .
  25. ↑ "Arreglos asociativos, el lenguaje de programación D" . Digital Mars.
  26. ↑ "Guía de programación de archivos y serializaciones" , Apple Inc., 2012
  • Diccionario de algoritmos y estructuras de datos del NIST: Arreglo asociativo
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Tipo de datos abstractoEn informática , un tipo abstracto de datos ( ADT ) es un modelo matemático para los tipos de datos , definido por su comportamiento ( semántica ) ...Colección (tipo de datos abstractos)Colección (tipo de datos abstractos)En programación informática , una colección es un tipo de datos abstracto que es una agrupación de elementos que pueden usarse de manera polimórfica .Par nombre-valorEjemplo de un formulario web con pares nombre-valor Un par nombre-valor , también conocido como par atributo-valor , par clave-valor o par campo-va...{\displaystyle f(x)=x^{2}+1;}Function (mathematics)In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y.[1] The set X is called the domain of the ...Dominio de una funciónUna función f de X a Y. El conjunto de puntos en el óvalo rojo X es el dominio de f . Gráfica de la función raíz cuadrada de valor real , f ( x ) =...