Matriz associativa - Associative array
Na ciência da computação , uma matriz associativa , mapa , tabela de símbolos ou dicionário é um tipo de dado abstrato composto de uma coleção de pares (chave, valor) , de modo que cada chave possível apareça no máximo uma vez na coleção. Não deve ser confundido com Processadores Associativos
As operações associadas a este tipo de dados permitem:
- adicione um par à coleção;
- remova um par da coleção;
- modificar um par existente;
- lookup um valor associado a uma chave particular.
A implementação de matrizes associativas apresenta o problema do dicionário , um problema clássico da ciência da computação: a tarefa de projetar uma estrutura de dados que mantém um conjunto de dados durante as operações de 'pesquisa', 'exclusão' e 'inserção'. As duas principais soluções para o problema do dicionário são uma tabela hash e uma árvore de pesquisa . Em alguns casos, também é possível resolver o problema usando matrizes endereçadas diretamente , árvores de pesquisa binárias ou outras estruturas mais especializadas.
Muitas linguagens de programação incluem matrizes associativas como tipos de dados primitivos e estão disponíveis em bibliotecas de software para muitos outros. A memória endereçável por conteúdo é uma forma de suporte direto em nível de hardware para matrizes associativas.
As matrizes associativas têm muitos aplicativos, incluindo padrões de programação fundamentais , como memoização e o padrão de decorador .
O nome não vem da propriedade associativa conhecida em matemática. Em vez disso, surge do fato de que associamos valores a chaves.
Operações
Em uma matriz associativa, a associação entre uma chave e um valor é freqüentemente conhecida como "mapeamento", e a mesma palavra mapeamento também pode ser usada para se referir ao processo de criação de uma nova associação.
As operações que geralmente são definidas para uma matriz associativa são:
- Adicionar ou inserir : adiciona um novo par à coleção, mapeando a nova chave para seu novo valor. Os argumentos para esta operação são a chave e o valor.
- Reatribuir : substitui o valor em um dos pares que já estão na coleção, mapeando uma chave existente para um novo valor. Tal como acontece com uma inserção, os argumentos para esta operação são a chave e o valor.
- Remover ou excluir : remove um par da coleção, desmapeando uma determinada chave de seu valor. O argumento para esta operação é a chave.
- Lookup : encontre o valor (se houver) que está vinculado a uma determinada chave. O argumento para esta operação é a chave e o valor é retornado da operação. Se nenhum valor for encontrado, algumas implementações de matriz associativa levantam uma exceção , enquanto outras criam um par com a chave fornecida e o valor padrão do tipo de valor (zero, recipiente vazio ...).
Freqüentemente, em vez de adicionar ou reatribuir, há uma única operação de conjunto que adiciona um novo par, se ainda não houver um, e o reatribui.
Além disso, as matrizes associativas também podem incluir outras operações, como determinar o número de mapeamentos ou construir um iterador para percorrer todos os mapeamentos. Normalmente, para tal operação, a ordem na qual os mapeamentos são retornados pode ser definida pela implementação.
Um multimapa generaliza uma matriz associativa, permitindo que vários valores sejam associados a uma única chave. Um mapa bidirecional é um tipo de dado abstrato relacionado no qual os mapeamentos operam em ambas as direções: cada valor deve ser associado a uma chave exclusiva e uma segunda operação de pesquisa pega um valor como um argumento e procura a chave associada a esse valor.
Exemplo
Suponha que o conjunto de empréstimos feitos por uma biblioteca seja representado em uma estrutura de dados. Cada livro em uma biblioteca pode ser retirado apenas por um único usuário da biblioteca por vez. No entanto, um único usuário pode fazer check-out de vários livros. Portanto, as informações sobre quais livros são retirados para quais clientes podem ser representadas por uma matriz associativa, na qual os livros são as chaves e os clientes são os valores. Usando notação de Python ou JSON , a estrutura de dados seria:
{
"Pride and Prejudice": "Alice",
"Wuthering Heights": "Alice",
"Great Expectations": "John"
}
Uma operação de pesquisa na chave "Grandes expectativas" retornaria "John". Se John devolver seu livro, isso causaria uma operação de exclusão, e se Pat fizer check-out de um livro, isso causaria uma operação de inserção, levando a um estado diferente:
{
"Pride and Prejudice": "Alice",
"The Brothers Karamazov": "Pat",
"Wuthering Heights": "Alice"
}
Implementação
Para dicionários com um número muito pequeno de mapeamentos, pode fazer sentido implementar o dicionário usando uma lista de associação , uma lista vinculada de mapeamentos. Com essa implementação, o tempo para realizar as operações básicas do dicionário é linear no número total de mapeamentos; entretanto, é fácil de implementar e os fatores constantes em seu tempo de execução são pequenos.
Outra técnica de implementação muito simples, utilizável quando as chaves são restritas a um intervalo estreito, é o endereçamento direto em uma matriz: o valor de uma determinada chave k é armazenado na célula da matriz A [ k ], ou se não houver mapeamento para k então, a célula armazena um valor sentinela especial que indica a ausência de um mapeamento. Além de simples, essa técnica é rápida: cada operação do dicionário leva um tempo constante. No entanto, o requisito de espaço para essa estrutura é o tamanho de todo o keyspace, tornando-o impraticável, a menos que o keyspace seja pequeno.
As duas principais abordagens para a implementação de dicionários são uma tabela hash ou uma árvore de pesquisa .
Implementações de tabela de hash
A implementação de propósito geral usada com mais frequência de uma matriz associativa é com uma tabela hash : uma matriz combinada com uma função hash que separa cada chave em um "depósito" separado da matriz. A ideia básica por trás de uma tabela hash é que acessar um elemento de uma matriz por meio de seu índice é uma operação simples e em tempo constante. Portanto, a sobrecarga média de uma operação para uma tabela hash é apenas o cálculo do hash da chave, combinado com o acesso ao depósito correspondente dentro da matriz. Como tal, as tabelas hash geralmente funcionam no tempo O (1) e superam as alternativas na maioria das situações.
As tabelas de hash precisam ser capazes de lidar com colisões : quando a função de hash mapeia duas chaves diferentes para o mesmo balde do array. As duas abordagens mais comuns para esse problema são o encadeamento separado e o endereçamento aberto . No encadeamento separado, a matriz não armazena o valor em si, mas armazena um ponteiro para outro contêiner, geralmente uma lista de associação , que armazena todos os valores correspondentes ao hash. Por outro lado, no endereçamento aberto, se uma colisão de hash for encontrada, a tabela buscará um ponto vazio em uma matriz para armazenar o valor de maneira determinística, geralmente olhando para a próxima posição imediata na matriz.
O endereçamento aberto tem uma taxa de perda de cache menor do que o encadeamento separado quando a tabela está quase vazia. No entanto, à medida que a tabela é preenchida com mais elementos, o desempenho do endereçamento aberto se degrada exponencialmente. Além disso, o encadeamento separado usa menos memória na maioria dos casos, a menos que as entradas sejam muito pequenas (menos de quatro vezes o tamanho de um ponteiro).
Implementações de árvore
Árvores binárias de busca com equilíbrio automático
Outra abordagem comum é implementar uma matriz associativa com uma árvore de pesquisa binária de autobalanceamento , como uma árvore AVL ou uma árvore vermelha e preta .
Em comparação com as tabelas de hash, essas estruturas têm vantagens e fraquezas. O desempenho de pior caso de árvores de busca binária de autobalanceamento é significativamente melhor do que o de uma tabela hash, com uma complexidade de tempo em notação grande O de O (log n ). Isso contrasta com as tabelas hash, cujo desempenho no pior caso envolve todos os elementos que compartilham um único depósito, resultando em complexidade de tempo O ( n ). Além disso, como todas as árvores de pesquisa binárias, as árvores de pesquisa binária com autobalanceamento mantêm seus elementos em ordem. Portanto, percorrer seus elementos segue um padrão do menor para o maior, enquanto percorrer uma tabela hash pode resultar em elementos em uma ordem aparentemente aleatória. No entanto, as tabelas hash têm uma complexidade de tempo médio de caso muito melhor do que as árvores de busca binária de auto-equilíbrio de O (1), e seu desempenho no pior caso é altamente improvável quando uma boa função hash é usada.
É importante notar que uma árvore de pesquisa binária de autobalanceamento pode ser usada para implementar os depósitos para uma tabela hash que usa encadeamento separado. Isso permite a pesquisa de constante de caso médio, mas garante um desempenho de O (log n ) no pior caso . No entanto, isso introduz complexidade extra na implementação e pode causar desempenho ainda pior para tabelas de hash menores, onde o tempo gasto para inserir e balancear a árvore é maior do que o tempo necessário para realizar uma pesquisa linear em todos os elementos de um link lista ou estrutura de dados semelhante.
Outras arvores
Matrizes associativas também podem ser armazenadas em árvores de pesquisa binárias desequilibradas ou em estruturas de dados especializadas para um tipo particular de chaves, como árvores radix , tentativas , matrizes Judy ou árvores van Emde Boas , embora a capacidade desses métodos de implementação em comparação com tabelas de hash varia; por exemplo, as árvores Judy continuam indicadas para executar com uma quantidade menor de eficiência do que as tabelas hash, enquanto as tabelas hash cuidadosamente selecionadas geralmente funcionam com maior eficiência em comparação com as árvores radix adaptativas, com restrições potencialmente maiores sobre os tipos de dados que podem manipular. As vantagens dessas estruturas alternativas vêm de sua capacidade de lidar com operações além das básicas de um array associativo, como encontrar o mapeamento cuja chave é a mais próxima de uma chave consultada, quando a própria consulta não está presente no conjunto de mapeamentos.
Comparação
| Estrutura de dados subjacente | Pesquisa ou exclusão | Inserção | Ordenado | ||
|---|---|---|---|---|---|
| média | pior caso | média | pior caso | ||
| Tabela de hash | O (1) | O ( n ) | O (1) | O ( n ) | Não |
| Árvore de pesquisa binária de auto-equilíbrio | O (log n ) | O (log n ) | O (log n ) | O (log n ) | sim |
| árvore de pesquisa binária desequilibrada | O (log n ) | O ( n ) | O (log n ) | O ( n ) | sim |
| Recipiente sequencial de pares chave-valor (por exemplo, lista de associação ) |
O ( n ) | O ( n ) | O (1) | O (1) | Não |
Dicionário pedido
A definição básica do dicionário não exige uma ordem. Para garantir uma ordem fixa de enumeração, geralmente são usadas versões ordenadas da matriz associativa. Existem dois sentidos em um dicionário ordenado:
- A ordem de enumeração é sempre determinística para um determinado conjunto de chaves por classificação. Esse é o caso das implementações baseadas em árvore, um representante sendo o
<map>contêiner de C ++. - A ordem de enumeração é independente de chave e, em vez disso, é baseada na ordem de inserção. Esse é o caso do "dicionário ordenado" no .NET Framework e Python .
O último sentido de dicionários ordenados é mais comumente encontrado. Eles podem ser implementados usando uma lista de associação ou sobrepondo uma lista duplamente vinculada no topo de um dicionário normal. A última abordagem, conforme usada pelo CPython antes da versão 3.6, tem a vantagem de manter a complexidade potencialmente melhor de outra implementação. CPython 3.6+ faz dicionários ordenados dividindo a tabela hash em um array ordenado por inserção de pares kv e um array esparso ("tabela hash") de índices.
Suporte de linguas
Os arrays associativos podem ser implementados em qualquer linguagem de programação como um pacote e muitos sistemas de linguagem os fornecem como parte de sua biblioteca padrão. Em algumas linguagens, eles não são apenas integrados ao sistema padrão, mas têm uma sintaxe especial, geralmente usando subscritos semelhantes a array.
O suporte sintático integrado para matrizes associativas foi introduzido em 1969 por SNOBOL4 , sob o nome de "tabela". TMG ofereceu tabelas com chaves de string e valores inteiros. O MUMPS fez arrays associativos multidimensionais, opcionalmente persistentes, sua estrutura de dados chave. SETL os apoiava como uma possível implementação de conjuntos e mapas. A maioria das linguagens de script modernas, começando com AWK e incluindo Rexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language , Go e Lua , oferece suporte a matrizes associativas como um tipo de contêiner primário. Em muitas outras linguagens, eles estão disponíveis como funções de biblioteca sem sintaxe especial.
Em Smalltalk , Objective-C , .NET , Python , REALbasic , Swift , VBA e Delphi eles são chamados de dicionários ; em Perl , Ruby e Seed7 eles são chamados de hashes ; em C ++ , Java , Go , Clojure , Scala , OCaml , Haskell eles são chamados de mapas (veja map (C ++) , unordered_map (C ++) e Map); no Common Lisp e no Windows PowerShell , eles são chamados de tabelas de hash (já que ambos normalmente usam essa implementação); no Maple e na Lua, eles são chamados de tabelas . No PHP , todos os arrays podem ser associativos, exceto que as chaves são limitadas a inteiros e strings. Em JavaScript (consulte também JSON ), todos os objetos se comportam como matrizes associativas com chaves com valor de string, enquanto os tipos Map e WeakMap aceitam objetos arbitrários como chaves. Em Lua, eles são usados como o bloco de construção primitivo para todas as estruturas de dados. No Visual FoxPro , eles são chamados de Coleções . A linguagem D também oferece suporte para matrizes associativas.
Armazenamento permanente
Muitos programas que usam matrizes associativas, em algum momento, precisarão armazenar esses dados de uma forma mais permanente, como em um arquivo de computador . Uma solução comum para esse problema é um conceito generalizado conhecido como arquivamento ou serialização , que produz um texto ou representação binária dos objetos originais que podem ser gravados diretamente em um arquivo. Isso é mais comumente implementado no modelo de objeto subjacente, como .Net ou Cocoa, que incluem funções padrão que convertem os dados internos em formato de texto. O programa pode criar uma representação de texto completa de qualquer grupo de objetos chamando esses métodos, que quase sempre já estão implementados na classe base de matriz associativa.
Para programas que usam conjuntos de dados muito grandes, esse tipo de armazenamento de arquivo individual não é apropriado e um sistema de gerenciamento de banco de dados (DB) é necessário. Alguns sistemas de banco de dados armazenam matrizes associativas nativamente, serializando os dados e, em seguida, armazenando esses dados serializados e a chave. Arrays individuais podem ser carregados ou salvos do banco de dados usando a chave para se referir a eles. Esses armazenamentos de valores-chave têm sido usados por muitos anos e têm uma história tão longa quanto o banco de dados relacional (RDBs) mais comum , mas a falta de padronização, entre outros motivos, limitou seu uso a certas funções de nicho. RDBs foram usados para essas funções na maioria dos casos, embora salvar objetos em um RDB possa ser complicado, um problema conhecido como incompatibilidade de impedância relacional de objeto .
Depois de c. Em 2010 , a necessidade de bancos de dados de alto desempenho adequados para computação em nuvem e uma correspondência mais próxima com a estrutura interna dos programas que os utilizam levou a um renascimento no mercado de armazenamento de valor-chave. Esses sistemas podem armazenar e recuperar arrays associativos de maneira nativa, o que pode melhorar muito o desempenho em fluxos de trabalho comuns relacionados à web.