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