O que é um Hashtable?
Na ciência da computação, uma hashtable é uma estrutura de dados para armazenar dados que consiste em uma lista de valores, chamados chaves, que são emparelhadas com uma lista correspondente de valores, chamada matriz. Por exemplo, um nome comercial pode ser emparelhado com seu endereço. Normalmente, cada valor na matriz tem um número de posição conhecido como hash. A função hash geralmente é um conjunto de instruções ou um algoritmo que mapeia cada valor de 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 hash é atribuir cada chave a um valor correspondente exclusivo na matriz; isso geralmente é chamado de hash. As funções de hash devem ser formatadas corretamente para que uma hashtable funcione corretamente.
O desempenho de uma tabela de hash em um conjunto de dados depende da eficiência de sua função de hash. Uma boa função de hash normalmente fornece uma pesquisa uniforme de chaves e uma distribuição uniforme de mapeamentos na matriz correspondente. Uma colisão de hash ocorre quando duas chaves 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 tabela de hashtags seja geralmente fixo, às vezes pode haver chaves duplicadas. Mesmo assim, uma tabela de hash bem projetada possui funções de hash efetivas 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 cluster de mapeamentos. Se uma função hash criar um cluster de mapeamentos para chaves existentes, isso poderá aumentar a quantidade de tempo que leva para procurar os valores correspondentes. Isso pode diminuir 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 cluster de valores já foi atribuído, 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 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 chaves já atribuídas pelo tamanho da matriz correspondente. À medida que o fator de carga aumenta, uma boa função de hash normalmente mantém 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 de uma função hash com um determinado número de chaves e quando uma nova função 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 clusters devido a um fator de carga crescente. Em teoria, a chave para produzir uma hashtable perfeita é produzir uma função 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 clusters - com um fator de carga crescente. Nos piores cenários, uma função de hash perfeita ainda permitiria hash constante sem atingir um limite.