logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

C++ Program to Implement Hash Tables with Quadratic Probing

Posted on August 28, 2013 by Manish
This C++ Program demonstrates operations on Hash Tables with Quadratic Probing.

Here is source code of the C++ Program to demonstrate Hash Tables with Quadratic Probing. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Hash Tables with Quadratic Probing
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #define MIN_TABLE_SIZE 10
  7. using namespace std;
  8. /*
  9.  * Node Type Declaration
  10.  */
  11. enum EntryType {Legitimate, Empty, Deleted};
  12. /*
  13.  * Node Declaration
  14.  */
  15. struct HashNode
  16. {
  17.     int element;
  18.     enum EntryType info;
  19. };
  20. /*
  21.  * Table Declaration
  22.  */
  23. struct HashTable
  24. {
  25.     int size;
  26.     HashNode *table;
  27. };
  28. /*
  29.  * Returns whether n is prime or not
  30.  */
  31. bool isPrime (int n)
  32. {
  33.     if (n == 2 || n == 3)
  34.         return true;
  35.     if (n == 1 || n % 2 == 0)
  36.         return false;
  37.     for (int i = 3; i * i <= n; i += 2)
  38.         if (n % i == 0)
  39.             return false;
  40.     return true;
  41. }
  42. /*
  43.  * Finding next prime size of the table
  44.  */
  45. int nextPrime(int n)
  46. {
  47.     if (n <= 0)
  48.         n == 3;
  49.     if (n % 2 == 0)
  50.         n++;
  51.     for (; !isPrime( n ); n += 2);
  52.     return n;
  53. }
  54. /*
  55.  * Function To Generate Hash
  56.  */
  57. int HashFunc(int key, int size)
  58. {
  59.     return key % size;
  60. }
  61. /*
  62.  * Function to Initialize Table
  63.  */
  64. HashTable *initializeTable(int size)
  65. {
  66.     HashTable *htable;
  67.     if (size < MIN_TABLE_SIZE)
  68.     {
  69.         cout<<"Table Size Too Small"<<endl;
  70.         return NULL;
  71.     }
  72.     htable = new HashTable;
  73.     if (htable == NULL)
  74.     {
  75.         cout<<"Out of Space"<<endl;
  76.         return NULL;
  77.     }
  78.     htable->size = nextPrime(size);
  79.     htable->table = new HashNode [htable->size];
  80.     if (htable->table == NULL)
  81.     {
  82.         cout<<"Table Size Too Small"<<endl;
  83.         return NULL;
  84.     }
  85.     for (int i = 0; i < htable->size; i++)
  86.     {
  87.         htable->table[i].info = Empty;
  88.         htable->table[i].element = NULL;
  89.     }
  90.     return htable;
  91. }
  92. /*
  93.  * Function to Find Element at a key
  94.  */
  95. int Find(int key, HashTable *htable)
  96. {
  97.     int pos = HashFunc(key, htable->size);
  98.     int collisions = 0;
  99.     while (htable->table[pos].info != Empty &&
  100.            htable->table[pos].element != key)
  101.     {
  102.         pos = pos + 2 * ++collisions -1;
  103.         if (pos >= htable->size)
  104.             pos = pos - htable->size;
  105.     }
  106.     return pos;
  107. }
  108. /*
  109.  * Function to Insert Element into a key
  110.  */
  111. void Insert(int key, HashTable *htable)
  112. {
  113.     int pos = Find(key, htable);
  114.     if (htable->table[pos].info != Legitimate)
  115.     {
  116.         htable->table[pos].info = Legitimate;
  117.         htable->table[pos].element = key;
  118.     }
  119. }
  120. /*
  121.  * Function to Rehash the Table
  122.  */
  123. HashTable *Rehash(HashTable *htable)
  124. {
  125.     int size = htable->size;
  126.     HashNode *table = htable->table;
  127.     htable = initializeTable(2 * size);
  128.     for (int i = 0; i < size; i++)
  129.     {
  130.         if (table[i].info == Legitimate)
  131.             Insert(table[i].element, htable);
  132.     }
  133.     free(table);
  134.     return htable;
  135. }
  136. /*
  137.  * Function to Retrieve Hash Table
  138.  */
  139. void Retrieve(HashTable *htable)
  140. {
  141.     for (int i = 0; i < htable->size; i++)
  142.     {
  143.         int value = htable->table[i].element;
  144.         if (!value)
  145.             cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
  146.         else
  147.             cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
  148.     }
  149.  
  150. }
  151. /*
  152.  * Main Contains Menu
  153.  */
  154. int main()
  155. {
  156.     int value, size, pos, i = 1;
  157.     int choice;
  158.     HashTable *htable;
  159.     while(1)
  160.     {
  161.         cout<<"\n----------------------"<<endl;
  162.         cout<<"Operations on Quadratic Probing"<<endl;
  163.         cout<<"\n----------------------"<<endl;
  164.         cout<<"1.Initialize size of the table"<<endl;
  165.         cout<<"2.Insert element into the table"<<endl;
  166.         cout<<"3.Display Hash Table"<<endl;
  167.         cout<<"4.Rehash The Table"<<endl;
  168.         cout<<"5.Exit"<<endl;
  169.         cout<<"Enter your choice: ";
  170.         cin>>choice;
  171.         switch(choice)
  172.         {
  173.         case 1:
  174.             cout<<"Enter size of the Hash Table: ";
  175.             cin>>size;
  176.             htable = initializeTable(size);
  177.             cout<<"Size of Hash Table: "<<nextPrime(size);
  178.             break;
  179.         case 2:
  180.             if (i > htable->size)
  181.             {
  182.                 cout<<"Table is Full, Rehash the table"<<endl;
  183.                 continue;
  184.             }
  185.         	cout<<"Enter element to be inserted: ";
  186.         	cin>>value;
  187.             Insert(value, htable);
  188.             i++;
  189.             break;
  190.         case 3:
  191.             Retrieve(htable);
  192.             break;
  193.         case 4:
  194.             htable = Rehash(htable);
  195.             break;
  196.         case 5:
  197.             exit(1);
  198.         default:
  199.            cout<<"\nEnter correct option\n";
  200.        }
  201.     }
  202.     return 0;
  203. }

advertisement
$ g++ Quadratic_Probing.cpp
$ a.out
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 5
Table Size Too Small
Size of Hash Table: 5
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 10
Size of Hash Table: 11
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 100
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 200
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 300
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 400
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 500
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 600
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 700
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 800
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 900
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1000
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1100
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 1100
Position: 2 Element: 100
Position: 3 Element: 200
Position: 4 Element: 300
Position: 5 Element: 400
Position: 6 Element: 500
Position: 7 Element: 600
Position: 8 Element: 700
Position: 9 Element: 800
Position: 10 Element: 900
Position: 11 Element: 1000
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: Null
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2200
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3300
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4400
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5500
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6600
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: 5500
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: 4400
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: 3300
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: 2200
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: 6600
 
----------------------
Operations on Quadratic Probing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
« Prev Page - C++ Program to Check for balanced paranthesis by using Stacks
» Next Page - C++ Program to Implement Hash Tables Chaining with List Heads

« C# Program to Illustrate Bitwise Operations
C++ Program to Implement Hash Tables Chaining with List Heads »

Deep Dive @ Sanfoundry:

  1. C Programming Examples on Linked List
  2. C# Programming Examples on Matrix
  3. C# Programming Examples on Mathematics
  4. C# Programming Examples on Sorting
  5. Data Structure Questions and Answers
  6. C Programming Examples on Mathematical Functions
  7. Java Programming Examples on Collection API
  8. Java Programming Examples on Data-Structures
  9. C++ Programming Examples on Data-Structures
  10. C Programming Examples on Data-Structures
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.