Vetor associativo

Um vetor associativo é uma estrutura de dados composta de um conjunto não-ordenado de itens formados por um par chave e valor, no qual cada chave possui um valor associado. Essas chaves são definidas pelo usuário e devem ser armazenadas na estrutura. O relacionamento existente entre as chaves e seus respectivos valores é chamado de mapeamento, pois para buscar um valor utiliza-se a chave como índice de busca. Na implementação de um vetor associativo, os elementos são armazenados e recuperados com funções de dispersão. Pode-se buscar o valor de um elemento pela chave e também verificar se existe algum elemento relacionado àquela chave.

A principal vantagem existente na utilização de vetores associativos está na facilidade de realização de buscas por valores. Porém, não é tão eficiente quanto um vetor comum quando todos os elementos do vetor devem ser processados.

A relação entre uma chave e seu valor as vezes é chamada de mapeamento ou ligação. Por exemplo, se o valor associado à chave "bob" é 7, dizemos que nosso vetor mapeia "bob" para 7. Vetores associativos estão intimamente relacionados ao conceito matemático de função bijetora com um domínio finito. Como consequência, um uso comum e importante de vetores associativos é em memorização.

Operações

As operações normalmente disponíveis em vetores associativos são:

Adição: liga uma chave a um valor
Redefinição: liga uma chave antiga a um novo valor
Remoção: desvincula uma chave de um valor e apaga a chave da lista de chaves
Busca: procura o valor que está vinculado a uma chave

Exemplos

Um exemplo bastante comum para a utilização de vetores associativos é uma lista telefônica, na qual o nome da pessoa é utilizado como chave e o telefone da pessoa é o valor:

telefones['bob']='55555555'

Python

Em Python, os vetores associativos são representados por estruturas chamadas de dicionários. Ao definir um dicionário com os seguintes elementos:

dict = {"SO":"Linux", "Nucleo":"2.6"}

"SO" e "Nucleo" passarão a ser usados como chave, para obtenção dos valores. Um exemplo de utilização é:

print dict["SO"]

Esse código irá mostrar na saída do programa o valor armazenado para a chave "SO":

Linux

Estruturas de dados para vetores associativos

Vetores associativos são geralmente usados quando a busca é a operação mais frequente. Por essa razão, implementações são geralmente planejadas para permitir rapidez na busca, ao custo de lentas inserções e uma grande área de cobertura para armazenamento se comparado a outras estruturas de dados (como listas associadas).

Existem duas estruturas de dados principais usadas para representar vetores associativos: a tabela de dispersão e a árvore binária de busca auto-balanceada (como a árvore rubro-negra ou a árvore AVL). Árvore B (e variantes) também podem ser usadas, e são comumente usadas quando o vetor associativo é muito grande para ser armazenado completamente em memória, por exemplo, em um banco de dados simples.

Uma simples, mas geralmente ineficiente, representação de vetores associativos é através de lista associada, que simplesmente armazena uma lista encadeada de pares chave-valor. Cada busca realiza uma procura linear através da lista procurando por uma chave.

Referências

SEBESTA, Robert W. Conceitos de Linguagens de Programação. Edição 5. Bookman Editora. 2003.