Vetores associativos

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 hash. 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 conseqüência, um uso comum e importante de vetores associativos é em memorização.

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
Lookup: procura o valor que está vinculado a uma chave

Índice

[editar] 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'

[editar] Python

Em Linguagem 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", "Kernel":"2.6"}

"SO" e "Kernel" 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

[editar] Estruturas de Dados para Vetores Associativos

Vetores associativos são geralmente usados quando a busca é a operação mais freqüente. 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).

[editar] Representações Eficientes

Existem duas estruturas de dados principais usadas para representar vetores associativos: a tabela hash 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.

[editar] Listas Associadas

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.