C++ hash table

Table of contents

What is a hash table?

A Hash Table in C/C++ (Associative array) is a data structure that maps keys to values. This uses a hash function to compute indexes for a key.

Based on the Hash Table index, we can store the value at the appropriate location.

The C++ STL (Standard Template Library) has the unordered_map() data structure which implements all these hash table functions.

Components

Any Hash Table implementation has the following three components:

• A good Hash function to map keys to values
• A Hash Table Data Structure that supports insert, search and delete operations.
• A Data Structure to account for collision of keys

map vs unordered_map

Advantages of BST over Hash Table

• We can get all keys in sorted order by just doing Inorder Traversal of BST.
  • This is not a natural operation in Hash Tables and requires extra efforts.
• Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs
  • Like sorting, these operations are not a natural operation with Hash Tables.
• BSTs are easy to implement compared to hashing
• With BSTs, all operations are garanteed to work in O(log(N))
  • But with Hashing, O(1) is average time and some particular operations may be costly i.e, O(n²), especially when table resizing happens.
• In BST we can do range searches efficiently but in Hash Table we cannot do range search efficiently.
• BST are memory efficient but Hash table is not.

Size

The size of our Hash Table and so the number with which we do our modulo calculation, should be a prime number that is only divisible with itself or 1. That way we prevent stacking of many values in one place like 2 when the numbers are even!

Very simple hash table implementation

class VerySimpleHashTable {
  // Table: array of list of integer with 7 buckets
  array<list<int>, 7> mTable{};  // must be a prime number
  size_t hashFunction(int item) { return item % mTable.size(); }

 public:
  void insertItem(int item) {
    auto index = hashFunction(item);
    auto it = find(mTable[index].begin(), mTable[index].end(), item);
    if (it == mTable[index].end()) {
      mTable[index].push_back(item);
    }
  }

  void deleteItem(int item) {
    auto index = hashFunction(item);
    auto it = find(mTable[index].begin(), mTable[index].end(), item);
    if (it != mTable[index].end()) {
      mTable[index].erase(it);
    }
  }

  void print() {
    size_t index = 0;
    for (const auto& lst : mTable) {
      cout << "Bucket " << index << ":";
      for (const auto& i : lst) {
        cout << ' ' << i;
      }
      cout << '\n';
      ++index;
    }
    cout << "-----------------\n";
  }
};

Example of use

  VerySimpleHashTable simpleTable;
  simpleTable.print();
  int element;
  srand(0);
  for (int i = 0; i < 50; ++i) {
    element = rand() % 100;
    simpleTable.insertItem(element);
  }
  simpleTable.print();

  simpleTable.deleteItem(101);

  srand(0);
  for (int i = 0; i < 45; ++i) {
    element = rand() % 100;
    simpleTable.deleteItem(element);
  }
  simpleTable.print();

C++ unordered_map example

  // Helper function
  auto print_unorderd_map = [](const auto& table) {
    for (const auto& [key, value] : table) {
      cout << "Key:[" << key << "] Value:[" << value << "]\n";
    };
    cout << "-----------------\n";
  };

  unordered_map<string, string> colorTable = {
      {"RED", "#FF0000"}, {"GREEN", "#00FF00"}, {"BLUE", "#0000FF"}};

  print_unorderd_map(colorTable);

  // Add two new entries to the unordered_map
  colorTable["BLACK"] = "#000000";
  colorTable["WHITE"] = "#FFFFFF";

  // Replace item
  colorTable["RED"] = "#FF6666";

  print_unorderd_map(colorTable);

  colorTable.erase("RED");

  print_unorderd_map(colorTable);

Possible output

Bucket 0:
Bucket 1:
Bucket 2:
Bucket 3:
Bucket 4:
Bucket 5:
Bucket 6:
-----------------
Bucket 0: 77 35 49 21 63 56 42 84 98 70
Bucket 1: 15 92 36 29 22
Bucket 2: 86 93 72 30 23 2 58 37
Bucket 3: 59 73 24
Bucket 4: 11 67
Bucket 5: 26 40 68 82 19
Bucket 6: 83 62 27 90 69
-----------------
Bucket 0: 98 70
Bucket 1:
Bucket 2: 37
Bucket 3: 24
Bucket 4:
Bucket 5:
Bucket 6:
-----------------
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]
-----------------
Key:[WHITE] Value:[#FFFFFF]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF6666]
-----------------
Key:[WHITE] Value:[#FFFFFF]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
-----------------

Reference

• Hash Table in C/C++ - A Complete Implementation
• Advantages of BST over Hash Table