Função Hashing

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Função Hashing

Mensagem  Renancr em Ter 9 Nov 2010 - 9:33

1) Implemente em C++ duas funções hashing a fim de avaliar qual delas é a melhor. Para realizar esta tarefa, deve-se desenvolver um procedimento que conte quantas colisões ocorreram em uma posição de um vetor qualquer ( H ). Esta posição é o índice que a função hashing gerou. Observe que a função hashing pode criar o mesmo índice a partir de um ou mais valores. Ao final, um histograma deverá ser impresso para ilustrar o total de colisões em cada posição. Considere o seguinte exemplo abaixo:

    [1]Criar um vetor ( V ) com números aleatórios;

    [2]Cada valor do vetor ( V[i] ) será passado como argumento para função hashing que irá gerar um índice;

    [3]O índice gerado pela função é utilizado para incrementar o conteúdo do vetor H;

    [4]Finalmente, será impresso na tela um histograma parar avaliar se a função é boa ou não. No exemplo abaixo, a análise do histograma indica que a função hashing não é boa, pois ela gera o mesmo índice 6 a partir de 8 valores distintos.


[Você precisa estar registrado e conectado para ver esta imagem.]

Abaixo é ilustrado um exemplo de uma função hashing, onde info é o primeiro argumento da função do tipo inteiro e representa o valor a ser utilizado para gerar a chave, enquanto o N é também do tipo inteiro e representa o tamanho do vetor H. A função hash_a irá retornar um valor que será utilizado como índice parar atualizar os valores do vetor H. Utilize esta função como exemplo e implemente mais uma função e avalie qual delas é a melhor.

int hash_a (int info, int N)
{

return (info%N);

}

Código:
#include <iostream>
#include <stdlib.h> //biblioteca para uso da função srand e rand para gerar números aleatórios.
#include <time.h> //biblioteca para uso da função time.
using namespace std;
int const vt1 = 15, vt2 = 12; //definição do tamanho do vetor.

int hash_a(int vet[vt1],int i, int N);
int hash_b(int vet[vt1],int i, int N);

void main()

  int i, vetor1[vt1], vetor2[vt2], vetor3[vt2], indice, cont;
  for(i=0; i < vt2; i++)
  {
    vetor2[i]=0;
    vetor3[i]=0;
  }

  srand((unsigned)time( NULL )); //cria os números aleatórios
  for (i = 0; i < vt1; i++)
    vetor1[i] = rand();  //atribui um valor aleatório para cada posição do vetor

  for(i = 0; i < vt1; i++)
  {
    indice=hash_a(vetor1, i, vt2);
    vetor2[indice]+= 1;
  }
  for(i = 0; i < vt1; i++)
  {
    indice=hash_b(vetor1, i, vt2);
    if(indice == vt2)
    {
       indice-=1;
       vetor3[indice]+= 1;
    }
    else
       vetor3[indice]+= 1;
  }

  for(i=0; i < vt1; i++)
     cout<< " " <<vetor1[i];
  cout<< "\n\n";
  cout<< "\tFuncao Hash solicitada pelo professor\n";
  cout<< "========================================================\n\n";
  for(i=0; i<vt2; i++)
  {
    cont = vetor2[i];
    cout<< "| ";
    while(cont != 0)
    {
        cout<< ".";
        cont--;
    }
    cout<< "\n";
  }
  cout<< "\n========================================================\n\n\n";
  cout<< "\t\tFuncao Hash encontrada\n";
  cout<< "========================================================\n\n";
  for(i=0; i<vt2; i++)
  {
    cont = vetor3[i];
    cout<< "| ";
    while(cont != 0)
    {
        cout<< ".";
        cont--;
    }
    cout<< "\n";
  }
  cout<< "\n========================================================\n\n\n";
}

int hash_a(int vet[vt1],int i, int N)
{
   return (vet[i]%N);
}

int hash_b(int vet[vt1],int i, int N)
{
   return ((vet[i]*N)%vt1);
}
avatar
Renancr

Mensagens : 118
Data de inscrição : 08/03/2010

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum