2

ハッシュを使用するアプリケーションに直面していますが、それがどのように機能するのかまだわかりません。これが私の問題です。ハッシュを使用してインデックスを生成し、それらのインデックスを使用してさまざまなテーブルにアクセスし、インデックスを使用して取得したすべてのテーブルの値を追加した後、最終的な値を取得します。これは、メモリ要件を削減するために行われます。ハッシュ関数への入力は、ランダムな定数とアプリケーションからのいくつかのパラメーターの間で XOR を実行しています。

これは典型的なハッシング アプリケーションですか? 私が理解していないのは、ハッシュを使用してメモリ要件をどのように削減できるかということです. 誰でもこれを明確にできますか?

ありがとうございました

4

4 に答える 4

3

ハッシュだけでは、メモリとは何の関係もありません。

よく使われるのはハッシュテーブルです。ハッシュテーブルは、キーオフするもののハッシュを計算することによって機能し、データ構造へのインデックスとして使用されます。

ハッシュを使用すると、キー (文字列など) を整数やビットのセットなどのよりコンパクトな値に減らすことができます。

それは、あなたが言及しているメモリの節約かもしれません-大きなキーを単純な整数に減らします。

ただし、ハッシュは一意ではないことに注意してください。優れたハッシュ アルゴリズムは衝突を最小限に抑えますが、一意の値に減らすことを意図していません。そうするのは不可能です (たとえば、ハッシュが 32 ビット整数を出力する場合、ハッシュは 2^32 の一意の値しか持たないでしょう)。

于 2009-01-15T00:31:56.853 に答える
2

あなたが話しているのはブルームフィルターですか?これは、ハッシュ関数を使用して、セットのメンバーシップをテストするスペース効率の良い方法を取得します。その場合は、説明のリンクを参照してください。

于 2009-01-15T00:31:02.940 に答える
0

ほとんどの優れたハッシュ実装はメモリ効率が悪く、そうでなければより多くの計算が必要になり、ハッシュのポイントが正確に失われます。

ハッシュの実装は、挿入、削除、取得などの操作に一定の実行時間を提供するため、処理効率のために使用されます。

タイプやサイズに関係なく、すべてのデータが常に単一の固定長形式で表現されるように、ハッシュの品質を考えることができます。

于 2009-01-15T00:45:51.223 に答える
0

これは、行われているハッシュが真のハッシュ テーブルを構築するためではなく、文字列/メモリ ブロック テーブルにインデックスを作成するだけである場合に説明できます。データに同じ文字列 (またはメモリ シーケンス) が 20 回あり、その文字列の 20 個のインスタンスすべてをそのハッシュ/テーブル インデックスだけに置き換えた場合、その方法でデータ圧縮を実現できます。ただし、ハッシュ値ごとにそのテーブルに実際の衝突チェーンが含まれている場合、今説明したことは起こっていることではありません。その場合、ハッシュの理由は、圧縮ではなく、(格納された値への迅速なアクセスを提供することによって) 実行を高速化するためである可能性が最も高くなります。

于 2009-01-15T00:51:48.700 に答える