Al3XS0n

Hash-table

Sep 21st, 2020
747
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Node {
  2.     string key;
  3.     bool deleted;
  4.     Node(string _key);
  5. };
  6.  
  7. Node::Node(string _key) : key(_key), deleted(false){}
  8.  
  9.  
  10. class HashTable {
  11. private:
  12.     int size = 0;
  13.     int countKeys = 0;
  14.     vector<Node> table;
  15.  
  16.     int GetHash(string key, int mod) const;
  17.     void Rehash();
  18.  
  19. public:
  20.     HashTable();
  21.     ~HashTable();
  22.  
  23.     bool Insert(string key);
  24.     bool Erase(string key);
  25.     bool Find(string key);
  26. };
  27.  
  28. HashTable::HashTable() : size(8), countKeys(0) {
  29.     table.resize(8, Node("empty"));
  30. }
  31.  
  32. HashTable::~HashTable() {
  33.     size = countKeys = 0;
  34.     table.clear();
  35. }
  36.  
  37. int HashTable::GetHash(string key, int mod) const {
  38.     int hash = 0;
  39.     int base = 11;
  40.     for (int i = 0; i < key.size(); ++i) {
  41.         hash = (hash * base + key[i]) % mod;
  42.     }
  43.     return hash;
  44. }
  45.  
  46. void HashTable::Rehash() {
  47.     int newSize = size * 2;
  48.     vector<Node> newTable(newSize, Node("empty"));
  49.     for (int i = 0; i < size; i++) {
  50.         if (table[i].key != "empty" && !table[i].deleted) {
  51.             int hash = GetHash(table[i].key, newSize);
  52.             int k = 0;
  53.             while (newTable[hash].key != "empty" && k < newSize) {
  54.                 hash = (hash + (k * k) % newSize) % newSize;
  55.                 k++;
  56.             }
  57.             newTable[hash] = table[i];
  58.         }
  59.     }
  60.     table = newTable;
  61.     size = newSize;
  62. }
  63.  
  64. bool HashTable::Insert(string key) {
  65.     if (((double)countKeys / (double)size) >= (double)0.75) {
  66.         Rehash();
  67.     }
  68.  
  69.     int hash = GetHash(key, size);
  70.     int i = 0;
  71.     int firstDeleted = -1;
  72.     while (table[hash].key != "empty" && i < size) {
  73.         if (table[hash].key == key && !table[hash].deleted) {
  74.             return false;
  75.         }
  76.         if (table[hash].deleted && firstDeleted < 0) {
  77.             firstDeleted = hash;
  78.         }
  79.         i++;
  80.         hash = (hash + (i * i) % size) % size;
  81.     }
  82.  
  83.     if (firstDeleted < 0) {
  84.         table[hash] = Node(key);
  85.     } else {
  86.         table[firstDeleted].key = key;
  87.         table[firstDeleted].deleted = false;
  88.     }
  89.     countKeys++;
  90.     return true;
  91. }
  92.  
  93. bool HashTable::Erase(string key) {
  94.     int hash = GetHash(key, size);
  95.     int i = 0;
  96.     while (table[hash].key != "empty" && i < size) {
  97.         if (table[hash].key == key && !table[hash].deleted) {
  98.             table[hash].deleted = true;
  99.             countKeys--;
  100.             return true;
  101.         }
  102.         i++;
  103.         hash = (hash + (i * i) % size) % size;
  104.     }
  105.     return false;
  106. }
  107.  
  108. bool HashTable::Find(string key) {
  109.     int hash = GetHash(key, size);
  110.     int i = 0;
  111.     while (table[hash].key != "empty" && i < size) {
  112.         if (table[hash].key == key && !table[hash].deleted) {
  113.             return true;
  114.         }
  115.         i++;
  116.         hash = (hash + (i * i) % size) % size;
  117.     }
  118.     return false;
  119. }
  120.  
RAW Paste Data