O que é uma hashtable?
Na ciência da computação, a hashtable é uma estrutura de dados para armazenar dados que consistem em uma lista de valores, chamada chaves, que são emparelhadas com uma lista correspondente de valores, chamada de matriz. Por exemplo, um nome comercial pode ser emparelhado com seu endereço. Normalmente, cada valor na matriz possui um número de posição referido como um hash. A função hash geralmente é um conjunto de instruções ou um algoritmo que mapeia cada valor -chave para um hash - conectando o nome da empresa ao seu endereço, seu número de telefone e sua categoria de negócios, por exemplo. O objetivo da função de hash é atribuir cada chave a um valor correspondente exclusivo na matriz; Isso é comumente referido como hash. As funções de hash devem ser adequadamente formatadas para uma hashtable para funcionar corretamente.
O desempenho de uma hashtable em um conjunto de dados depende da eficiência de sua função de hash. Uma boa função hash típicaAlly fornece uma pesquisa uniforme de teclas e uma distribuição uniforme de mapeamentos na matriz correspondente. Uma colisão de hash ocorre quando duas teclas são atribuídas ao mesmo valor correspondente. Quando ocorre uma colisão de hash, a função de hash geralmente é executada novamente até que um valor correspondente exclusivo seja encontrado; Isso geralmente resulta em tempos de hash mais longos. Embora o número de chaves em uma hashtable seja geralmente fixo, às vezes pode haver teclas duplicadas. Mesmo assim, uma hashtable bem projetada possui funções de hash eficazes que mapeiam cada chave para um valor correspondente exclusivo na matriz.
Às vezes, funções de hash ineficientes em uma hashtable também podem produzir um aglomerado de mapeamentos. Se uma função hash criar um cluster de mapeamentos para as teclas existentes, isso pode aumentar a quantidade de tempo necessária para procurar os valores correspondentes. Isso pode desacelerar o hash para chaves futuras, pois a maioria das funções de hash geralmente procura a próxima posição disponível na matriz. Se um grande clusterdos valores já foram atribuídos, normalmente levaria muito mais tempo para procurar um valor não atribuído para uma nova chave.
O fator de carga é outro conceito relacionado à eficiência de uma função de hash; O fator de carga é a quantidade de hashings já existentes em relação ao tamanho geral da matriz correspondente em uma hashtable. Geralmente é definido dividindo o número de teclas já atribuídas pelo tamanho da matriz correspondente. À medida que o fator de carga aumenta, uma boa função de hash normalmente ainda manterá um número constante de colisões e clusters até um determinado ponto. Muitas vezes, esse limite pode ser usado para determinar a eficiência da função de hash com um determinado número de chaves e quando uma nova função de hash pode ser necessária.
Muitos pesquisadores de ciência da computação se esforçaram para produzir a função de hash perfeita - uma que não produz colisões ou aglomerados, com um fator de carga crescente. Em teoria, a chave para produzir uma hashtable perfeita é proDuce uma função de hash perfeita. Em geral, os pesquisadores acreditam que uma função de hash perfeita deve ter desempenho constante - o número de colisões e aglomerados - com um fator de carga crescente. Na pior das hipóteses, uma função de hash perfeita ainda permitiria hash constante sem atingir um limiar.