Exibir código-fonte para Discussão:Índices Hash

= Comentários =
<br>

* Hashing:
** É uma técnica simples e amplamente utilizada na programação de sistemas. Quando a tabela hash tem tamanho adequado ao número de chaves que irá armazenar e a função hash utilizada apresenta boa qualidade, a estratégia de manipulação por hashing é bastante eficiente


* A função de espalhamento ou função de dispersão é a responsável por gerar um índice a partir de determinada chave
**Caso a função seja mal escolhida, toda a tabela terá um mau desempenho.
* A função de dispersão pode calcular o mesmo índice para duas chaves diferentes, uma situação chamada colisão. Por conta disso, a função deve ser projetada para evitar ao máximo a ocorrência de colisões.
* Colisões: muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas



* Funções de espalhamento perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável
** Exemplo: nas funções de dispersão da criptografia), ou quando conhecemos previamente o conteúdo da tabela armazenada
* A tabela de dispersão é uma estrutura de dados do tipo dicionário, que não permite armazenar elementos repetidos, recuperar elementos sequencialmente (ordenação), nem recuperar o elemento antecessor e sucessor.
* Aplicações:
** banco de dados
** implementações das tabelas de símbolos dos compiladores
** na programação de jogos para acessar rapidamente a posição para qual o personagem irá se mover e na implementação de um dicionário.


* Vantagem:
** Desempenho -- enquanto a busca linear tem complexidade temporal e a busca binária tem complexidade  O(\log N), o tempo de busca na tabela hash é praticamente independente do número de chaves armazenadas na tabela, ou seja, tem complexidade temporal O(1). 


* Boa função hash deve apresentar duas propriedades básicas: 
** seu cálculo deve ser rápido 
** deve gerar poucas colisões