document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. // Program to implement Hashing with Quadratic Probing
  2. #include<iostream>
  3. #include<math.h>
  4. #define SIZE 13
  5. using namespace std;
  6.  
  7. class hashTable{
  8.    
  9.     private:
  10.         int table[SIZE], elementCount;
  11.    
  12.     public:
  13.    
  14.         // initialize hash Table
  15.         hashTable(){
  16.             for(int i=0; i < SIZE; i++){
  17.                 table[i] = 0;
  18.             }
  19.             elementCount = 0;
  20.         }
  21.        
  22.         // method that checks if the hash table is full or not
  23.         bool isFull(){
  24.             if(elementCount == SIZE){
  25.                 return true;
  26.             }else{
  27.                 return false;
  28.             }
  29.         }
  30.        
  31.        
  32.         // method that returns position for a given element
  33.         int hashFunction(int element){
  34.             return element % SIZE;
  35.         }  
  36.        
  37.         // method that finds the next empty position using quadratic probing
  38.         int quadraticProbing(int element, int position){
  39.             int limit = 50, i = 1;
  40.             int newPosition = -1;
  41.             while(i <= 50){
  42.                 newPosition = this->hashFunction(position + (int)pow(i, 2));
  43.                 if(this->table[newPosition] == 0){
  44.                     break;
  45.                 }
  46.                 else{
  47.                     i++;
  48.                 }
  49.             }
  50.             return newPosition;
  51.         }
  52.        
  53.         // method that inserts element inside the hash table
  54.         void insert(int element){
  55.             int position;
  56.             // checking if the table is full
  57.             if(this->isFull()){
  58.                 cout<<"\\nHash Table Full";
  59.                 return;
  60.             }  
  61.            
  62.             bool isStored = false;
  63.            
  64.             position = this->hashFunction(element);
  65.                
  66.             // checking if the position is empty
  67.             if(table[position] == 0){
  68.                 table[position] = element;
  69.                 cout<<"\\nElement " <<element<<" stored at position " <<position;
  70.                 isStored = true;
  71.                 elementCount += 1;
  72.             }  
  73.            
  74.             // collision occured hence we do linear probing
  75.             else{
  76.                 cout<<"\\nCollision has occured for element " <<element<<" at position " <<position<<" finding new Position.";
  77.                 position = quadraticProbing(element, position);
  78.                 if(position != -1){
  79.                     this->table[position] = element;
  80.                     elementCount += 1;
  81.                     cout<<"\\nElement " <<element<<" stored at position " <<position;
  82.                 }
  83.                
  84.             }  
  85.             return;
  86.         }  
  87.  
  88.         // method that searches for an element in the table
  89.         // returns position of element if found
  90.         // else returns false
  91.         int search(int element){
  92.             bool found = false;
  93.            
  94.             int position = this->hashFunction(element);
  95.            
  96.             if(table[position] == element){
  97.                 found = true;
  98.                 return position;
  99.             }  
  100.            
  101.             // if element is not found at position returned hash function
  102.             // then we search element using quadratic probing
  103.             else{
  104.                 int limit = 50, i = 1;
  105.                 int newPosition = -1;
  106.                 while(i <= 50){
  107.                     newPosition = this->hashFunction(position + (int)pow(i, 2));
  108.                     if(this->table[newPosition] == element){
  109.                         found = true;
  110.                         break;
  111.                     }
  112.                     else{
  113.                         i++;
  114.                     }
  115.                 }
  116.                 if(found){
  117.                     return newPosition;
  118.                 }
  119.                 else{
  120.                     cout<<"Element not found";
  121.                     return -1;
  122.                 }
  123.             }  
  124.         }  
  125.        
  126.        
  127.         // method to remove an element from the table      
  128.         void remove(int element){
  129.             int position = this->search(element);
  130.             if(position != -1){
  131.                 table[position] = 0;
  132.                 cout<<"\\nElement " <<element<<" is Deleted";
  133.                 this->elementCount -= 1;
  134.             }else{
  135.                 cout<<"\\nElement is not present in the Hash Table";
  136.             }
  137.             return;
  138.         }  
  139.        
  140.         // method to display the hash table
  141.         void display(){
  142.             for (int i = 0; i < SIZE; i++){
  143.                 cout<<"\\n"<<i<<" = "<<table[i];
  144.             }  
  145.             cout<<"\\nThe number of element is the Table are : " <<this->elementCount;
  146.         }  
  147. };     
  148.  
  149. int main(){
  150.     // main function
  151.     hashTable table1;
  152.  
  153.     // storing elements in table
  154.     table1.insert(12);
  155.     table1.insert(26);
  156.     table1.insert(31);
  157.     table1.insert(17);
  158.     table1.insert(90);
  159.     table1.insert(28);
  160.     table1.insert(88);
  161.     table1.insert(40);
  162.     table1.insert(77);      // element that causes collision at position 0
  163.  
  164.     // displaying the Table
  165.     table1.display();
  166.     cout<<"\\n";
  167.  
  168.     // printing position of elements
  169.     cout<<"\\nThe position of element 31 is : " <<table1.search(31);
  170.     cout<<"\\nThe position of element 28 is : " <<table1.search(28);
  171.     cout<<"\\nThe position of element 90 is : " <<table1.search(90);
  172.     cout<<"\\nThe position of element 77 is : " <<table1.search(77);
  173.     cout<<"\\nThe position of element 1 is : " <<table1.search(1);
  174.  
  175.     cout<<"\\n";
  176.  
  177.     table1.remove(90);
  178.     table1.remove(12);
  179.  
  180.     table1.display();
  181. }
');