C++ STL を使用するときにハッシュの衝突に対処するにはどうすればよいですか?

C++ STL ハッシュの競合は次の方法で処理されます: チェーン アドレス方法: リンク リストを使用して競合する要素を保存します。これは適切な適用性があります。オープン アドレス指定方法: 要素を保存するためにバケット内の利用可能な場所を検索します。 サブメソッドは次のとおりです。 線形検出: 順番に次の利用可能な場所を検索します。二次検出: 二次形式で位置をスキップして検索します。

C++ STL でハッシュ衝突を処理する方法

C++ 標準テンプレート ライブラリ (STL) のハッシュ テーブルを使用する場合、複数のキーが同じバケットにハッシュされる可能性があるため、衝突は避けられません。競合を処理するために、STL は次のメソッドを提供します。

チェーン アドレス メソッド

チェーン アドレス メソッドは、リンクされたリストを使用して、ハッシュされた要素を同じバケットに格納します。競合が発生すると、新しいリンク リスト ノードが作成され、要素がリンク リストに追加されます。これは、高密度のハッシュ テーブルを適切に処理できるため、最も一般的に使用される衝突処理方法です。

#include <unordered_map>
#include <list>

int main() {
  std::unordered_map<int, std::list<int>> hash_table;
  hash_table[10].push_back(100);
  hash_table[10].push_back(200);

  // 迭代哈希到 10 的键
  for (auto& item : hash_table[10]) {
    std::cout << item << " ";  // 输出 100 200
  }
  return 0;
}

オープンアドレッシングメソッド

オープンアドレッシングメソッドは、競合が発生した場合に新しいノードを作成しません。代わりに、要素を保存するためにバケット内で次に利用可能な場所を探します。いくつかのオープン アドレス指定方法があり、最も一般的なのは線形プローブと二次プローブです。

線形プローブ:

#include <unordered_map>

int main() {
  std::unordered_map<int, int> hash_table;
  hash_table[10] = 100;  // 插入 (10, 100)
  hash_table[10] = 200;  // 更新 (10, 200)

  // 访问更新后的值
  std::cout << hash_table[10] << std::endl;  // 输出 200
  return 0;
}

二次プローブ:

#include <unordered_map>

int main() {
  std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, QuadraticProbing<int, int>> hash_table;
  hash_table[10] = 100;  // 插入 (10, 100)
  hash_table[10] = 200;  // 更新 (10, 200)

  // 访问更新后的值
  std::cout << hash_table[10] << std::endl;  // 输出 200
  return 0;
}

どの衝突処理方法が選択されるかは、ハッシュ テーブルの予想される負荷係数によって異なります。一般に、チェーン アドレス指定方法は密なハッシュ テーブルにより適しており、オープン アドレス指定方法は疎なハッシュ テーブルにより適しています。

以上がC++ STL を使用するときにハッシュの衝突に対処するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。