fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Chaining idea to reduce Collision
  5.  
  6. int hash_string(string name , int limit){
  7.         long long sum=0, nn =limit;
  8.         for(int i=0;i<(int)name.size();i++){
  9.             sum = (sum * 26 + name[i] - 'a') % nn;
  10.         }
  11.     return sum % nn;
  12. }
  13.  
  14. class Entry{
  15.     public:
  16.     const static int Internal_limit=65407;
  17.     string name;//key
  18.     string phoneNumber;//data
  19.  
  20.     Entry(string name,string phoneNumber):
  21.         name(name),phoneNumber(phoneNumber){
  22.     }
  23.  
  24.     int hash(){
  25.         return  hash_string(name,Internal_limit);
  26.     }
  27.  
  28.     void print(){
  29.         cout <<setw(2)<< " ("<<name <<", "<<phoneNumber<<") "<<'\n';
  30.     }
  31. };
  32.  
  33. class HashTable{
  34.     private:
  35.     int table_size{0};
  36.     vector<Entry*>table;
  37.     Entry* deleted = new Entry(""," ");
  38.  
  39.     public:
  40.     HashTable(int table_size):table_size(table_size){
  41.         table.resize(table_size);
  42.     }
  43.     bool put(Entry phone){
  44.         int idx = phone.hash()%table_size;
  45.  
  46.         //max moves is table size steps
  47.         for(int i = 0;i < (int)table_size;i++){
  48.             if(table[i]==deleted || !table[idx]){
  49.                 table[idx] = new Entry (phone.name,phone.phoneNumber);
  50.                 return true;
  51.             }
  52.             else if(table[idx]->name == phone.name){
  53.                 //update
  54.                 table[idx]->phoneNumber =phone.phoneNumber;
  55.                 return true;
  56.             }
  57.             idx =(idx + 1)% table_size;
  58.         }
  59.         return false;
  60.     }
  61.     bool remove(Entry phone){
  62.         int idx = phone.hash()%table_size;
  63.  
  64.         for(int i =0;i<table_size;i++){
  65.             if(!table[idx]) break;
  66.             else if(table[idx]!=deleted and table[idx]->name ==phone.name){
  67.                 delete table[idx];
  68.                 table[idx]=deleted;
  69.                 return true;
  70.             }
  71.             //move one step
  72.             idx =(idx + 1)% table_size;
  73.         }
  74.         return false;
  75.     } 
  76.  
  77.     bool get(Entry phone){
  78.         int idx = phone.hash()%table_size;
  79.  
  80.         for(int i =0;i<table_size;i++){
  81.             if(!table[idx]) break;
  82.             else if(table[idx]!=deleted and table[idx]->name ==phone.name){
  83.                 phone.phoneNumber = table[idx]->phoneNumber;
  84.                 return true;
  85.             }
  86.             //move one step
  87.             idx =(idx + 1)% table_size;
  88.         }
  89.         return false;
  90.     } 
  91.     void print_all(){
  92.         for(int i = 0 ; i < table_size ; i++){
  93.             cout << i <<" ";
  94.             if(table[i]==deleted){
  95.                 cout <<" X ";
  96.             }
  97.             else if(!table[i]){
  98.                 cout<<" E ";
  99.             }
  100.             else{
  101.                 table[i]->print();
  102.             }
  103.             cout <<'\n';
  104.         }
  105.         cout <<"*************************\n";
  106.     }
  107. };
  108. int main(){
  109.     HashTable table(11);
  110.     table.put(Entry("manar","13"));
  111.     table.put(Entry("manora","4"));
  112.     table.put(Entry("mona","830"));
  113.     table.put(Entry("noha","9"));
  114.     table.put(Entry("mohamed","349"));
  115.     table.put(Entry("adam","759"));
  116.     table.print_all();
  117.     cout <<"After removing noha\n";
  118.     table.remove(Entry("noha","9"));
  119.     table.print_all();
  120.  
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0  E 
1  E 
2  (manar, 13) 

3  (noha, 9) 

4  E 
5  (adam, 759) 

6  E 
7  (mona, 830) 

8  E 
9  (manora, 4) 

10  (mohamed, 349) 

*************************
After removing noha
0  E 
1  E 
2  (manar, 13) 

3  X 
4  E 
5  (adam, 759) 

6  E 
7  (mona, 830) 

8  E 
9  (manora, 4) 

10  (mohamed, 349) 

*************************
https://ideone.com/OEHMtH
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!