O que é uma matriz associativa?

Uma matriz associativa, também chamada de tabela de hash ou mapa de hash, é semelhante a uma matriz padrão, exceto que o índice da matriz pode ser uma sequência em vez de um número inteiro. Em muitos aplicativos de banco de dados e em outros programas que lidam com grandes quantidades de dados, uma matriz associativa é um elemento vital para ajudar a classificar e acessar informações de maneira eficiente. No centro de uma matriz associativa, há uma matriz padrão indexada com números inteiros, como normalmente seria o caso. Um algoritmo especial chamado função hash converte o índice de string em um índice inteiro para encontrar o valor. Como uma conversão é consistente, o índice inteiro real nunca precisa ser armazenado, mas é calculado a partir da sequência conforme necessário a cada vez.

A terminologia usada ao se referir a uma matriz associativa pode ser um pouco diferente da usada quando se fala de uma matriz normal. O que normalmente seria chamado de índice - a localização numérica de um elemento dentro de uma matriz - é chamado de chave. Os dados associados à chave são chamados de valor. Isso significa que, dentro de uma matriz associativa, uma chave está associada a um valor, que se correlaciona com um índice que faz referência a um elemento em uma matriz padrão na estrutura de dados.

No coração de toda matriz associativa está a função hash. Este é um algoritmo usado para determinar o índice numérico de um valor com base na chave. Existem vários tipos de funções de hash, algumas projetadas para operar em teclas que são números inteiros e outras projetadas para trabalhar em teclas que são seqüências de caracteres. No caso de uma chave inteira, um método popular é dividir o valor da chave pelo tamanho da matriz e usar o restante da divisão para, esperançosamente, obter um valor de índice exclusivo.

A função hash pode ser muito mais complexa para chaves que são seqüências de caracteres. Alguns métodos incluem adicionar o valor numérico de cada caractere na sequência e depois dividi-lo por algum número ou usar apenas os primeiros caracteres da sequência para obter um número único. Existem várias maneiras de derivar um número de uma sequência de caracteres.

Ao lidar com uma grande quantidade de pares de valores-chave em uma matriz associativa, um problema que pode surgir é chamado de colisão. A colisão acontece quando o índice inteiro derivado de uma chave é idêntico ao índice inteiro de outra chave. Essas duas chaves apontam efetivamente para o mesmo índice na matriz de valores. Existem várias soluções para a colisão, principalmente porque tem uma alta probabilidade de acontecer na maioria das aplicações práticas.

Uma solução para a colisão é fazer com que cada índice de valor seja realmente uma lista vinculada, para que, quando mais de uma chave for resolvida para esse local de índice, o local possa conter mais de um valor. Isso se chama encadeamento e é uma maneira simples de lidar com uma colisão, embora também possa diminuir o tempo necessário para recuperar as informações. Outro método para lidar com uma colisão é chamado de sondagem linear. Quando ocorre uma colisão, a análise linear funciona movendo-se pela matriz de valores até que um índice não utilizado seja encontrado. Essa solução pode ajudar a manter os dados distribuídos uniformemente na matriz associativa, mas também pode aumentar a quantidade de tempo necessária para procurar um valor.