ハッシュ テーブルと C++ のハッシュ テーブル

ハッシュ テーブルと C のハッシュ テーブル

ハッシュ テーブルとハッシュ テーブルは、コンピューター サイエンスにおいて非常に一般的なデータ構造です。なぜ？ハッシュ テーブルとハッシュ テーブルは一定時間内に特定の要素をすばやく見つけることができるためです。多くのアプリケーションでは、このパフォーマンスの違いは重大です。

それでは、ハッシュ テーブルとハッシュ テーブルの違いは何でしょうか? C では、この 2 つの違いは非常に微妙であり、一般的には同じ概念であると考えられます。この記事では、ハッシュテーブルとハッシュテーブルについて詳しく紹介します。

ハッシュ テーブル

ハッシュ テーブルは、ハッシュ関数に基づくデータ構造です。定数時間の挿入および検索操作をサポートします。ハッシュ テーブルのデータ要素は、ハッシュ関数の結果に従って編成されます。キーが異なると、ハッシュ関数によって返される結果は一意になります。つまり、各キー値がハッシュ値に対応します。

C でハッシュ テーブルを使用するには、標準ライブラリの unowned_map クラスを使用します。ヘッダー ファイル をインクルードした後、unowned_map オブジェクトを定義し、そのメンバー関数を使用してそれを操作できます。例:

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> grades;

    // 添加键值对
    grades["John"] = 90;
    grades["Sara"] = 85;
    grades["Bob"] = 95;

    // 查找键对应的值
    std::cout << "John's grade is " << grades["John"] << std::endl;

    return 0;
}

上の例では、unowned_map オブジェクト Grade を使用して、学生の成績クエリの関数を実装しました。 Grade["John"] を使用すると、John の成績を簡単に見つけることができ、出力結果は 90 になります。

ハッシュ テーブル

ハッシュ テーブルは、ハッシュ関数に基づいてキーを位置にマップするデータ構造です。これにより、挿入や検索などの操作を一定時間で実行できます。ハッシュ テーブルとハッシュ テーブルの中心的な考え方は同じですが、唯一の違いは、ハッシュ テーブルも競合を処理する必要があることです。

いわゆる競合とは、2 つの異なるキー値がハッシュ関数によって同じ位置にハッシュされることを意味します。現時点では、オープン ハッシュやリンク リスト ハッシュなどのハッシュ関数の競合解決方法を使用する必要があります。オープン ハッシュでは、オープン アドレス方法は、オープン スロットと呼ばれる他のスロットを使用し、キーのハッシュ値を計算してハッシュ テーブルの他のスロットにキーを挿入します。スロットがすでに占有されている場合は、別の A スロットを試します。 。リンク リスト ハッシュでは、リンク リストがハッシュ テーブルのスロットに実装されます。

C でハッシュ テーブルを使用するには、標準ライブラリの unowned_map または unowned_set クラスを使用する必要があります。これら 2 つのクラスを使用する場合、ハッシュ関数も提供する必要があります。デフォルトは std::hash クラス テンプレートで、ハッシュ可能な型の変数を一意の整数値にマップできます。例:

#include <unordered_set>
#include <string>
#include <iostream>

struct Person
{
    std::string name;
    int age;
};

bool operator==(const Person& lhs, const Person& rhs)
{
    return lhs.name == rhs.name && lhs.age == rhs.age;
}

// 哈希函数
struct PersonHash
{
    std::size_t operator()(const Person& p) const
    {
        std::size_t h1 = std::hash<std::string>()(p.name);
        std::size_t h2 = std::hash<int>()(p.age);
        return h1 ^ (h2 << 1);
    }
};

int main()
{
    std::unordered_set<Person, PersonHash> people = {
        {"John", 30},
        {"Sara", 25},
        {"Bob", 45},
    };

    // 添加元素
    people.insert({"Mary", 38});

    // 查找元素
    Person p = {"John", 30};
    if (people.find(p) != people.end()) {
        std::cout << p.name << " is found" << std::endl;
    }

    return 0;
}

上記の例では、unowned_set オブジェクトを使用して人々の情報のグループを管理します。ここで、person は、名前と年齢の 2 つのフィールドを含む構造体タイプです。カスタム ハッシュ関数 PersonH​​ash も提供されていることに注意してください。パーソン タイプはハッシュ可能なタイプではないため、そのハッシュ関数を提供する必要があります。

概要

ハッシュ テーブルとハッシュ テーブルは、C における非常に実用的なデータ構造です。実際の開発では、キーワードのセットとインデックスを維持するためによく使用されます。使用する場合は、ハッシュ関数の選択と競合への対処方法に注意する必要があります。

以上がハッシュ テーブルと C++ のハッシュ テーブルの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。