GLibのHashTablesはどのように役立つのですか？

Question

私はハッシュ関数の考え方に精通していますが、GLibの実装がどのように役立つかは不明です。これを例を使って説明します。

数値理論（私は数学者です）に依存する奇妙な方法で正の実数に再帰的（何らかの形で）な高価な関数があるとします。ある小さな範囲の大きな数で関数を計算する必要のあるアルゴリズムがあるとしましょう。 [1000000000 - 1000999999]と言ってください。

高価な関数を100万回呼び出したくないので、再帰的に値をメモし始めます。それから各呼び出しで関数を最初から計算する必要はありません。私が既に計算した低い数値（再帰​​中）の関数の値を覚えておいてください。その第1レベルの再帰での実際の総コール数が低いと仮定しよう。繰り返しの価値がたくさんあり、メモは実際にあなたに多くの時間を節約します。

これは、なぜハッシュテーブルのデータ構造が有用であるかを理解する漫画的な方法です。私が得意ではないことは、事前に必要なキーを正確に知らなくてもこれを行う方法です。

再帰関数は一般的に数値理論的なので、どの値を繰り返し使用するか分かりません。だから私はバケツ（ハッシュテーブル）に私の関数への再帰的な呼び出しのポップアップでこれらを投げたいです

GLibでは、あなたの（キー、値）のペアは、常にあなたは個人的にどこかに横たわっていなければなりません。私の関数が入力xを計算している場合。私は前に値xを見たことがあるかどうかを知る方法がわかりませんが、関数g_hash_table_contains（）には値xではなくポインタが必要です。だから何が使えますか？

私はまだ親切に勉強しています。私はCでのコーディングに精通していますが、この言語でハッシュテーブルをまだ使用していないので、そうしようとしていて、GLibでそれに熟達していますが、これは得られません。

Answer 1

私はそれを説明するためにそれを掘ってみましょう。 まず、ハッシュマップを使用している場合は、必ず入力として[キー、値]のペアが必要です。

ハッシュマップのユーザーとして、私たちは鍵の選択について独創的でなければならず、用途によっても異なります。

あなたの場合、私が理解する限り、あなたは範囲で動作し、結果を与える機能を持っています。そして、計算の際には、大きな問題を構成する小さな問題の結果を使用できるようにメモを使用します。

たとえば、文字列が[10000000009]の[1000999998]の結果を使用する可能性のある文字列をキーとして使用すると、1000999997などの結果をさらに使用する可能性があります。ハッシュマップで計算し、ハッシュマップに保存します。

簡単に言えば、ユーザーとして、私たちは鍵を選択することについて創造的である必要があります。 データベースの主キーの選択について考える必要がある場合、理解するべき類似点は、あなたがやった方法です。

もう一つの例は、ハッシュマップを使ってfibonacci（n）を解くことについて考えた方法です。