fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const static int limit = 2147483647 ;
  4.  
  5.  
  6. // Problem 1 : Handling all letters and digits
  7. int hash_string(string name, int limit) {
  8.     long long sum = 0;
  9.     const int base = 62;
  10.  
  11.     for (auto ch : name) {
  12.         int val = 0;
  13.         if (islower(ch)) val = ch - 'a'; 
  14.         else if (isupper(ch)) val = 26 + (ch - 'A');
  15.         else if (isdigit(ch)) val = 52 + (ch - '0'); 
  16.         else continue;
  17.  
  18.         sum = (sum * base + val) % limit;
  19.     }
  20.     return sum;
  21. }
  22.  
  23. //Problem 4 : Folding for hashing
  24. int Folding_Hash(string input){
  25.  
  26.     long long hashValue = 0;
  27.  
  28.     for(int i = 0 ; i < (int)input.size(); i+=4){
  29.         string word = input.substr(i, 4);
  30.         int blockHash = hash_string(word,limit);
  31.         hashValue =(hashValue + blockHash) % limit;
  32.     }
  33.     return hashValue;
  34. }
  35.  
  36. // Problem 2 : Key based on multiple variables
  37. class someObject {
  38. public:
  39.     string str1, str2;
  40.     int number;
  41.  
  42.     int hash(string str1, string str2, int number) {
  43.         return (hash_string(str1, limit) +
  44.                 hash_string(str2, limit) +
  45.                 hash_string(to_string(number), limit)) % limit;
  46.     }
  47. };
  48.  
  49. // Problem 3 : Rehashing
  50. class Entry {
  51. public:
  52.     const static int Internal_limit = 65407;
  53.     string name; // key
  54.     string phoneNumber; // data
  55.  
  56.     Entry(string name, string phoneNumber) : name(name), phoneNumber(phoneNumber) {}
  57.  
  58.     int hash() const {
  59.         return hash_string(name, Internal_limit);
  60.     }
  61.  
  62.     void print() const {
  63.         cout << setw(4) << " (" << name << ", " << phoneNumber << ") " << '\n';
  64.     }
  65. };
  66.  
  67. class HashTable {
  68. private:
  69.     int table_size{0};
  70.     int added{0};
  71.     double limitf;
  72.     vector<vector<Entry>> table;
  73.  
  74. public:
  75.     HashTable(int table_size, double limitf) : table_size(table_size), limitf(limitf) {
  76.         table.resize(table_size);
  77.     }
  78.  
  79.     void put(const Entry &phone) {
  80.         if (Need_rehashing()) {
  81.             rehashing();
  82.         }
  83.         int idx = phone.hash() % table_size;
  84.  
  85.         for (int i = 0; i < (int)table[idx].size(); i++) {
  86.             if (table[idx][i].name == phone.name) {
  87.                 table[idx][i] = phone;
  88.                 return;
  89.             }
  90.         }
  91.         added++;
  92.         table[idx].push_back(phone);
  93.     }
  94.  
  95.     void put(const string &name, const string &phoneNumber) {
  96.         put(Entry(name, phoneNumber));
  97.     }
  98.  
  99.     bool remove(const Entry &phone) {
  100.         int idx = phone.hash() % table_size;
  101.         for (int i = 0; i < (int)table[idx].size(); i++) {
  102.             if (table[idx][i].name == phone.name) {
  103.                 swap(table[idx][i], table[idx].back());
  104.                 table[idx].pop_back();
  105.                 added--;
  106.                 return true;
  107.             }
  108.         }
  109.         return false;
  110.     }
  111.  
  112.     bool get(Entry &phone) const {
  113.         int idx = phone.hash() % table_size;
  114.  
  115.         for (int i = 0; i < (int)table[idx].size(); i++) {
  116.             if (table[idx][i].name == phone.name) {
  117.                 phone = table[idx][i];
  118.                 return true;
  119.             }
  120.         }
  121.         return false;
  122.     }
  123.  
  124.     void print_all() const {
  125.         for (int hash = 0; hash < table_size; hash++) {
  126.             if (table[hash].empty())
  127.                 continue;
  128.  
  129.             cout << "Hash " << hash << ": " << '\n';
  130.             for (const auto &entry : table[hash]) {
  131.                 entry.print();
  132.             }
  133.             cout << '\n';
  134.         }
  135.     }
  136.  
  137.     bool Need_rehashing() const {
  138.         return (double)added / table_size > limitf;
  139.     }
  140.  
  141.     void rehashing() {
  142.         int old_table_size = table_size;
  143.         table_size *= 2;
  144.         vector<vector<Entry>> New_table(table_size);
  145.         added = 0;
  146.  
  147.         for (int i = 0; i < old_table_size; i++) {
  148.             for (const auto &entry : table[i]) {
  149.                 int new_idx = entry.hash() % table_size;
  150.                 New_table[new_idx].push_back(entry);
  151.                 added++;
  152.             }
  153.         }
  154.  
  155.         table.swap(New_table);
  156.     }
  157. };
  158.  
  159. class Node {
  160. public:
  161.     Entry data;
  162.     Node* next;
  163.     Node* prev;
  164.  
  165.     Node(Entry data) : data(data), next(nullptr), prev(nullptr) {}
  166. };
  167.  
  168. class DLL {
  169. private:
  170.     Node* head = nullptr;
  171.     Node* tail = nullptr;
  172.     int size = 0;
  173.  
  174. public:
  175.     void insert(const Entry &entry) {
  176.         Node* newNode = new Node(entry);
  177.         if (!head) {
  178.             head = tail = newNode;
  179.         } 
  180.         else {
  181.             tail->next = newNode;
  182.             newNode->prev = tail;
  183.             tail = newNode;
  184.         }
  185.         size++;
  186.     }
  187.  
  188.     void print_forward() const {
  189.         Node* temp = head;
  190.         while (temp) {
  191.             temp->data.print();
  192.             temp = temp->next;
  193.         }
  194.         cout << endl;
  195.     }
  196.  
  197.     int get_size() const {
  198.         return size;
  199.     }
  200.  
  201.     ~DLL() {
  202.         Node* current = head;
  203.         while (current) {
  204.             Node* nextNode = current->next;
  205.             delete current;
  206.             current = nextNode;
  207.         }
  208.     }
  209. };
  210.  
  211. // Problem 5 : Chaining using Double Linked List
  212. class HashTable2 {
  213. private:
  214.     int table_size{0}, added{0};
  215.     vector<DLL*> table;
  216.  
  217. public:
  218.     HashTable2(int size) : table_size(size), added(0) {
  219.         table.resize(size);
  220.         for (int i = 0; i < size; i++) {
  221.             table[i] = new DLL();
  222.         }
  223.     }
  224.  
  225.     void put(const Entry &phone) {
  226.         int idx = phone.hash() % table_size;
  227.         table[idx]->insert(phone);
  228.         added++;
  229.     }
  230.  
  231.     void put(const string &name, const string &phoneNumber) {
  232.         put(Entry(name, phoneNumber));
  233.     }
  234.  
  235.     void print_all() const {
  236.         for (int hash = 0; hash < table_size; hash++) {
  237.             if (table[hash]->get_size() == 0)
  238.                 continue;
  239.  
  240.             cout << "Hash " << hash << ": " << endl;
  241.             table[hash]->print_forward();
  242.         }
  243.     }
  244.  
  245.     ~HashTable2() {
  246.         for (auto &dll : table) {
  247.             delete dll;
  248.         }
  249.     }
  250. };
  251.  
  252. int main() {
  253.     HashTable ht(4, 0.75);
  254.     ht.put("Alice", "1234567890");
  255.     ht.put("Bob", "2345678901");
  256.  
  257.     Entry search("Alice", "");
  258.     if (ht.get(search)) {
  259.         cout << "Found Alice's number: " << search.phoneNumber << '\n';
  260.     } 
  261.     else {
  262.         cout << "Alice not found.\n";
  263.     }
  264.     cout <<"--------------------------\n\n";
  265.     HashTable2 ht2(7);
  266.     ht2.put("Charlie", "3456789012");
  267.     ht2.put("Diana", "4567890123");
  268.     ht2.put("Alice", "1234567890");
  269.     ht2.put("Bob", "2345678901");
  270.     ht2.put("manarmanora","749347");
  271.     cout << "HashTable2 contents:\n";
  272.     ht2.print_all();
  273. }
  274.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found Alice's number: 1234567890
--------------------------

HashTable2 contents:
Hash 1: 
   (Diana, 4567890123) 
   (Bob, 2345678901) 

Hash 3: 
   (Alice, 1234567890) 

Hash 4: 
   (manarmanora, 749347) 

Hash 6: 
   (Charlie, 3456789012)
https://ideone.com/cvBU9e
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!