問題タブ [hash-function]

ハッシュテーブルに入れたいデータがあると想像してみましょう。ハッシュ関数は、各データ オブジェクトのハッシュ値を計算し、このハッシュ値をテーブルに入れます (各値は独自のバケットを取得する必要があります)。ハッシュ値を使用すると、テーブル内のデータ オブジェクトの正確な位置がわかります。

ここでキーはどのような役割を果たしますか? Java の HashMap は、HashMap に入れるすべての値に対して特定のキーを必要とし、キーを使用して値を取得できます。

Hashtable (Java Hashmap) に入れたい値、ハッシュ値、キーの違いは何ですか? その背後にある数学は何ですか？

一意の構造を識別するための 3 つの int を持つ単純な C++ 構造体の場合、a、b、および c の現実的な値についてあまり知られていない場合、適切なハッシュ関数の実装となるものは何でしょうか。unordered_map のキーとして構造体を使用する必要がありますか?

私は高速になるように設計されたCでプログラムを書いています。

データフロー内の IP アドレスの出現回数を保存したいと考えています。たとえば、約 2 000 000 の IP アドレスを含む 100MB のバイナリ ファイルを分析します (ただし、プログラムは x-GB ファイルにも使用される可能性があります)。

私の考えはハッシュテーブルを使用することなので、これらのハッシュ関数が必要です:

この関数がいつか衝突しても問題はないと思います (Separate chaining を使用してこれを解決します)。

• どのハッシュ関数を使用すればよいですか?
• この問題にはハッシュ テーブルを使用することをお勧めします。

ちょっとした数学:

• 20b index = 1 048 576 要素 (足りるか? )
• 32b 要素 = 4B 要素 = 4MB テーブル サイズ (プログラムが現在のコンピュータで実行される場合、このサイズは問題ありませんか? )

注: IP アドレスでマスクが指定されている場合があります。例: IPv4/24 --> 現在、2^32 ではなく 2^24 の異なる IPv4 アドレスしかありません。マスクが設定されている場合、別のハッシュ テーブル サイズを使用する必要がありますか?

絶対に優先するのはスピードです。

元の問題の参照: Poker-Monte-Carlo-Simulation の手評価アルゴリズムの最適化

5 から 7 枚のカードのリストがあり、それらの値をハッシュテーブルに格納したいと考えています。ハッシュテーブルは 32 ビット整数の配列であり、インデックスとしてハッシュ関数値によって直接アクセスする必要があります。52 枚のカード デッキで可能な組み合わせの量が多いことに関しては、あまり多くのメモリを浪費したくありません。

数字:

• 7 カードの組み合わせ: 133784560
• 6 カードの組み合わせ: 20358520
• 5 カードの組み合わせ: 2598960
• 合計: 156.742.040 可能な組み合わせ

1 億 5700 万の 32 ビット整数値を保存するには、約 580MB のコストがかかります。したがって、不要な値のために配列内のメモリを予約することで、この数を増やすことを避けたいと思います。

問題は次のとおりです: ハッシュ関数はどのように見えるでしょうか? 可能性のある重複していないカードの組み合わせを 0 から 156.742.040 までの連続した値にマッピングするか、少なくともそれに近い値にしますか?

試験の準備中に、ハッシュ テーブルに関する質問に出くわしました。次のハッシュ関数を使用して、長さ 11 のテーブルが与えられます。

次に、ハッシュ テーブルのサイズが 12 に変更されます。したがって、新しいハッシュ関数は次のようになります。

どのような問題が発生しますか?

ハッシュ関数と辞書を取り、単語のハッシュ値をビットベクトルにマップするスペルチェッカーを実装しようとしています。より具体的には、ハッシュ関数のリストと単語の辞書を入力として受け取り、スペルチェッカーを返す gen-checker という関数を作成しようとしています。スペルチェッカーは、単語の正しいスペルまたは間違ったスペルを示す #t または #f を含む、辞書の入力のビットベクトル表現を生成する必要があります。

既に has 関数を定義しており、使用する辞書を持っていますが、ビット ベクトルのセットアップを取得できないようです。

ここにある（make-bitvector 8 #f）を実装してみました：

http://www.gnu.org/software/guile/manual/html_node/Bit-Vectors.html

しかし、何らかの理由でドラケットはそれを認識しません。私は何を間違っていますか？ビットベクトル表現を実装する方法は?

ハッシュ テーブル プログラムの特定のキーに対してビット演算を実行しようとしています。私が理解しようとしている方法は、フォールディング、ミッドスクエア、切り捨て、および基数です。誰かが私に直接の答えをくれるとは思っていませんが、私を正しい方向に導く手助けをしてください。これを参照する通信やヘルプ、または役立つ可能性のあるアルゴリズムをオンラインで見つけることができません。シフト、XOR、OR、AND< など、2 進数の演算の一部を示すビット単位のプログラムがあります。私が理解していないのは、32 ビットの 2 進数の 1 つの部分のみを選択する方法です。たとえば、中央の 4 ビットを選択し、それらだけを演算に使用する正方形などです。いろいろ試してみましたが、以下の方法に行き着きました。ミッドスクエアは機能すると思います（確かではありませんが）、しかし、大きな整数でのみ機能するようです。折りたたみと切り捨ては確実に機能していません。私は基数法を試みたことさえありません。ヘルプ、ガイダンス、または最も役立つ適切なドキュメントへの参照は素晴らしいでしょう。

編集（改訂）：わかりました、ここに私が行ったいくつかの改訂があります。これらのいずれかが正しいかどうかはわかりませんが、何が変更され、より最適化され、完全に間違っているかを教えてください。4つの方法すべてで出力が得られますが、大丈夫かどうかはまだわかりません。一つ一つ詳しく調べていません。

改訂されたコード:

最近、Jeff Six 著の Application Security For The Android Platform を読んでいて、不可解な記述に出くわしました。ソルトとハッシュ関数を説明する際の暗号化セクションで、このステートメントが作成されました

IV [Initialization Vector] と同様に、salt 値はランダムである必要がありますが、秘密にしておく必要はありません。

これは本当ですか？ソルトとハッシュ関数についての私の理解は、このステートメントは間違っており、ソルトが解放された場合、ソルトを不要にする新しいレインボーテーブルを生成できるため、ソルトを保護する必要があるということでしたか? これは正しいです？それとも、塩を秘密にしておく必要は本当にないのでしょうか? それはなぜですか?