fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. /*
  5.     ============================================================
  6.     LINEAR PROBING
  7.     ============================================================
  8. */
  9.  
  10. class LinearProbingHashTable {
  11. private:
  12.     int* table;
  13.     int tableSize;
  14.     int count;
  15.     const int EMPTY = -1;
  16.  
  17.     int hashFunction(int key) {
  18.         return key % tableSize;
  19.     }
  20.  
  21. public:
  22.     LinearProbingHashTable(int size) {
  23.         tableSize = size;
  24.         count = 0;
  25.         table = new int[tableSize];
  26.  
  27.         for (int i = 0; i < tableSize; i++) {
  28.             table[i] = EMPTY;
  29.         }
  30.     }
  31.  
  32.     ~LinearProbingHashTable() {
  33.         delete[] table;
  34.     }
  35.  
  36.     bool insert(int key) {
  37.         if (count == tableSize) {
  38.             return false;
  39.         }
  40.  
  41.         int h = hashFunction(key);
  42.  
  43.         while (table[h] != EMPTY) {
  44.             h = (h + 1) % tableSize;
  45.         }
  46.  
  47.         table[h] = key;
  48.         count++;
  49.         return true;
  50.     }
  51.  
  52.     bool search(int key) {
  53.         int h = hashFunction(key);
  54.         int start = h;
  55.  
  56.         while (true) {
  57.             if (table[h] == EMPTY) {
  58.                 return false;
  59.             }
  60.  
  61.             if (table[h] == key) {
  62.                 return true;
  63.             }
  64.  
  65.             h = (h + 1) % tableSize;
  66.  
  67.             if (h == start) {
  68.                 return false;
  69.             }
  70.         }
  71.     }
  72.  
  73.     void print() {
  74.         cout << "Linear Probing:\n";
  75.  
  76.         for (int i = 0; i < tableSize; i++) {
  77.             cout << "[" << i << "] ";
  78.  
  79.             if (table[i] == EMPTY) {
  80.                 cout << "EMPTY";
  81.             } else {
  82.                 cout << table[i];
  83.             }
  84.  
  85.             cout << endl;
  86.         }
  87.     }
  88. };
  89.  
  90. /*
  91.     ============================================================
  92.     QUADRATIC PROBING
  93.     ============================================================
  94. */
  95.  
  96. class QuadraticProbingHashTable {
  97. private:
  98.     int* table;
  99.     int tableSize;
  100.     int count;
  101.     const int EMPTY = -1;
  102.  
  103.     int hashFunction(int key) {
  104.         return key % tableSize;
  105.     }
  106.  
  107. public:
  108.     QuadraticProbingHashTable(int size) {
  109.         tableSize = size;
  110.         count = 0;
  111.         table = new int[tableSize];
  112.  
  113.         for (int i = 0; i < tableSize; i++) {
  114.             table[i] = EMPTY;
  115.         }
  116.     }
  117.  
  118.     ~QuadraticProbingHashTable() {
  119.         delete[] table;
  120.     }
  121.  
  122.     bool insert(int key) {
  123.         if (count == tableSize) {
  124.             return false;
  125.         }
  126.  
  127.         int h = hashFunction(key);
  128.  
  129.         for (int attempt = 0; attempt < tableSize; attempt++) {
  130.             int index = (h + attempt * attempt) % tableSize;
  131.  
  132.             if (table[index] == EMPTY) {
  133.                 table[index] = key;
  134.                 count++;
  135.                 return true;
  136.             }
  137.         }
  138.  
  139.         return false;
  140.     }
  141.  
  142.     bool search(int key) {
  143.         int h = hashFunction(key);
  144.  
  145.         for (int attempt = 0; attempt < tableSize; attempt++) {
  146.             int index = (h + attempt * attempt) % tableSize;
  147.  
  148.             if (table[index] == EMPTY) {
  149.                 return false;
  150.             }
  151.  
  152.             if (table[index] == key) {
  153.                 return true;
  154.             }
  155.         }
  156.  
  157.         return false;
  158.     }
  159.  
  160.     void print() {
  161.         cout << "Quadratic Probing:\n";
  162.  
  163.         for (int i = 0; i < tableSize; i++) {
  164.             cout << "[" << i << "] ";
  165.  
  166.             if (table[i] == EMPTY) {
  167.                 cout << "EMPTY";
  168.             } else {
  169.                 cout << table[i];
  170.             }
  171.  
  172.             cout << endl;
  173.         }
  174.     }
  175. };
  176.  
  177. /*
  178.     ============================================================
  179.     DOUBLE HASHING
  180.     ============================================================
  181. */
  182.  
  183. class DoubleHashingHashTable {
  184. private:
  185.     int* table;
  186.     int tableSize;
  187.     int count;
  188.     int R;
  189.     const int EMPTY = -1;
  190.  
  191.     int hash1(int key) {
  192.         return key % tableSize;
  193.     }
  194.  
  195.     int hash2(int key) {
  196.         return R - (key % R);
  197.     }
  198.  
  199. public:
  200.     DoubleHashingHashTable(int size, int primeLessThanSize) {
  201.         tableSize = size;
  202.         R = primeLessThanSize;
  203.         count = 0;
  204.         table = new int[tableSize];
  205.  
  206.         for (int i = 0; i < tableSize; i++) {
  207.             table[i] = EMPTY;
  208.         }
  209.     }
  210.  
  211.     ~DoubleHashingHashTable() {
  212.         delete[] table;
  213.     }
  214.  
  215.     bool insert(int key) {
  216.         if (count == tableSize) {
  217.             return false;
  218.         }
  219.  
  220.         int h1 = hash1(key);
  221.         int h2 = hash2(key);
  222.  
  223.         for (int attempt = 0; attempt < tableSize; attempt++) {
  224.             int index = (h1 + attempt * h2) % tableSize;
  225.  
  226.             if (table[index] == EMPTY) {
  227.                 table[index] = key;
  228.                 count++;
  229.                 return true;
  230.             }
  231.         }
  232.  
  233.         return false;
  234.     }
  235.  
  236.     bool search(int key) {
  237.         int h1 = hash1(key);
  238.         int h2 = hash2(key);
  239.  
  240.         for (int attempt = 0; attempt < tableSize; attempt++) {
  241.             int index = (h1 + attempt * h2) % tableSize;
  242.  
  243.             if (table[index] == EMPTY) {
  244.                 return false;
  245.             }
  246.  
  247.             if (table[index] == key) {
  248.                 return true;
  249.             }
  250.         }
  251.  
  252.         return false;
  253.     }
  254.  
  255.     void print() {
  256.         cout << "Double Hashing:\n";
  257.  
  258.         for (int i = 0; i < tableSize; i++) {
  259.             cout << "[" << i << "] ";
  260.  
  261.             if (table[i] == EMPTY) {
  262.                 cout << "EMPTY";
  263.             } else {
  264.                 cout << table[i];
  265.             }
  266.  
  267.             cout << endl;
  268.         }
  269.     }
  270. };
  271.  
  272. /*
  273.     ============================================================
  274.     CHAINING
  275.     ============================================================
  276. */
  277.  
  278. class ChainingHashTable {
  279. private:
  280.     struct Node {
  281.         int key;
  282.         Node* next;
  283.  
  284.         Node(int k) {
  285.             key = k;
  286.             next = nullptr;
  287.         }
  288.     };
  289.  
  290.     Node** table;
  291.     int tableSize;
  292.  
  293.     int hashFunction(int key) {
  294.         return key % tableSize;
  295.     }
  296.  
  297. public:
  298.     ChainingHashTable(int size) {
  299.         tableSize = size;
  300.         table = new Node*[tableSize];
  301.  
  302.         for (int i = 0; i < tableSize; i++) {
  303.             table[i] = nullptr;
  304.         }
  305.     }
  306.  
  307.     ~ChainingHashTable() {
  308.         for (int i = 0; i < tableSize; i++) {
  309.             Node* current = table[i];
  310.  
  311.             while (current != nullptr) {
  312.                 Node* temp = current;
  313.                 current = current->next;
  314.                 delete temp;
  315.             }
  316.         }
  317.  
  318.         delete[] table;
  319.     }
  320.  
  321.     void insert(int key) {
  322.         int index = hashFunction(key);
  323.  
  324.         Node* newNode = new Node(key);
  325.  
  326.         if (table[index] == nullptr) {
  327.             table[index] = newNode;
  328.         } else {
  329.             Node* current = table[index];
  330.  
  331.             while (current->next != nullptr) {
  332.                 current = current->next;
  333.             }
  334.  
  335.             current->next = newNode;
  336.         }
  337.     }
  338.  
  339.     bool search(int key) {
  340.         int index = hashFunction(key);
  341.  
  342.         Node* current = table[index];
  343.  
  344.         while (current != nullptr) {
  345.             if (current->key == key) {
  346.                 return true;
  347.             }
  348.  
  349.             current = current->next;
  350.         }
  351.  
  352.         return false;
  353.     }
  354.  
  355.     void print() {
  356.         cout << "Chaining:\n";
  357.  
  358.         for (int i = 0; i < tableSize; i++) {
  359.             cout << "[" << i << "]";
  360.  
  361.             Node* current = table[i];
  362.  
  363.             while (current != nullptr) {
  364.                 cout << " -> " << current->key;
  365.                 current = current->next;
  366.             }
  367.  
  368.             cout << endl;
  369.         }
  370.     }
  371. };
  372.  
  373. /*
  374.     ============================================================
  375.     MAIN
  376.     ============================================================
  377. */
  378.  
  379. int main() {
  380.     int keys[] = {55, 35, 66, 76, 59, 48, 84, 70};
  381.     int n = 8;
  382.  
  383.     cout << "==============================\n";
  384.     cout << "Linear Probing Example\n";
  385.     cout << "==============================\n";
  386.  
  387.     LinearProbingHashTable linearTable(11);
  388.  
  389.     for (int i = 0; i < n; i++) {
  390.         linearTable.insert(keys[i]);
  391.     }
  392.  
  393.     linearTable.print();
  394.  
  395.     cout << "Search 48: " << (linearTable.search(48) ? "Found" : "Not Found") << endl;
  396.     cout << "Search 100: " << (linearTable.search(100) ? "Found" : "Not Found") << endl;
  397.  
  398.     cout << endl;
  399.  
  400.     cout << "==============================\n";
  401.     cout << "Quadratic Probing Example\n";
  402.     cout << "==============================\n";
  403.  
  404.     QuadraticProbingHashTable quadraticTable(11);
  405.  
  406.     for (int i = 0; i < n; i++) {
  407.         quadraticTable.insert(keys[i]);
  408.     }
  409.  
  410.     quadraticTable.print();
  411.  
  412.     cout << "Search 48: " << (quadraticTable.search(48) ? "Found" : "Not Found") << endl;
  413.     cout << "Search 100: " << (quadraticTable.search(100) ? "Found" : "Not Found") << endl;
  414.  
  415.     cout << endl;
  416.  
  417.     cout << "==============================\n";
  418.     cout << "Double Hashing Example\n";
  419.     cout << "==============================\n";
  420.  
  421.     DoubleHashingHashTable doubleHashTable(11, 7);
  422.  
  423.     for (int i = 0; i < n; i++) {
  424.         doubleHashTable.insert(keys[i]);
  425.     }
  426.  
  427.     doubleHashTable.print();
  428.  
  429.     cout << "Search 48: " << (doubleHashTable.search(48) ? "Found" : "Not Found") << endl;
  430.     cout << "Search 100: " << (doubleHashTable.search(100) ? "Found" : "Not Found") << endl;
  431.  
  432.     cout << endl;
  433.  
  434.     cout << "==============================\n";
  435.     cout << "Chaining Example\n";
  436.     cout << "==============================\n";
  437.  
  438.     ChainingHashTable chainingTable(10);
  439.  
  440.     int chainingKeys[] = {10, 12, 23, 26, 32, 52, 70, 88};
  441.     int chainingN = 8;
  442.  
  443.     for (int i = 0; i < chainingN; i++) {
  444.         chainingTable.insert(chainingKeys[i]);
  445.     }
  446.  
  447.     chainingTable.print();
  448.  
  449.     cout << "Search 52: " << (chainingTable.search(52) ? "Found" : "Not Found") << endl;
  450.     cout << "Search 99: " << (chainingTable.search(99) ? "Found" : "Not Found") << endl;
  451.  
  452.     return 0;
  453. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
==============================
Linear Probing Example
==============================
Linear Probing:
[0] 55
[1] 66
[2] 35
[3] EMPTY
[4] 59
[5] 48
[6] 70
[7] 84
[8] EMPTY
[9] EMPTY
[10] 76
Search 48: Found
Search 100: Not Found

==============================
Quadratic Probing Example
==============================
Quadratic Probing:
[0] 55
[1] 66
[2] 35
[3] EMPTY
[4] 59
[5] 48
[6] EMPTY
[7] 84
[8] 70
[9] EMPTY
[10] 76
Search 48: Found
Search 100: Not Found

==============================
Double Hashing Example
==============================
Double Hashing:
[0] 55
[1] EMPTY
[2] 35
[3] 70
[4] 66
[5] 48
[6] EMPTY
[7] 84
[8] 59
[9] EMPTY
[10] 76
Search 48: Found
Search 100: Not Found

==============================
Chaining Example
==============================
Chaining:
[0] -> 10 -> 70
[1]
[2] -> 12 -> 32 -> 52
[3] -> 23
[4]
[5]
[6] -> 26
[7]
[8] -> 88
[9]
Search 52: Found
Search 99: Not Found
https://ideone.com/wi6Z6K
language:
C++ (gcc 8.3)
created:
4 hours 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!