Trabalho sobre Tabela Hash

Prévia do material em texto

UNIVERSIDADE DO OESTE DE SANTA CATARINA– UNOESC 
ÁREA DAS CIÊNCIAS EXATAS E DA TERRA
CAROLINA FRANCO
MICHEL ZARPELON
TABELAS HASH
Joaçaba
2013
CAROLINA FRANCO
MICHEL ZARPELON
TABELAS HASH
Trabalho apresentado à disciplina de Estrutura de Dados, Curso de Engenharia da Computação. Área das Ciências Exatas e daTerra, Universidade do Oeste de Santa Catarina.
Professor: Ricardo Antonello
Joaçaba
2013
INTRODUÇÃO
	Tabelas Hash também são conhecidas como tabelas de espalhamento, são estruturas de dados que associam chaves de pesquisa (hash) a valores. Usando tabelas hash podemos fazer uma pesquisa rápida de valores a partir de uma chave simples. S busca por chaves ocorre através de comparações. Para essa busca se utiliza a função hash que realiza o calculo da posição que uma chave ocupa na tabela. 
	Seu uso é conhecido desde os anos 60 para a construção de compiladores para manter as listas de variáveis e usuário e seus respectivos valores. Mas outros dão o credito da criação para H.P. Luhn que teve a ideia em 1953 enquanto trabalhava para a IBM. 
TABELAS 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.
	As tabelas hash podem ser representadas com vetores e vetores encadeados:
Vetor: cada posição do vetor guarda uma informação. Se a função de hashing aplicada a um conjunto de elementos determinar as informações I1, I2, ..., In, então o vetor V[1... N] é usado para representar a tabela hash.
Vetor + Lista Encadeada: o vetor contém ponteiros para as listas que representam as informações.
FUNÇÃO HASHING
	
	A Função de Hashing é a responsável por gerar um índice a partir de uma determinada chave. O ideal é que a função forneça índices únicos para o conjunto das chaves de entrada possíveis. A função de Hashing é extremamente importante, pois ela é responsável por distribuir as informações pela Tabela Hash. A implementação da função de Hashing tem influência direta na eficiência das operações sobre o Hash.
 HASHING PERFEITO
 	Uma função hash perfeita para um conjunto específico, pode ser avaliada em tempo constante, e com valores de uma escala pequena, pode ser encontrada por um algoritmo aleatório num certo número de operações que é proporcional ao tamanho do conjunto. O tamanho mínimo da descrição de uma função hash perfeita depende do alcance de seus valores da função: Quanto menor o intervalo, é necessário mais espaço. As funções hash perfeitas adequados para utilização com uma tabela hash exigem, pelo menos, um número de bits que é proporcional ao tamanho do conjunto.
 	Uma função hash perfeita com um número limitado de valores de intervalo pode ser utilizado para operações de pesquisa eficiente, pela colocação de chaves a partir do conjunto (ou outros valores associados) numa tabela indexada pela saída da função. A utilização da função hash perfeita é melhor em situações onde existe um grande conjunto freqüentemente consultado, que raramente é atualizado. Soluções eficientes para realizar atualizações são conhecidas como hashing perfeitas dinâmicas, mas estes métodos são relativamente complicado de implementar. 
 HASING IMPERFEITO
 	Podemos caracterizar o hashing imperfeito por existirem nele chaves diferentes que pertencem ao mesmo conjunto, onde a função hash utilizada fornece saidas iguais.
	
EXEMPLO PRÁTICO:
Suponha que queiramos armazenar as seguintes chaves: C, H, A, V, E e S em um vetor de P = 7 posições (0..6) conforme a seguinte função f(k) = k(código ASCII) % P.
Tabela ASCII: C (67); H (72); A (65); V (86); E (69) e S (83). 
	Chave
	K = ord(chave)
	Ii = h(K)
	C
	67
	4
	H
	72
	2
	A
	65
	2
	V
	86
	2
	E
	69
	6
	S
	83
	6
 COLISÕES
	
	Colisões são extremamente comuns quando usamos tabelas hash, acontece quando duas ou mais chaves geram o mesmo endereço da Tabela Hash.
Principais causas:
Em geral o número de chaves possíveis é muito maior que o número de entradas disponíveis na tabela.
Não se pode garantir que as funções de hashing possuam um bom potencial de distribuição.
	Podemos usar outras estruturas de dados junto com hash para solucionar o problema das colisões, são elas:
Listas Encadeadas; 
Árvores Balanceadas.
	Um bom método de resolução de colisões é essencial, não importando a qualidade da função de hashing.
Há diversas técnicas de resolução de colisão. As técnicas mais comuns podem ser enquadradas em duas categorias: 
Endereçamento Aberto; 
Encadeamento. 
HASHING FECHADO DE ENDEREÇAMENTO ABERTO
Utilizando esse método os registros em conflito ficam armazenados dentro da própria tabela. Para solucionar a colisão são utilizadas consultas uniformizadas dentro da tabela, essa busca é feita de forma unidimensional na tabela até encontrar um campo vazio ou o campo buscado. Outras maneiras que podem ser implementadas costumam incrementar o índice exponencialmente. Para inserir elementos é utilizado o mesmo método de busca. 
PONTOS IMPORTANTES
Utiliza somente uma estrutura de dados de tamanho fixo para implementar o hashing.
Não necessita de ponteiros para a sua implementação.
Forma muito utilizada "antigamente".
Adequada para implementação em disco (ISAM).
Somente uma tabela dividida em partes iguais.
Áreas de tamanho fixo para cada Repositórios.
Cada repositório é examinado seqüencialmente na busca por uma chave
Quando um repositório está cheio, há estouro.
Filosofias para tratamento de estouros:
Utilização do primeiro espaço vazio
Busca quadrática
Implementação com busca seqüencial após estouro.
EXEMPLO EM JAVA
package hashaberto;
 
import java.util.Scanner;
 
public class HashAberto {
 
    public static class hash {
 
        int chave;
        char livre;
    }
    static int tam = 8;
    static hash tabela[] = new hash[tam];
    static Scanner entrada = new Scanner(System.in);
 
    public static void inserir(int pos, int n) {
        int i = 0;
        while (i < tam
                && tabela[(pos + i) % tam].livre != 'L'
                && tabela[(pos + i) % tam].livre != 'R') {
            i = i + 1;
        }
        if (i < tam) {
            tabela[(pos + i) % tam].chave = n;
            tabela[(pos + i) % tam].livre = 'O';
        } else {
            System.out.println("Tabela cheia");
        }
    }
 
    public static void remover(int n) {
        int posicao = buscar(n);
        if (posicao < tam) {
            tabela[posicao].livre = 'R';
        } else {
            System.out.println("Elemento não está presente");
        }
    }
 
    public static int buscar(int n) {
        int i = 0;
        int pos = funcaohashing(n);
        while (i < tam
                && tabela[(pos + i) % tam].livre != 'L'
                && tabela[(pos + i) % tam].chave != n) {
            i = i + 1;
        }
        if (tabela[(pos + i) % tam].livre == n
                && tabela[(pos + i) % tam].livre != 'R') {
            return (pos + i) % tam;
        } else {
            return tam;
        }
    }
 
    static int funcaohashing(int num) {
        return num % tam;
    }
 
    static void mostrarhash() {
        for (int i = 0; i < tam; i++) {
            if (tabela[i].livre == 'O') {
                System.out.println("Estrada " + i + ": " + tabela[i].chave + " " + tabela[i].livre);
            }
        }}
 
    public static void main(String[] args) {
        // TODO code application logic here
        int op, pos, num, i;
 
        for (i = 0; i < tam; i++) {
            tabela[i] = new hash();
            tabela[i].livre = 'L';
        }
        do {
            System.out.println("\nMENU DE OPÇÕES\n");
            System.out.println("1 - Inserir elemento");
            System.out.println("2 - Mostar tabela hashing");
            System.out.println("3 - Excluir elemento");
            System.out.println("Digite sua opção:");
            op = entrada.nextInt();
 
            if (op < 1 || op > 4) {
                System.out.println("Opção inválida!");
            } else {
                switch (op) {
                    case 1:
                        System.out.println("Digite um número: ");
                        num = entrada.nextInt();
                        pos = funcaohashing(num);
                        inserir(pos, num);
                        break;
                    case 2:
                        mostrarhash();
                        break;
                    case 3:
                        System.out.println("Digite um número: ");
                        num = entrada.nextInt();
                        remover(num);
                        break;
                }
            }
        } while (op != 4);
    }
}
HASHING ABERTO DE ENCADEAMENTO SEPARADO
É provavelmente o método mais simples para resolução de colisões, em que normalmente um índice aponta para uma lista encadeada onde são contidos os registros em conflito. Para a inserção de elementos na tabela é preciso uma consulta na lista encadeada. Para remover elementos é necessário atualizar os índices da lista. 
PONTOS IMPORTANTES
Forma mais intuitiva de se implementar o conceito de Hashing.
Utiliza a idéia de termos uma tabela com N entradas, cada uma como cabeça de lista para uma lista representando o conjunto Ni.
Calculamos a partir da chave qual entrada da tabela é a cabeça da lista que queremos.
Utilizamos uma técnica qualquer para pesquisa dentro de Ni. Tipicamente será a técnica de pesquisa seqüencial em lista encadeada.
Podemos utilizar qualquer outra coisa para representar os Ni. Uma árvore poderia ser uma opção.
EXEMPLO PRÁTICO
Suponha que queiramos armazenar os caracteres que compõem a palavra CHAVES em um vetor de P = 7 posições (0..6) conforme a seguinte função f(k) = k(código ASCII) % P. 
EXEMPLO EM JAVA
import java.util.Scanner;
 
public class HashLista {
 
    public static class hash {
 
        int chave;
        hash prox;
    }
 
    static int tam = 10;
    static hash tabela[] = new hash[10];
    static Scanner entrada = new Scanner(System.in);
 
    public static void inserir(int pos, int n) {
        hash novo;
        novo = new hash();
        novo.chave = n;
        novo.prox = tabela[pos];
        tabela[pos] = novo;
    }
 
    static int funcaohashing(int num) {
        return num % tam;
    }
 
    static void mostrarhash() {
        hash aux;
        for (int i = 0; i < tam; i++) {
            aux = tabela[i];
            while (aux != null) {
                System.out.println("Entrada " + i + ": " + aux.chave);
                aux = aux.prox;
            }
        }
    }
 
    static void excluirhash(int num) {
        int pos = funcaohashing(num);
        hash aux;
        if (tabela[pos] != null) {
            if (tabela[pos].chave == num) {
                tabela[pos] = tabela[pos].prox;
            } else {
                aux = tabela[pos].prox;
                hash ant = tabela[pos];
                while (aux != null && aux.chave != num) {
                    ant = aux;
                    aux = aux.prox;
                }
                if (aux != null) {
                    ant.prox = aux.prox;
                } else {
                    System.out.println("Número não encotrado");
                }
            }
        } else {
            System.out.println("Número não encontrador");
        }
    }
 
    public static void main(String[] args) {
        int op, pos;
        int num;
 
        do {
            System.out.println("\nMENU DE OPÇÕES\n");
            System.out.println("1 - Inserir elemento");
            System.out.println("2 - Mostar tabela hashing");
            System.out.println("3 - Excluir elemento");
            System.out.println("Digite sua opção:");
            op = entrada.nextInt();
 
            if (op < 1 || op > 4) {
                System.out.println("Opção inválida!");
            } else {
                switch (op) {
                    case 1:
                        System.out.println("Digite um número: ");
                        num = entrada.nextInt();
                        pos = funcaohashing(num);
                        inserir(pos, num);
                        break;
                    case 2:
                        mostrarhash();
                        break;
                    case 3:
                        System.out.println("Digite um número: ");
                        num = entrada.nextInt();
                        excluirhash(num);
                        break;
                }
            }
        } while (op != 4);
 
    }
}
VANTAGENS
Simplicidade, na medida em que é muito fácil de definir um algoritmo para implementar hashing. 
Escalabilidade, dado que podemos adequar o tamanho da tabela de hashing ao número de elementos a armazenar N esperado para a aplicação. 
Eficiência para grande número de elementos, para trabalharmos com problemas envolvendo N = 100.000 de dados, podemos imaginar uma tabela de hash com n=1.000 entradas, onde temos uma divisão do espaço de procura da ordem de N/1.000 de imediato. 
Aplicação imediata a arquivos, os métodos de hashing, tanto de endereçamento aberto como fechado, podem ser utilizados praticamente sem nenhuma alteração em um ambiente de dados persistentes utilizando arquivos em disco.
DESVANTAGENS
Dependência da escolha de função de hashing, para que o tempo de acesso médio seja mantido, é necessário que a função de hashing divida o universo dos dados de entrada em conjuntos de tamanho aproximadamente igual. 
Ineficiência para os últimos elementos das listas encadeadas, para o qual o acesso a estes elementos pode ser mais demorado do que em implementações em árvore.
CONCLUSÃO
Tabelas Hash podem ser ditas como algoritmos de fácil implementação, muito eficientes para armazenar um grande número de elementos. As tabelas de dispersão se beneficiam da elevada rapidez revelada pelas tabelas/listas nas principais operações de manipulação de dado, que são a inserção e a remoção de elementos. 
REFERÊNCIAS
PEREIRA, Silvio do Lago. Estrutura de dados fundamentais: conceitos e aplicações. 5. ed. São Paulo: Érica, 2001. 246 p. ISBN 8571943702 
GUIMARÃES, A. M. Algoritmos e estruturas de dados. LTC, 1994.
LOPES, Arthur. Estrutura de dados para a construção de sofware. Canoas, RS: Ulbra, 1999. 440p. ISBN 8585692650
LORENZI, Fabiana; MATTOS, Patrícia Noll de; CARVALHO, Tanisi Pereira de. Estrutura de dados. São Paulo: Thomson, 2007. 175 p. ISBN 852105561
ESTRUTURAS de dados. Rio de Janeiro: SENAC, 1999. 112 p. ISBN 8574580058
VILLAS, Marcos Vianna. Estrutura de dados: conceitos e técnicas de implementação. Rio de Janeiro: Campus, 2004. 298 p. : ISBN 8570017995
VELOSO, P., et al. Estruturas de dados. Rio de Janeiro: Campus, 1986.
Site: <http://www.manfred.com.br/index.php/bsi/estrutura-de-dados-i/146-aula-14-tabela-hash-em-java> acesso em 04 de junho de 2013
MANACERO, Jr Aleardo. Tabelas Hash. Disponível em: <http://www.dcce.ibilce.unesp.br/ ~aleardo/cursos/ed/hashing07.pdf> acesso em 03 de junho de 2013
AZEREDO,P. A. Métodos de classificação de dados e análise de suas complexidades. Rio de Janeiro: Campus, 1996.
0
1
2
3
4
5
6
C
H
A
V
E
S