Advertisement
Guest User

HashTable

a guest
May 23rd, 2018
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #pragma once
  2. const int DEFAULT_SIZE = 16;
  3.  
  4. template<typename V>
  5. class HashTable
  6. {
  7. private:
  8.     template<typename V>
  9.     struct Node {
  10.         int key;
  11.         V value;
  12.  
  13.         Node(int k, V v) : key(k), value(v) {}
  14.         Node() : key(-1) {}
  15.     };
  16.  
  17.     bool isUnEmpty() {
  18.         return !(length == 0);
  19.     }
  20.  
  21.     Node<V>* *table;
  22.     size_t length;
  23.     int (*func)(const V&);
  24. public:
  25.     HashTable(int (*f)(const V&)) : table(new Node<V>*[DEFAULT_SIZE]), func(f), length(0) {
  26.         for (int i = 0; i < DEFAULT_SIZE; i++) {
  27.             table[i] = (Node<V>*)nullptr;
  28.         }
  29.     };
  30.     ~HashTable() {
  31.         for (int i = 0; i < DEFAULT_SIZE * length; i++) {
  32.             delete table[i];
  33.         }
  34.         delete[] table;
  35.     };
  36.  
  37.     void add(V elem) {
  38.         int hash = hashCode(elem);
  39.         if (table[hash] == (Node<V>*)nullptr) {
  40.             length++;
  41.         }
  42.         table[hash] = new Node<V>(hash, elem);
  43.     }
  44.  
  45.     int hashCode(V elem) {
  46.         if (length < DEFAULT_SIZE) {
  47.             return func(elem) % DEFAULT_SIZE;
  48.         }
  49.         return func(elem) % length;
  50.     }
  51.  
  52.     bool isEmpty() {
  53.         return !isUnEmpty();
  54.     }
  55.  
  56.     int findElem(V elem) {
  57.         int hash = hashCode(elem);
  58.         for (int i = 0; i < DEFAULT_SIZE * length; i++) {
  59.             if (table[i]->hash == hash) return hash;
  60.         }
  61.         return -1;
  62.     }
  63.  
  64.     void remove(V elem) {
  65.         int hash = findElem(elem);
  66.         table[hash] = nullptr;
  67.         length--;
  68.     }
  69.  
  70.     void makeEmpty() {
  71.         int i = 0;
  72.         while (!isEmpty()) {
  73.             remove(table[i++]);
  74.         }
  75.     }
  76.  
  77.     /*V get(int key) {
  78.  
  79.     }*/
  80.  
  81.  
  82. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement