ハッシュテーブルと C++ のハッシュテーブル-C++-php.cn

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

WBOY

リリース： 2023-08-21 21:58:43

オリジナル

1519 人が閲覧しました

ハッシュテーブルと 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 つのフィールドを含む構造体タイプです。カスタムハッシュ関数 PersonHash も提供されていることに注意してください。パーソンタイプはハッシュ可能なタイプではないため、そのハッシュ関数を提供する必要があります。

概要

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

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