Discussão:Índices Hash

Comentários

• 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