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 string 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 de função de hash converte o índice de string em um índice inteiro para encontrar o valor. Essa é uma conversão consistente; portanto, o índice inteiro real nunca precisa ser armazenado, mas é calculado a partir da string, conforme necessário a cada vez. O que normalmente seria chamado de índice - a localização numérica de um elemento dentro de uma matriz - é chamada dechave. 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 a um índice referenciando um elemento em uma matriz padrão na estrutura de dados.
No coração de cada matriz associativa está a função de 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 chaves que são inteiros e algumas projetadas para funcionar em chaves que são strings. No caso de uma chave inteira, um método popular é dividir o valor -chave pelo tamanho da matriz e usar o restante da divisão para, esperançosamente, obter um valor de índice único.
A função de hash pode ser muito mais complexa para chaves que são strings. Alguns métodos incluem adicionar o valor numérico de cada caractere na string e depois dividi -la por algum número,Ou usando apenas os primeiros caracteres da string para obter um número exclusivo. Existem muitas maneiras de derivar um número de uma série de caracteres.
Ao lidar com uma grande quantidade de pares de valor-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 teclas apontam efetivamente para o mesmo índice na matriz de valores. Existem várias soluções para colisão, principalmente porque tem uma alta probabilidade de acontecer na maioria das aplicações práticas.
Uma solução para a colisão é ter cada índice de valor na verdade uma lista vinculada para que, quando mais de uma chave resolver para esse local de índice, o local pode conter mais de um valor. Isso é chamado de encadeamento e é uma maneira simples de lidar com uma colisão, embora também possa desacelerar o tempo necessário para recuperar as informações. Outro método de lidar com uma colisão é chamado de sondagem linear.Quando ocorre uma colisão, a investigação linear funciona movendo -se através da matriz de valor até que um índice não utilizado seja encontrado. Esta 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.