fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class LinearProbingHashTable {
  5. private:
  6.     int* table;
  7.     int tableSize;
  8.     int count;
  9.     const int EMPTY = -1;
  10.  
  11.     int hashFunction(int key) {
  12.         return key % tableSize;
  13.     }
  14.  
  15. public:
  16.     LinearProbingHashTable(int size) {
  17.         tableSize = size;
  18.         count = 0;
  19.         table = new int[tableSize];
  20.  
  21.         for (int i = 0; i < tableSize; i++) {
  22.             table[i] = EMPTY;
  23.         }
  24.     }
  25.  
  26.     ~LinearProbingHashTable() {
  27.         delete[] table;
  28.     }
  29.  
  30.     bool isFull() {
  31.         return count == tableSize;
  32.     }
  33.  
  34.     bool insert(int key) {
  35.         if (isFull()) {
  36.             return false;
  37.         }
  38.  
  39.         int h = hashFunction(key);
  40.  
  41.         while (table[h] != EMPTY) {
  42.             h = (h + 1) % tableSize;
  43.         }
  44.  
  45.         table[h] = key;
  46.         count++;
  47.         return true;
  48.     }
  49.  
  50.     bool search(int key) {
  51.         int h = hashFunction(key);
  52.         int start = h;
  53.  
  54.         while (true) {
  55.             if (table[h] == EMPTY) {
  56.                 return false;
  57.             }
  58.  
  59.             if (table[h] == key) {
  60.                 return true;
  61.             }
  62.  
  63.             h = (h + 1) % tableSize;
  64.  
  65.             if (h == start) {
  66.                 return false;
  67.             }
  68.         }
  69.     }
  70.  
  71.     void print() {
  72.         for (int i = 0; i < tableSize; i++) {
  73.             cout << "[" << i << "] ";
  74.  
  75.             if (table[i] == EMPTY) {
  76.                 cout << "EMPTY";
  77.             } else {
  78.                 cout << table[i];
  79.             }
  80.  
  81.             cout << endl;
  82.         }
  83.     }
  84. };
  85.  
  86. int main() {
  87.     LinearProbingHashTable table(11);
  88.  
  89.     int keys[] = {55, 35, 66, 76, 59, 48, 84, 70};
  90.  
  91.     for (int key : keys) {
  92.         table.insert(key);
  93.     }
  94.  
  95.     table.print();
  96.  
  97.     cout << endl;
  98.  
  99.     cout << "Search 48: " << (table.search(48) ? "Found" : "Not Found") << endl;
  100.     cout << "Search 100: " << (table.search(100) ? "Found" : "Not Found") << endl;
  101.  
  102.     return 0;
  103. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[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
https://ideone.com/BrkeyX
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!