Click here to load reader

Pesquisa em Memória Primária - Hashing

  • View
    21

  • Download
    0

Embed Size (px)

DESCRIPTION

Pesquisa em Memória Primária - Hashing. David Menotti Algoritmos e Estruturas de Dados I DECOM – UFOP. Transformação de Chave ( Hashing ). Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa. Hash significa: - PowerPoint PPT Presentation

Text of Pesquisa em Memória Primária - Hashing

  • Pesquisa em Memria Primria - HashingDavid MenottiAlgoritmos e Estruturas de Dados IDECOM UFOP

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformao de Chave (Hashing)Os registros armazenados em uma tabela so diretamente endereados a partir de uma transformao aritmtica sobre a chave de pesquisa.

    Hash signica: Fazer picadinho de carne e vegetais para cozinhar. Fazer uma baguna. (Websters New World Dictionary)

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformao de Chave (Hashing)Um mtodo de pesquisa com o uso da transformao de chave constitudo de duas etapas principais:1 - Computar o valor da funo de transformao, a qual transforma a chave de pesquisa em um endereo da tabela.2 - Considerando que duas ou mais chaves podem ser transformadas em um mesmo endereo de tabela, necessrio existir um mtodo para lidar com colises.Qualquer que seja a funo de transformao, algumas colises iro ocorrer fatalmente, e tais colises tm de ser resolvidas de alguma forma.Mesmo que se obtenha uma funo de transformao que distribua os registros de forma uniforme entre as entradas da tabela, existe uma alta probabilidade de haver colises.

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformao de Chave (Hashing)O paradoxo do aniversrio (Feller,1968, p. 33), diz que em um grupo de 23 ou mais pessoas, juntas ao acaso, existe uma chance maior do que 50% de que 2 pessoas comemorem aniversrio no mesmo dia.Assim, se for utilizada uma funo de transformao uniforme que enderece 23 chaves randmicas em uma tabela de tamanho 365, a probabilidade de que haja colises maior do que 50%.

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformao de Chave (Hashing)A probabilidade p de se inserir N itens consecutivos sem coliso em uma tabela de tamanho M :

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformao de Chave (Hashing)Alguns valores de p para diferentes valores de N, onde M = 365.

    Para N pequeno a probabilidade p pode ser aproximada por p N (N 1))/730 . Por exemplo, para N = 10 ento p 87,7%.

    NP100,883220,524230,493300,303

    David MenottiAlgoritmos e Estrutura de Dados I

    Funes de TransformaoUma funo de transformao deve mapear chaves em inteiros dentro do intervalo [0...M 1], onde M o tamanho da tabela.

    A funo de transformao ideal aquela que:Seja simples de ser computada.Para cada chave de entrada, qualquer uma das sadas possveis igualmente provvel de ocorrer.

    David MenottiAlgoritmos e Estrutura de Dados I

    Mtodo mais UsadoUsa o resto da diviso por M .

    h(K) = K % M (em linguagem C)

    onde K um inteiro correspondente chave.

    David MenottiAlgoritmos e Estrutura de Dados I

    Mtodo mais UsadoCuidado na escolha do valor de M. M deve ser um nmero primo, mas no qualquer primo: devem ser evitados os nmeros primos obtidos a partir de

    b*i j

    onde b a base do conjunto de caracteres (geralmente b = 64 para BCD, 128 para ASCII, 256 para EBCDIC, ou 100 para alguns cdigos decimais), e i e j so pequenos inteiros.

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformaes de Chaves no numricasAs chaves no numricas devem ser transformadas em nmeros:

    n o nmero de caracteres da chave.Chave[i] corresponde representao ASCII do i-simo caractere da chave.p[i] um inteiro de um conjunto de pesos gerados randomicamente para 1 i n.

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformaes de Chaves no numricasVantagem de se usar pesos: Dois conjuntos diferentes de pesos p1 [i] e p2 [i], 1 i n, leva a duas funes de transformao h1 (K) e h2 (K) diferentes.

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformaes de Chaves no numricasPrograma que gera um peso para cada caractere de uma chave constituda de n caracteres:

    void GeraPesos(TipoPesos p){ /* Gera valores randomicos entre 1 e 10.000 */ int i; struct timeval semente; /* Utilizar o tempo como semente para a funcao srand() */ gettimeofday(&semente,NULL); srand((int)(semente.tv_sec + 1000000*semente.tv_usec)); for (i = 0; i < n; i++) p[i] = 1+(int) (10000.0*rand()/(RAND_MAX+1.0));}

    David MenottiAlgoritmos e Estrutura de Dados I

    Transformaes de Chaves no numricasImplementao da funo de transformao:

    Indice h(TipoChave Chave, TipoPesos p){ int i; unsigned int Soma = 0; int comp = strlen(Chave); for (i = 0; i < comp; i++) Soma += (unsigned int)Chave[i] * p[i];

    return (Soma % M);}

    David MenottiAlgoritmos e Estrutura de Dados I

    Listas EncadeadasUma das formas de resolver as colises simplesmente construir uma lista linear encadeada para cada endereo da tabela. Assim, todas as chaves com mesmo endereo so encadeadas em uma lista linear.

    David MenottiAlgoritmos e Estrutura de Dados I

    Listas EncadeadasExemplo: Se a i-sima letra do alfabeto representada pelo nmero i e a funo de transformao h(Chave) = Chave mod M utilizada para M = 7, o resultado da insero das chaves P E S Q U I S A na tabela o seguinte:Por exemplo, h(A) = h(1) = 1, h(E) = h(5) = 5, h(S) = h(19) = 5, etc

    David MenottiAlgoritmos e Estrutura de Dados I

    ExemploF E R I A D O

    David MenottiAlgoritmos e Estrutura de Dados I

    Endereamento AbertoQuando o nmero de registros a serem armazenados na tabela puder ser previamente estimado, ento no haver necessidade de usar apontadores para armazenar os registros.Existem vrios mtodos para armazenar N registros em uma tabela de tamanho M > N , os quais utilizam os lugares vazios na prpria tabela para resolver as colises. (Knuth, 1973, p.518)

    David MenottiAlgoritmos e Estrutura de Dados I

    Endereamento AbertoNo Endereamento aberto todas as chaves so armazenadas na prpria tabela, sem o uso de apontadores explcitos.Existem vrias propostas para a escolha de localizaes alternativas. A mais simples chamada de hashing linear, onde a posio hj na tabela dada por:

    hj = (h(x) + j) mod M, para 1 j M 1.

    David MenottiAlgoritmos e Estrutura de Dados I

    ExemploSe a i-sima letra do alfabeto representada pelo nmero i e a funo de transformao h(Chave) = Chave mod M utilizada para M = 7,

    ento o resultado da insero das chaves L U N E S na tabela T, usando hashing linear para resolver colises mostrado abaixo.

    David MenottiAlgoritmos e Estrutura de Dados I

    ExemploPor exemplo: h(L) = h(12) = 5, h(U ) = h(21) = 0, h(N ) = h(14) = 0, h(E) = h(5) = 5, h(S) = h(19) = 5.

  • Cdigo para Tratamento de Coliso Usando Listas Encadeadas

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio para Listas Enceadas#define M 7#define n 7 typedef char TipoChave[n];

    typedef unsigned int TipoPesos[n];

    typedef struct { /* outros componentes */ TipoChave Chave;} TipoItem;

    typedef unsigned int Indice;

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio para Listas Enceadastypedef struct _celula* Apontador;

    typedef struct _celula { TipoItem Item; Apontador Prox;} Celula;

    typedef struct { Celula *Primeiro, *Ultimo;} TipoLista;

    typedef TipoLista TipoDicionario[M];

    David MenottiAlgoritmos e Estrutura de Dados I

    Operaes do Dicionrio Usando Listas Encadeadasvoid Inicializa(TipoDicionario T){ int i; for (i = 0; i < M; i++)FLVazia(&T[i]);}

    David MenottiAlgoritmos e Estrutura de Dados I

    Operaes do Dicionrio Usando Listas EncadeadasApontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T){ /*Obs.: Apontador de retorno aponta para o item anterior da lista */ Indice i; Apontador Ap; i = h(Ch, p); if (Vazia(T[i])) return NULL; /* Pesquisa sem sucesso */ else { Ap = T[i].Primeiro; while ((Ap->Prox->Prox != NULL) && (strncmp(Ch, Ap->Prox->Item.Chave, sizeof(TipoChave)) )) {Ap = Ap->Prox;} if (!strncmp(Ch, Ap->Prox->Item.Chave, sizeof(TipoChave))) return Ap; else return NULL; /* Pesquisa sem sucesso */ }}

    David MenottiAlgoritmos e Estrutura de Dados I

    Operaes do Dicionrio Usando Listas Encadeadasvoid Insere(TipoItem x, TipoPesos p, TipoDicionario T){ if (Pesquisa(x.Chave, p, T) == NULL) Ins(x, &T[h(x.Chave, p)]); else printf(" Registro ja esta presente\n");}

    void Retira(TipoItem x, TipoPesos p, TipoDicionario T){ Apontador Ap; Ap = Pesquisa(x.Chave, p, T);

    if (Ap == NULL) printf(" Registro nao esta presente\n"); else Ret(Ap, &T[h(x.Chave, p)], &x);}

    David MenottiAlgoritmos e Estrutura de Dados I

    AnliseAssumindo que qualquer item do conjunto tem igual probabilidade de ser endereado para qualquer entrada de T, ento o comprimento esperado de cada lista encadeada N/M, onde N representa o nmero de registros na tabela e M o tamanho da tabela.Logo: as operaes Pesquisa, Insere e Retira custam O(1 + N/M ) operaes em mdia, onde a constante 1 representa o tempo para encontrar a entrada na tabela e N/M o tempo para percorrer a lista. Para valores de M prximos de N , o tempo se torna constante, isto , independente de N .

  • Cdigo para Endereamento Aberto

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio Usando Endereamento Aberto#define Vazio "!!!!!!!!!!"#define Retirado "**********"#define M 7#define n 11 /* Tamanho da chave */

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio Usando Endereamento Aberto

    typedef unsigned int Apontador;

    typedef char TipoChave[n];typedef unsigned TipoPesos[n];

    typedef struct { /* outros componentes */ TipoChave Chave;} TipoItem;

    typedef unsigned int Indice;typedef TipoItem TipoDicionario[M];

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio Usando Endereamento Abertovoid Inicializa(TipoDicionario T){ int i; for (i = 0; i < M; i++) memcpy(T[i].Chave, Vazio, n);}

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio Usando Endereamento AbertoApontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T){ unsigned int i = 0; unsigned int Inicial;

    Inicial = h(Ch, p); while ( (strcmp (T[(Inicial + i) % M].Chave,Vazio) != 0) && (strcmp ( T[(Inicial + i) % M].Chave, Ch) != 0) && (i < M)) i++; if (strcmp (T[(Inicial + i) % M].Chave, Ch) == 0) return ((Inicial + i) % M); else return M; /* Pesquisa sem sucesso */}

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio Usando Endereamento Abertovoid Insere(TipoItem x, TipoPesos p, TipoDicionario T){ unsigned int i = 0; unsigned int Inicial; if (Pesquisa(x.Chave, p, T) < M) { printf("Elemento ja esta presente\n"); return; } Inicial = h(x.Chave, p); while ((strcmp(T[(Inicial + i) % M].Chave,Vazio) != 0) && (strcmp(T[(Inicial + i) % M].Chave,Retirado) != 0) && (i < M)) i++; if (i < M) { /* Copiar os demais campos de x, se existirem */ strcpy (T[(Inicial + i) % M].Chave, x.Chave); } else printf(" Tabela cheia\n");}

    David MenottiAlgoritmos e Estrutura de Dados I

    Estrutura do Dicionrio Usando Endereamento Abertovoid Retira(TipoChave Ch, TipoPesos p, TipoDicionario T){ Indice i; i = Pesquisa(Ch, p, T); if (i < M) memcpy(T[i].Chave, Retirado, n); else printf("Registro nao esta presente\n");}

    David MenottiAlgoritmos e Estrutura de Dados I

    AnliseSeja = N/M o fator de carga da tabela. Conforme demonstrado por Knuth (1973), o custo de uma pesquisa com sucesso

    O hashing linear sofre de um mal chamado agrupamento(clustering) (Knuth, 1973, pp.520521).

    Este fenmeno ocorre na medida em que a tabela comea a car cheia, pois a insero de uma nova chave tende a ocupar uma posio na tabela que esteja contgua a outras posies j ocupadas, o que deteriora o tempo necessrio para novas pesquisas.

    David MenottiAlgoritmos e Estrutura de Dados I

    AnliseEntretanto, apesar do hashing linear ser um mtodo relativamente pobre para resolver colises os resultados apresentados so bons.O melhor caso, assim como o caso mdio, O(1).

    David MenottiAlgoritmos e Estrutura de Dados I

    Vantagens e Desvantagens de Transformaes de ChavesVantagens:Alta ecincia no custo de pesquisa, que O(1) para o caso mdio.Simplicidade de implementaoDesvantagens:Custo para recuperar os registros na ordem lexicogrca das chaves alto, sendo necessrio ordenar o arquivo.Pior caso O(N)