How to implement a hash table in C++?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <unordered_map>
#include <string>

int main() {
  // Declare a hash table with integer keys and string values
  std::unordered_map<int, std::string> hash_table;

  // Insert some key-value pairs into the hash table
  hash_table[1] = "one";
  hash_table[2] = "two";
  hash_table[3] = "three";

  // Check if a key is in the hash table
  if (hash_table.count(1) > 0) {
    std::cout << "Key 1 is in the hash table" << std::endl;
  }

  // Get the value associated with a key
  std::string value = hash_table[1];
  std::cout << "Value for key 1: " << value << std::endl;

  return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

#include <iostream>

// Node structure for linked lists
struct Node {
  int key;
  std::string value;
  Node* next;

  Node(int k, std::string v) : key(k), value(v), next(nullptr) {}
};

// Hash table class
class HashTable {
private:
  int size; // size of the hash table
  Node** table; // dynamic array of linked lists

  // Hash function to convert key to an index
  int hash(int key) {
    return key % size;
  }

public:
  // Constructor
  HashTable(int tableSize) : size(tableSize) {
    table = new Node*[size]{}; // initialize the table with nullptrs
  }

  // Destructor
  ~HashTable() {
    for (int i = 0; i < size; i++) {
      Node* current = table[i];
      while (current) {
        Node* temp = current;
        current = current->next;
        delete temp;
      }
    }
    delete[] table;
  }

  // Insert a key-value pair into the hash table
  void insert(int key, const std::string& value) {
    int index = hash(key);
    Node* newNode = new Node(key, value);
    if (!table[index]) {
      table[index] = newNode;
    } else {
      Node* current = table[index];
      while (current->next) {
        current = current->next;
      }
      current->next = newNode;
    }
  }

  // Get the value associated with a key
  std::string get(int key) {
    int index = hash(key);
    Node* current = table[index];
    while (current) {
      if (current->key == key) {
        return current->value;
      }
      current = current->next;
    }
    return ""; // key not found
  }

  // Check if a key is in the hash table
  bool contains(int key) {
    int index = hash(key);
    Node* current = table[index];
    while (current) {
      if (current->key == key) {
        return true;
      }
      current = current->next;
    }
    return false;
  }
};

int main() {
  // Create a hash table with size 10
  HashTable hashTable(10);

  // Insert some key-value pairs into the hash table
  hashTable.insert(1, "one");
  hashTable.insert(2, "two");
  hashTable.insert(3, "three");

  // Check if a key is in the hash table
  if (hashTable.contains(1)) {
    std::cout << "Key 1 is in the hash table" << std::endl;
  }

  // Get the value associated with a key
  std::string value = hashTable.get(1);
  std::cout << "Value for key 1: " << value << std::endl;

  return 0;
}