Michaelzhao314

hashmaps

Oct 17th, 2020 (edited)
880
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Basically I'm creating an array on the stack for the table
  2. // If we don't use chaining, it'll just be an array of integers/strings
  3. // else, we have to use an array of integer/string vectors.
  4.  
  5. // If strings are used for hashing, then you will need to replace
  6. // all of the int hashTable[] with string hashTable[] and
  7. // use vs hashTable[] instead of vi hashTable[]
  8.  
  9. // There's actually a good amount of the overhead code that
  10. // needs to be changed if your exam uses strings instead of
  11. // integers to hash, but all of the individual functions are coorect
  12.  
  13. // Also I suggest writing everything on your own just in case and
  14. // for more practice. I just used random variables for the things that are defined;
  15. // those will most likely be given on the test
  16.  
  17. // One last thing, I used log base 2/10 of the size to get the r value
  18. // for the mid square hashing functions. They might give us that value on the test,
  19. // but just in case I have it calculated.
  20.  
  21. #include <iostream>
  22. #include <vector>
  23. #include <cmath>
  24. #include <string>
  25. using namespace std;
  26.  
  27. #define vi vector<int>
  28. #define vs vector<string>
  29. #define SIZE 100 // Given size
  30. #define INITIAL_MULT_VALUE 20 // Given if multiplicative string hashing
  31. #define MULTIPLIER 5 // Given if multiplicative string hashing
  32. #define ADLER_MOD 65521 // Given if adler32 hashing
  33. #define QUAD_PROBE_C1 4 // Given if quadratic probing
  34. #define QUAD_PROBE_C2 5 // Given if quadratic probing
  35.  
  36. // Hashing functions
  37. int hashItem(int key);
  38. int hashItem(int string);
  39. int moduloHash(int key);
  40. int midSquare10Hash(int key);
  41. int midSquare2Hash(int key);
  42. int multiStringHash(string key);
  43. int adler32Hash(string key);
  44.  
  45. // Insertion functions
  46. bool insert(int(&hashTable)[SIZE], int item);
  47. bool insert(vi(&hashTable)[SIZE], int item);
  48. bool chainingInsert(vi(&hashTable)[SIZE], int item);
  49. bool linearProbingInsert(int(&hashTable)[SIZE], int item);
  50. bool quadraticProbingInsert(int(&hashTable)[SIZE], int item);
  51. bool doubleHashingInsert(int(&hashTable)[SIZE], int item);
  52.  
  53. // Searching functions
  54. // Deletion function if param "toDelete" is set to true
  55. // Change param "query" to a string if using multiplicative string or adler32 hashing methods
  56. bool search(int(&hashTable)[SIZE], int query, bool toDelete);
  57. bool search(vi(&hashTable)[SIZE], int query, bool toDelete);
  58. bool chainingSearch(vi(&hashTable)[SIZE], int query, bool toDelete);
  59. bool linearProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete);
  60. bool quadraticProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete);
  61. bool doubleHashingSearch(int(&hashTable)[SIZE], int query, bool toDelete);
  62.  
  63. // Printing functions
  64. void output(int(&hashTable)[SIZE]);
  65. void output(vi(&hashTable)[SIZE]);
  66.  
  67. int main() {
  68.     int hashTable[SIZE]; // If not using chaining
  69.     for (int i = 0; i < SIZE; i++) hashTable[i] = -1; // If not using chaining
  70.  
  71.     // vi hashTable[SIZE]; // If using chaining
  72.  
  73.     // Main loop
  74.     int choice = 0;
  75.     while (choice != 5) {
  76.         cout << "Hash Tables - Pick an option" << endl;
  77.         cout << "1. Insert element" << endl;
  78.         cout << "2. Search for an element" << endl;
  79.         cout << "3. Delete an element" << endl;
  80.         cout << "4. Output all elements" << endl;
  81.         cout << "5. Exit" << endl;
  82.  
  83.         choice = 0;
  84.         while (choice < 1 || choice > 5) {
  85.             cout << "Enter an option (1-5): ";
  86.             cin >> choice;
  87.         }
  88.         cout << endl;
  89.  
  90.         int q; // Change to string if using multiplicative string or adler32 hashing
  91.  
  92.         if (choice == 1) {
  93.             int item;
  94.             cout << "Enter the item you want to insert: ";
  95.             cin >> item;
  96.             cout << (insert(hashTable, item) ? "Sucessfully added " + to_string(item) : "Could not insert item into hash table") << endl << endl;
  97.         }
  98.         else if (choice == 2) {
  99.             cout << "Enter key to search for: ";
  100.             cin >> q;
  101.             cout << (search(hashTable, q, false) ? "Item found" : "Item not found") << endl << endl;
  102.         }
  103.         else if (choice == 3) {
  104.             cout << "Enter key to delete: ";
  105.             cin >> q;
  106.             cout << (search(hashTable, q, true) ? "Item deleted" : "Item not found") << endl << endl;
  107.         }
  108.         else if (choice == 4) output(hashTable);
  109.     }
  110.     return 0;
  111. }
  112.  
  113. // -------------------------------------- General functions --------------------------------------
  114.  
  115. int hashItem(int key) {
  116.     // Call a hashing function
  117.     return moduloHash(key);
  118.     // return midSquare10Hash(key);
  119.     // return midSquare2Hash(key);
  120. }
  121.  
  122. int hashItem(string key) {
  123.     // These hashing functions have string keys
  124.     return multiStringHash(key);
  125.     // return adler32Hash(key);
  126. }
  127.  
  128. bool insert(int(&hashTable)[SIZE], int item) {
  129.     // return linearProbingInsert(hashTable, item);
  130.     // return quadraticProbingInsert(hashTable, item);
  131.     return doubleHashingInsert(hashTable, item);
  132. }
  133.  
  134. bool insert(vi(&hashTable)[SIZE], int item) {
  135.     // Chaining requires a vector<vector<int>>
  136.     return chainingInsert(hashTable, item);
  137. }
  138.  
  139. bool search(int(&hashTable)[SIZE], int query, bool toDelete) {
  140.     // return linearProbingSearch(hashTable, query, toDelete);
  141.     // return quadraticProbingSearch(hashTable, query, toDelete);
  142.     return doubleHashingSearch(hashTable, query, toDelete);
  143. }
  144.  
  145. bool search(vi(&hashTable)[SIZE], int query, bool toDelete) {
  146.     // Chaining requires a vector<vector<int>>
  147.     return chainingSearch(hashTable, query, toDelete);
  148. }
  149.  
  150. // -------------------------------------- Hashing functions --------------------------------------
  151.  
  152. int moduloHash(int key) {
  153.     return key % SIZE;
  154. }
  155.  
  156. int midSquare10Hash(int key) {
  157.     int r = (int)ceil(log10(SIZE));
  158.     string s = to_string(key * key);
  159.     int right = (s.length() - r) / 2;
  160.     s.erase(s.length() - right, right);
  161.     int left = s.size() - r;
  162.     s.erase(0, left);
  163.     return stoi(s) % SIZE;
  164. }
  165.  
  166. int midSquare2Hash(int key) {
  167.     int r = (int)ceil(log2(SIZE));
  168.     key *= key;
  169.     int lower = (32 - r) / 2;
  170.     int bits = key >> lower;
  171.     bits = bits & (0xFFFFFFFF >> (32 - r));
  172.     return bits % SIZE;
  173. }
  174.  
  175. int multiStringHash(string key) {
  176.     long long out = INITIAL_MULT_VALUE;
  177.     for (auto& s : key) {
  178.         out = (out * MULTIPLIER) + s;
  179.     }
  180.     return out % SIZE;
  181. }
  182.  
  183. int adler32Hash(string key) {
  184.     int a = 1;
  185.     int b = 0;
  186.     for (auto& s : key) {
  187.         a = (a + s) % ADLER_MOD;
  188.         b = (b + a) % ADLER_MOD;
  189.     }
  190.     return ((b << 16) | a) % SIZE;
  191. }
  192.  
  193. // -------------------------------------- Insertion functions --------------------------------------
  194.  
  195. bool chainingInsert(vi(&hashTable)[SIZE], int item) {
  196.     if (!chainingSearch(hashTable, item, false)) return false;
  197.     hashTable[hashItem(item)].push_back(item);
  198.     return true;
  199. }
  200.  
  201. bool linearProbingInsert(int(&hashTable)[SIZE], int item) {
  202.     if (linearProbingSearch(hashTable, item, false)) return false;
  203.     int bucket = hashItem(item);
  204.     int count = 0;
  205.     while (count < SIZE) {
  206.         if (hashTable[bucket] == -1) {
  207.             hashTable[bucket] = item;
  208.             return true;
  209.         }
  210.         bucket = (bucket + 1) % SIZE;
  211.         count++;
  212.     }
  213.     return false;
  214. }
  215.  
  216. bool quadraticProbingInsert(int(&hashTable)[SIZE], int item) {
  217.     if (quadraticProbingSearch(hashTable, item, false)) return false;
  218.     int count = 0;
  219.     int i = 0;
  220.     int initialHash = hashItem(item);
  221.     int bucket = initialHash;
  222.     while (count < SIZE) {
  223.         if (hashTable[bucket] == -1) {
  224.             hashTable[bucket] = item;
  225.             return true;
  226.         }
  227.         i++;
  228.         bucket = (initialHash + QUAD_PROBE_C1 * i + QUAD_PROBE_C2 * i * i) % SIZE;
  229.         count++;
  230.     }
  231.     return false;
  232. }
  233.  
  234. bool doubleHashingInsert(int(&hashTable)[SIZE], int item) {
  235.     if (doubleHashingSearch(hashTable, item, false)) return false;
  236.     int hash1 = moduloHash(item); // These can be any 2 hashing functions
  237.     int hash2 = midSquare2Hash(item);
  238.     int count = 0;
  239.     int i = 0;
  240.     int bucket;
  241.     while (count < SIZE) {
  242.         bucket = (hash1 + hash2 * i) % SIZE;
  243.         if (hashTable[bucket] == -1) {
  244.             hashTable[bucket] = item;
  245.             return true;
  246.         }
  247.         i++;
  248.         count++;
  249.     }
  250.     return false;
  251. }
  252.  
  253. // -------------------------------------- Search and delete functions --------------------------------------
  254.  
  255. bool chainingSearch(vi(&hashTable)[SIZE], int query, bool toDelete) {
  256.     auto& list = hashTable[hashItem(query)];
  257.     for (int i = 0; i < list.size(); i++) {
  258.         if (list[i] == query) {
  259.             if (toDelete) list.erase(list.begin() + i);
  260.             return true;
  261.         }
  262.     }
  263.     return false;
  264. }
  265.  
  266. bool linearProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete) {
  267.     int bucket = hashItem(query);
  268.     int count = 0;
  269.     while (count < SIZE) {
  270.         if (hashTable[bucket] == query) {
  271.             if (toDelete) hashTable[bucket] = -1;
  272.             return true;
  273.         }
  274.         bucket = (bucket + 1) % SIZE;
  275.         count++;
  276.     }
  277.     return false;
  278. }
  279.  
  280. bool quadraticProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete) {
  281.     int count = 0;
  282.     int i = 0;
  283.     int initialHash = hashItem(query);
  284.     int bucket = initialHash;
  285.     while (count < SIZE) {
  286.         if (hashTable[bucket] == query) {
  287.             if (toDelete) hashTable[bucket] = -1;
  288.             return true;
  289.         }
  290.         i++;
  291.         bucket = (initialHash + QUAD_PROBE_C1 * i + QUAD_PROBE_C2 * i * i) % SIZE;
  292.         count++;
  293.     }
  294.     return false;
  295. }
  296.  
  297. bool doubleHashingSearch(int(&hashTable)[SIZE], int query, bool toDelete) {
  298.     int hash1 = moduloHash(query); // These can be any 2 hashing functions
  299.     int hash2 = midSquare2Hash(query);
  300.     int count = 0;
  301.     int i = 0;
  302.     int bucket;
  303.     while (count < SIZE) {
  304.         bucket = (hash1 + hash2 * i) % SIZE;
  305.         if (hashTable[bucket] == query) {
  306.             if (toDelete) hashTable[bucket] = -1;
  307.             return true;
  308.         }
  309.         i++;
  310.         count++;
  311.     }
  312.     return false;
  313. }
  314.  
  315. // -------------------------------------- Output functions --------------------------------------
  316.  
  317. void output(int(&hashTable)[SIZE]) {
  318.     for (int i = 0; i < SIZE; i++) {
  319.         if (hashTable[i] != -1) {
  320.             cout << i << ": " << hashTable[i] << endl;
  321.         }
  322.     }
  323.     cout << endl;
  324. }
  325.  
  326. void output(vi(&hashTable)[SIZE]) {
  327.     for (int i = 0; i < SIZE; i++) {
  328.         for (auto& item : hashTable[i]) {
  329.             cout << i << ": " << item << endl;
  330.         }
  331.     }
  332.     cout << endl;
  333. }
  334.  
RAW Paste Data