C++におけるハッシュテーブルの実装と使用方法

1. ライブラリの使用: C++の標準ライブラリには、std::unordered_mapというハッシュテーブルの実装があります。これは、キーと値のペアを格納し、O(1)の平均時間での検索や挿入が可能です。以下は、std::unordered_mapの基本的な使用例です。

#include <unordered_map>
#include <iostream>
int main() {
  std::unordered_map<std::string, int> hashTable;
  // 要素の挿入
  hashTable["apple"] = 1;
  hashTable["banana"] = 2;
  hashTable["orange"] = 3;
  // 要素の検索
  if (hashTable.count("apple") > 0) {
    std::cout << "appleの値: " << hashTable["apple"] << std::endl;
  }
  return 0;
}

2. カスタム実装: ハッシュテーブルのカスタム実装では、ハッシュ関数と衝突解決方法を考慮する必要があります。以下は、単純なハッシュテーブルのカスタム実装の例です。

#include <iostream>
#include <vector>
class HashTable {
private:
  std::vector<std::pair<std::string, int>> table;
  int size;
public:
  HashTable(int size) {
    this->size = size;
    table.resize(size);
  }
  int hashFunction(const std::string& key) {
    // キーのハッシュ値を計算する方法を実装する
  }
  void insert(const std::string& key, int value) {
    int index = hashFunction(key) % size;
    // 衝突解決方法を実装する
    table[index] = std::make_pair(key, value);
  }
  int search(const std::string& key) {
    int index = hashFunction(key) % size;
    // 衝突解決方法を実装する
    if (table[index].first == key) {
      return table[index].second;
    }
    return -1;  // キーが見つからなかった場合
  }
};
int main() {
  HashTable hashTable(100);
  // 要素の挿入
  hashTable.insert("apple", 1);
  hashTable.insert("banana", 2);
  hashTable.insert("orange", 3);
  // 要素の検索
  int value = hashTable.search("apple");
  if (value != -1) {
    std::cout << "appleの値: " << value << std::endl;
  }
  return 0;
}

上記の例では、ハッシュテーブルの基本的な使い方とカスタム実装の方法を示しました。ハッシュテーブルはデータの追加や検索に優れた性能を発揮するため、大量のデータを効率的に管理する場合に便利です。さらに、ハッシュテーブルの衝突解決方法やパフォーマンスの最適化など、さまざまな応用方法があります。