DTL - Hash table

Introduction

The Hash table data structure stores elements in key-value pairs where the key must be unique and the value data is associated to that specific key. Therefore, if you want to access an element, you must specify which key was used to store the element.

Advantages

Constant access time in average for access, search, insertion and deletion.
In many situations, are more efficient than Binary Search Trees.

Disadvantages

Hash collisions are practically unavoidable.
Requires more space.

Using hash table with DTL

Initializing a hash table

Using a referenced size:

#include "hash_table.hpp"
#include <iostream>

int main() {
  // Static
  dby::HashTable<std::string, int> myStaHT(10);
  // Real size = next prime number : 10 -> 11

  // Pointer
  dby::HashTable<std::string, int>* myPtrHT = new dby::HashTable<std::string, int>(15);
  // Real size = next prime number : 15 -> 17
  
  delete myPtrHT;
  return 0;
}

Using a strict size:

#include "hash_table.hpp"
#include <iostream>

int main() {
  // Static
  dby::HashTable<std::string, int> myStaHT(10, true);
  // Real size = 10

  // Pointer
  dby::HashTable<std::string, int>* myPtrHT = new dby::HashTable<std::string, int>(15, true);
  // Real size = 15
  
  delete myPtrHT;
  return 0;
}

Inserting data

#include "hash_table.hpp"
#include <iostream>

int main() {
  // Static
  dby::HashTable<std::string, int> myStaHT(7);
  myStaHT.insert("key", 3);

  // Pointer
  dby::HashTable<int, int>* myPtrHT = new dby::HashTable<int, int>(4);
  myPtrHT->insert(1, 2022);
  
  delete myPtrHT;
  return 0;
}

Searching data

#include "hash_table.hpp"
#include <iostream>

int main() {
  // Static
  dby::HashTable<std::string, int> myStaHT(7);
  myStaHT.insert("one", 1);
  myStaHT.insert("three", 3);

  std::cout << "ONE: " << (myStaHT.search("one") ? "YES" : "NO") << '\n'; // YES
  std::cout << "TWO: " << (myStaHT.search("two") ? "YES" : "NO") << '\n'; // NO

  // Pointer
  dby::HashTable<int, int>* myPtrHT = new dby::HashTable<int, int>(4);
  myPtrHT->insert(1, 2022);
  myPtrHT->insert(2, 17);
  myPtrHT->insert(3, 12);

  std::cout << "1: " << (myPtrHT->search(1) ? "YES" : "NO") << '\n'; // YES
  std::cout << "2: " << (myPtrHT->search(2) ? "YES" : "NO") << '\n'; // YES
  std::cout << "3: " << (myPtrHT->search(3) ? "YES" : "NO") << '\n'; // YES
  
  delete myPtrHT;
  return 0;
}

Getting data

#include "hash_table.hpp"
#include <iostream>

class Obj {
  int val;
public:
  Obj(int val) {
    this->val = val;
  }

  ~Obj() { }

  void setVal(int val) {
    this->val = val;
  }

  int getVal() {
    return this->val;
  }
};

int main() {
  // Static
  dby::HashTable<std::string, int> myStaHT(7);
  myStaHT.insert("one", 1);
  myStaHT.insert("three", 3);

  int* elementToFind = myStaHT.get("two");
  if (elementToFind == nullptr) {
    std::cout << "Key not found.\n";
  }
  else {
    std::cout << "VALUE: " << *elementToFind << '\n';
  }

  // Pointer
  dby::HashTable<int, Obj*>* myPtrHT = new dby::HashTable<int, Obj*>(4);
  myPtrHT->insert(1, new Obj(18));
  myPtrHT->insert(2, new Obj(96));
  
  Obj** objectToFind = myPtrHT->get(1);
  if (objectToFind == nullptr) {
    std::cout << "Key not found.\n";
  }
  else {
    std::cout << "VALUE: " << (*objectToFind)->getVal();
  }

  delete myPtrHT;
  return 0;
}

Hash table methods

get(K key): Returns a pointer to the value if the 'key' exists in the Hash table.
insert(K key, V value): Adds an element with the specified key and value into the Hash table.
remove(K key): Removes an element if the 'key' exists in the HashTable.
search(K key): Check whether a particular key is present in the HashTable or not.
for_each(void(*doThis)(std::pair <K, V> value)): Applies the given function to every element of the Hash table. 'doThis' is a void function that receives a pair <Key, Value> as parameter.
for_each(void(*doThisCell)(int), void(*doThisList)(std::pair<K, V>), bool every_cell): Applies the given function to every cell and element of the Hash table. 'doThisCell' is a function that receives the position of the cell (int) as parameter. 'doThis' is a void function that receives a pair <Key, Value> as parameter.
count_collisions(): Returns the number of collisions in the Hash table.

Hash Table