Tabela Hash

Tabela Hash

Conteúdo

1. Conceitos Básicos

2. Definição de Hash

3. Função Hash

4. Colisões

5. Vantagens

6. Desvantagens

7. Exercícios

Conceitos Básicos

Um hash (ou escrutínio) é uma sequência de bits geradas por um algoritmo de dispersão, em geral representada em base hexadecimal, que permite a visualização em letras e números (0 a 9 e A a F), representando um nibble cada. O conceito teórico diz que "hash é a transformação de uma grande quantidade de informações em uma pequena quantidade de informações".

Essa sequência busca identificar um arquivo ou informação unicamente. Por exemplo, uma mensagem de correio eletrônico, uma senha, uma chave criptográfica ou mesmo um arquivo. É um método para transformar dados de tal forma que o resultado seja (quase) exclusivo. Além disso, funções usadas em criptografia garantem que não é possível a partir de um valor de hash retornar à informação original.

Como a sequência do hash é limitada, muitas vezes não passando de 512 bits, existem colisões (sequências iguais para dados diferentes). Quanto maior for a dificuldade de se criar colisões intencionais, melhor é o algoritmo.

Uma função de hash recebe um valor de um determinado tipo e retorna um código para ele. Enquanto o ideal seria gerar identificadores únicos para os valores de entrada, isso normalmente não é possível: na maioria dos casos, o contra-domínio de nossa função é muito menor do que o seu domínio, ou seja, (o tipo de entrada) pode assumir uma gama muito maior de valores do que (o resultado da função de hash).

 Arranjos utilizam índices para armazenar as informações.

 Através do índice as operações sobre arranjos são realizadas no tempo O(1).

 Arranjos não fornecem mecanismos para calcular o índice a partir de uma informação armazenada. A pesquisa não éO(1).

 Ideal: Parte da informação poderia ser utilizada para recuperar diretamente a informação.

Problema: Esta estratégia exigiria um arranjo muito grande e a maioria das posições seriam desperdiçadas.

Família

Família[1] = “José Maria”

Família[3] = “Artur”

Família[2] = “Leila”Em qual posição está “Alciene” ?

Definição de Hash

 Hash é uma generalização da noção mais simples de um arranjo comum, sendo uma estrutura de dados do tipo dicionário.

 Dicionários são estruturas especializadas em prover as operações de inserir, pesquisar e remover.

 A idéia central do Hash é utilizar uma função, aplicada sobre parte da informação (chave), para retornar o índice onde a informação deve ou deveria estar armazenada.

 Esta função que mapeia a chave para um índice de um arranjo é chamada de Função de Hashing.

 A estrutura de dados Hash é comumente chamada de Tabela Hash.

Tabela Hash

Uma tabela de Hashing (ou tabela de dispersão) é uma estrutura de dados que faz associação de valores a chaves.

Uma tabela hash é construída através de um vetor de tamanho n, no qual se armazenam as informações;

Nele, a localização de cada informação é dada a partir do cálculo de um índice através de uma função de indexação, a função hash.

Significado de Hash

Hashsignifica:

1. Fazer picadinho de carne e vegetais para cozinhar.

2. Fazerumabagunça. (Webster’s New World Dictionary)

Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa.

Tabela Hash

Em Computação a Tabela Hash é uma estrutura de dados especial, que armazena as informações desejadas associando chaves de pesquisa a estas informações.

Objetivo: a partir de uma chave, fazer uma busca rápida e obter o valor desejado.

A idéia central por trás da construção de uma Tabela Hash é identificar, na chave de busca, quais as partes que são significativas.

Função de Hashing

A Função de Hashing é a responsável por gerar um índice a partir de uma determinada chave.