Advertisement
ricco_soares

trying to implement the hash table in cpp

Nov 24th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include<iostream>
  2. #include<list>
  3. #include<vector>
  4. #include<cmath>
  5. using namespace std;
  6.  
  7. class hashtable{
  8.     public:
  9.    
  10.     list<string> table[5];
  11.     int size;  
  12.     int elements_count;
  13.     int collisions_count;  
  14.  
  15.     void insert(string s){
  16.     //consists in generating the hash function of the correspondent string and doing the push_back in table[hash]  
  17.         int h = hash(s);
  18.         table[h].push_back(s);
  19.         collisions_count++;
  20.    
  21.     }
  22.  
  23.     int hash(string s){
  24.         int cont=0;
  25.         int hax=0;
  26.         int ind =0;
  27.         int p=31; //arbitrary value that fits very well when equal to 31.
  28.         for(int i=0;i<s.size();i++)
  29.         {      
  30.             hax=int(hax+ int(s[i])*pow(p,cont))%size;
  31.             cont++;    
  32.         };
  33.         return hax;
  34.    
  35.     }
  36.  
  37.     void search(string s){
  38.         int index = hash(s);
  39.         int cont=0;
  40.         for(auto x: table[index])
  41.         {
  42.             cont++;
  43.             if(x == s)
  44.             {
  45.                 cout<<s<<" encontrado(a) no index: "<<index<<" apos: "<<cont<<" acessos.";
  46.                 break;
  47.             }  
  48.         }  
  49.     }
  50.    
  51.     void del(string s){
  52.  
  53.  
  54.  
  55.    
  56.     }
  57.     void print(){
  58.         //just in case
  59.         for(int i=0;i<size;i++)
  60.         {
  61.             for(auto d: table[i])
  62.                 cout<<d<<" ";
  63.             cout<<", ";
  64.        
  65.         }
  66.         cout<<endl;
  67.     }
  68. };
  69.  
  70. int main(void){
  71.     hashtable h;
  72.     h.size = 5;
  73.     h.elements_count = 0;
  74.     h.collisions_count=0;
  75.    
  76.     //time to learn to print an array of lists of strings :]
  77.     //think we should start declaring one ;]
  78.     int v=3;   
  79.     list<string>l[v];
  80.     string au;
  81.     getline(cin,au);
  82.     h.insert(au);
  83.     getline(cin,au);
  84.     h.insert(au);
  85.     getline(cin,au);
  86.     h.insert(au);
  87.     h.print();
  88.     cout<<"insira uma palavra para ser buscada"<<endl;
  89.     getline(cin,au);
  90.     h.search(au);
  91.    
  92.  
  93.    
  94.    
  95.     cout<<endl;
  96.     //h.print();
  97.  
  98.  
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement