Tabela HASH C++

[Pedro Vinicius Siqueira 1]

Boa noite galera. Tenho que fazer um programa que leia uma palavra e retorne se esta palavra é uma palavra reservada da linguagem C ou não. Para fazer isso tenho que utilzar uma tabela hash.

Bem até o momento eu não sei começar esse programa em C++. A minha dúvida é a seguinte. Eu tenho uma lista de palavras reservadas que somam ao todo 62 palavras e 369 caracteres. Qual a melhor função matemática/função hash que eu posso usar para simplificar a busca com essa quantidade de palavras? Quero evitar o máximo de dispersão. Gostaria de saber também como iniciar essa tabela em C++. Toda ajuda é bem vinda. Obrigado gente.

[guidjos 65]

Pra mim não ficou claro se você precisa implementar a função de hashing ou não.

 

Se não precisar, e puder usar bibliotecas já disponíveis, sugiro usar md5. Na verdade, como são tão poucos registros, não importa muito...

 

Se precisar implementar, a estória é outra. Nesse caso sugiro algum algoritmo simples. Seu professor deve ter recomendado algum. Se não, as aulas a partir desta abaixo, do MIT, disponibilizadas de graça, introduzem muito bem o assunto:

 

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-7-hashing-hash-functions/

[Pedro Vinicius Siqueira 1]

Era exatamente isso que eu precisava. Obrigado.

[Pedro Vinicius Siqueira 1]

Galera consegui fazer. Vou postar aqui para os demais que talvez tem dúvida sobre esse assunto. Fiz esse programa porque precisava de fazer um exercício aonde o usuário vai digitar alguma palavra reservada qualquer e tem que retornar para ele se ela está ou não na lista. Foi solicitado também o uso de uma tabela hash.

 

hash.cpp

#include <iostream>
#include <iostream>
#include "hash.h"
#include <string>
#include <cstdlib>

using namespace std;

hash::hash()
{
   for(int i = 0; i < TamanhoTabela; i++){
       TabelaHash[i] = new item;
       TabelaHash[i]->reservada = "vazio";
       TabelaHash[i]->prox = NULL;
   }
}

void hash::Inserir(string reservada)
{
   int indice = Hash(reservada);

   if(TabelaHash[indice]->reservada == "vazio")
   {
       TabelaHash[indice]->reservada = reservada;
   }
   else{
       item* ptr = TabelaHash[indice];
       item* n = new item;
       n->reservada = reservada;
       n->prox = NULL;
       while(ptr->prox != NULL){//faz o ponteiro percorrer até o final da table
           ptr = ptr->prox;
       }
       ptr->prox = n;
   }
}

int hash::NumeroDeItensNaLista(int indice){
   int contagem = 0;

   if(TabelaHash[indice]->reservada=="vazio"){
       return contagem;
   }
   else{
       contagem++;
       item* ptr = TabelaHash[indice];
       while(ptr->prox != NULL){
           contagem++;
           ptr = ptr->prox;
       }
   }
   return contagem;
}


void hash::ImprimirTabela(){
   int numero;

   for(int i = 0;i < TamanhoTabela; i++){
       numero = NumeroDeItensNaLista(i);
       cout<<"-------------------\n";
       cout<<"indice = "<<i<<endl;
       cout<<TabelaHash[i]->reservada <<endl;
       cout<<"# de itens na neste indice: "<<numero<<endl;
       cout<<"-------------------\n";
   }
}

void hash::ImprimirItensNoIndice(int indice){
   item* ptr = TabelaHash[indice];

   if(ptr->reservada == "vazio"){
       cout<<"indice = "<<indice<<" esta vazio"<<endl;
   }
   else{
       cout<<"indice = "<<indice<<" tem os seguintes itens: "<<endl;
       while(ptr!=NULL){
           cout<<"-------------------\n";
           cout<<ptr->reservada <<endl;
           cout<<"-------------------\n";
           ptr = ptr->prox;
       }
   }
}

int hash::Hash(string chave){
   int hash = 0;
   int indice;


   for(int i = 0; i<chave.length();i++)
   {
       hash = hash + (int)chave[i];
   }

   indice = hash % TamanhoTabela;

   return indice;

}

void hash::BuscaPalavra(string reservada){
   int indice = Hash(reservada);
   bool EncontrarPalavra = false;
   string palavra;

   item* ptr = TabelaHash[indice];
   while(ptr != NULL){        //percorrer a tabela
       if(ptr->reservada == reservada){
           EncontrarPalavra = true;
           palavra = ptr->reservada;
       }
       ptr=ptr->prox;
   }
   if(EncontrarPalavra == true){
       cout<<"A palavra esta na tabela"<<endl;
   }
   else{
       cout<<reservada<< " nao esta na tabela"<<endl;

   }
}

hash::~hash()
{
  item* ptr;
  for(int i=0;i<TamanhoTabela;i++)
  {
     while(TabelaHash[i] != NULL)
     {
        ptr = TabelaHash[i];
        TabelaHash[i] = TabelaHash[i]->prox;
        delete ptr;
     }
  }
}

hash.h

#ifndef HASH_H
#define HASH_H

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

class hash
{
private:
   static const int TamanhoTabela = 10; //define o tamanho da tabela dentro da classe

   struct item{
       string reservada;
       item *prox;
   };

   item* TabelaHash[TamanhoTabela]; //ponteiro com o tamanho da tabela

public:
   int Hash(string chave);
   void Inserir(string reservada);
   int NumeroDeItensNaLista(int indice);
   void ImprimirTabela();
   void ImprimirItensNoIndice(int indice);
   void BuscaPalavra(string reservada);

   hash();
   ~hash();

};

#endif // HASH_H

main.cpp

#include <iostream>
#include "hash.h"
#include <string>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
   hash ObjetoHash;

   ObjetoHash.Inserir("auto");
   ObjetoHash.Inserir("asm");
   ObjetoHash.Inserir("bool");
   ObjetoHash.Inserir("break");
   ObjetoHash.Inserir("case");
   ObjetoHash.Inserir("catch");
   ObjetoHash.Inserir("char");
   ObjetoHash.Inserir("class");
   ObjetoHash.Inserir("const");
   ObjetoHash.Inserir("const_cast");
   ObjetoHash.Inserir("continue");
   ObjetoHash.Inserir("default");
   ObjetoHash.Inserir("delete");
   ObjetoHash.Inserir("do");
   ObjetoHash.Inserir("double");
   ObjetoHash.Inserir("dynamic_cast");
   ObjetoHash.Inserir("else");
   ObjetoHash.Inserir("enum");
   ObjetoHash.Inserir("explicit");
   ObjetoHash.Inserir("extern");
   ObjetoHash.Inserir("false");
   ObjetoHash.Inserir("float");
   ObjetoHash.Inserir("for");
   ObjetoHash.Inserir("friend");
   ObjetoHash.Inserir("goto");
   ObjetoHash.Inserir("if");
   ObjetoHash.Inserir("inline");
   ObjetoHash.Inserir("int");
   ObjetoHash.Inserir("long");
   ObjetoHash.Inserir("mutable");
   ObjetoHash.Inserir("namespace");
   ObjetoHash.Inserir("new");
   ObjetoHash.Inserir("operator");
   ObjetoHash.Inserir("private");
   ObjetoHash.Inserir("protected");
   ObjetoHash.Inserir("public");
   ObjetoHash.Inserir("register");
   ObjetoHash.Inserir("reinterpret_cast");
   ObjetoHash.Inserir("return");
   ObjetoHash.Inserir("short");
   ObjetoHash.Inserir("signed");
   ObjetoHash.Inserir("sizeof");
   ObjetoHash.Inserir("static");
   ObjetoHash.Inserir("static_cast");
   ObjetoHash.Inserir("struct");
   ObjetoHash.Inserir("switch");
   ObjetoHash.Inserir("template");
   ObjetoHash.Inserir("this");
   ObjetoHash.Inserir("throw");
   ObjetoHash.Inserir("true");
   ObjetoHash.Inserir("try");
   ObjetoHash.Inserir("typedef");
   ObjetoHash.Inserir("typeid");
   ObjetoHash.Inserir("typename");
   ObjetoHash.Inserir("union");
   ObjetoHash.Inserir("unsigned");
   ObjetoHash.Inserir("using");
   ObjetoHash.Inserir("virtual");
   ObjetoHash.Inserir("void");
   ObjetoHash.Inserir("volatile");
   ObjetoHash.Inserir("wchar_t");
   ObjetoHash.Inserir("while");

   int opcao=0;
   int aux;
   string palavra = "";

   while (opcao!=4){
       cout<<"      **** MENU ****"<<endl<<endl;
       cout<<"Total de palavras reservadas = 62\nEspalhadas em uma tabela hash de tamanho 10\n\n";
       cout<<"1 - Buscar uma palavra reservada"<<endl;
       cout<<"2 - Imprimir tabela por indice"<<endl;
       cout<<"3 - Imprimir toda a tabela"<<endl;
       cout<<"4 - Para finalizar"<<endl;

       cout<<endl<<endl<<"Digite sua opcao: "<<endl;
       cin>>opcao;
       switch(opcao){
       case 1:
           while(palavra!="sair"){
               cout<<"Para terminar a busca, digite sair\nBuscar por: "<<endl;
               cin>>palavra;
               if(palavra != "sair"){
                   ObjetoHash.BuscaPalavra(palavra);
               }
           }
           break;
       case 2:
           cout<<endl<<"Digite o indice que deseja imprimir\nOBS: de 0 a 9"<<endl;
           cin>>aux;
           if(aux == 0 ){
               ObjetoHash.ImprimirItensNoIndice(0);
               cout<<endl;
           }
           if(aux == 1 ){
               ObjetoHash.ImprimirItensNoIndice(1);
               cout<<endl;
           }
           if(aux == 2 ){
               ObjetoHash.ImprimirItensNoIndice(2);
               cout<<endl;
           }
           if(aux == 3 ){
               ObjetoHash.ImprimirItensNoIndice(3);
               cout<<endl;
           }
           if(aux == 4 ){
               ObjetoHash.ImprimirItensNoIndice(4);
               cout<<endl;
           }
           if(aux == 5 ){
               ObjetoHash.ImprimirItensNoIndice(5);
               cout<<endl;
           }
           if(aux == 6 ){
               ObjetoHash.ImprimirItensNoIndice(6);
               cout<<endl;
           }
           if(aux == 7 ){
               ObjetoHash.ImprimirItensNoIndice(7);
               cout<<endl;
           }
           if(aux == 8 ){
               ObjetoHash.ImprimirItensNoIndice(8);
               cout<<endl;
           }
           if(aux == 9 ){
               ObjetoHash.ImprimirItensNoIndice(9);
               cout<<endl;
           }
           break;
       case 3:
           cout<<endl;
           ObjetoHash.ImprimirTabela();
           break;
       default:
           cout<<"Escolha invalida!"<<endl<<endl;
           break;
       }
       return 0;
   }
}