C++ で HashMap を使用する

1. C++ の std::map で HashMap を使用する
2. C++ で std::unordered_map で HashMap を使用する
3. 主な違いと C++ で各マップを使用する場合

HashMap は、関連するキーを使用して値を取得できるキーと値のペアを含む重要なデータ構造です。すべてのキーは、HashMap の 1つの特定の値にマップされます。

反復中にキーを使用すると、対応する値にはるかに高速にアクセスできます。したがって、HashMap は、任意のタイプのキーと値の両方を使用して値を取得するときに、効率的で不可欠なデータ構造と見なされます。

C++ 11 より前は、標準定義のハッシュテーブルは C++ の標準ライブラリに存在しませんでしたが、多少異なる実装者が、ハッシュテーブルの非標準バリアント（HashMap と呼ばれることが多い）を持っていました。C++ 11 とともに、ハッシュテーブルの標準実装が標準ライブラリに追加されました。

それでも、さまざまなライブラリからの HashMap としてハッシュテーブルのさまざまなバリエーションがあるため、混乱を避けるために、新しい実装を呼び出すために別の名前を使用することにしました。

したがって、C++ では、std::unordered_map は HashMap の別名ですが、別のマップはキーと値のペアの概念である std::map を使用します。

std::unordered_map と std::map には重要な違いがあります。名前が示すように、std::unordered_map 内の要素は順序付けられていませんが、std::map 内の要素は順序付けられています。

C++ の std::map で HashMap を使用する

std::map は、要素がマップされたキーと値のペアで格納される連想コンテナのカテゴリに属します。std::map と std::unordered_map では、キーは常に一意である必要がありますが、マップされた値が類似しているいくつかの一意のキーが存在する可能性があります。

std::map は、Self-Balancing Binary Search Tree（AVL ツリー/赤黒木）を使用して実装されます。BST（Self-Balancing Binary Search Tree）の主な機能は、要素の挿入と削除が発生したときに、高さが常に自動的に最小に保たれることです。

std::map では、平均時間計算量は、格納されている要素の数に対数的に依存します。したがって、操作が発生するまでに平均して O(log n) 時間がかかります。O(log n) では、O は Big O 表記を表し、n は格納されている要素の数を表します。

したがって、BST は、順序付きリストを作成および保守するときに役立ちます。

例：

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

出力：

Number of Players 2
1: Chen Long
2: Lin Dan

C++ で std::unordered_map で HashMap を使用する

std::unordered_map は、C++ のハッシュテーブルを使用して実装されます。ハッシュテーブルも連想コンテナに属しています。マップされた値は、バケットまたはスロットの配列のハッシュテーブルに格納され、そこから必要な値を取得できます。

このインデックス付けは、ハッシュ関数、ハッシュコードを使用して行われます。std::unordered_map の検索、挿入、削除の平均時間計算量は O(1) です。ここで、O は Big O 表記です。これが、std::unordered_map は非常に効率的です。

例：

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> info;

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

出力：

Number of Players 15
Year 2022
Age 18

主な違いと C++ で各マップを使用する場合

std::unordered_map と std::map を比較すると、2つの間の効率のギャップは非常に大きくなります。

std::unordered_map は、明らかに std::map よりもかなりのパフォーマンスエッジを持っています。これは主に、std::unordered_map がスロットに配置されるときに値を直接アドレス指定できるため、保持する必要のある順序がないためです。

一方、std::map には、保持する必要のある順序があります。したがって、より多くの時間を消費します。この効率は小さなデータセットでは見られないかもしれませんが、大きなデータセットではこの違いは非常に大きいです。

std::unordered_map は、データセットから単一の要素にアクセスする場合、または順序が不要な場合に要素の数を保持する場合に使用できます。

std::map には、std::unordered_map に比べていくつかの利点もあります。一般に、BST はハッシュテーブルよりも迅速に実装でき、これは好ましい方法で実行できますが、ハッシュの場合、ライブラリに大きく依存する必要があります。

したがって、std::map は、std::unordered_map と比較して簡単に実装できます。また、並べ替えに関しては、std::unordered_map よりも std::map でキーを並べ替える方がはるかに簡単です。これは、順序のトラバースがハッシュテーブルの自然な操作ではなく、BST の操作であるためです。

std::map は、データを並べ替えられた順序で印刷する場合など、検索クエリや順序統計などのためにデータを並べ替える必要がある場合に使用できます。

std::map と std::unordered_map には、その瞬間の必要性に応じて操作できる特定の類似点と相違点があります。