Função Hashing

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.

[Tens de ter uma conta e sessão iniciada para poderes visualizar 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.

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);
}