問題タブ [hash-function]

現在、15 パズル ソルバー (C++) を作成していますが、15 パズルだけでなく、3x4 パズル、8x8 パズルなども解く必要があります... - > X x Y パズル。訪れた州に関する情報をどうにかして保持する必要があります。私の最初のアイデアは、たとえばツリーを作成することでした:
パズル:

状態 1
1 2
3 0

状態 2
1 3
0 2

私は私のツリーに保管します：

root->1->2->3->0
            \_
                \->3->0->2

これは、すべてのパズルの 5x3、6x6 などのパズルでも機能します。

このアイデアは機能しますが、多くのメモリを浪費し、ノードを追加するには時間がかかります:/ したがって、非常に非効率的です。

次のアイデアは、訪問した状態を stl の std::map< > に保持することでしたが、パズル状態からショートカットを作成するための適切なハッシュ関数を作成する方法がわかりません (パズル状態を保存する必要がないため、必要なのはstd::map への鍵、または訪問された状態に関する情報を保持するための他のアイデアについて、何か考えはありますか?

インタビューで、整数または文字列にハッシュ関数を使用する必要がある状況に遭遇しました。そのような状況では、どちらを選択する必要がありますか? これらの状況で私は間違っていました。なぜなら、多くの衝突を生成するものを選択することになりますが、ハッシュ関数は数学的な傾向があり、インタビューで思い出すことができないからです。少なくともインタビュアーが整数または文字列入力に対するあなたのアプローチに満足するように、一般的な推奨事項はありますか? 「インタビューの状況」で両方の入力に適している関数はどれですか

(メカニズムhashを使用して) カスタム データ型に対して関数を自動的に生成できるように、汎用関数を作成した人はいますか? deriving何度か、私は次のようなボイラープレートを書きました。

これは自動的に生成できます。基本的な考え方は、データを追加するたびに、たとえばリストで素数を掛けることです。

要するに、私が書きたいのは

編集 1

皆様、大変参考になる回答をありがとうございました。時間があれば、演習としてジェネリック メソッドを追加してみます。今のところ (おそらく sclv は何を参照していたのでしょうか?)、もう少し良いコードを書くことができることに気付きました。

編集 2

ghc を使用すると、編集 1 でのタプルよりも、ランダムな素数による乗算の方がはるかにうまく機能します。Data.HashTable との競合は、95% (非常に悪い) から 36% になりました。コードはここにあります: [ http://pastebin.com/WD0Xp0T1 ] [ http://pastebin.com/Nd6cBy6G ]。

次のコードを検討してください

問題は、なぜ s2 のサイズが 1 ではなく 2 なのかということです。ハッシュ関数と関係があるに違いないと確信しています。ブーストドキュメントを見て、ハッシュ関数をいじってみましたが、うまくいきませんでした。

アイデア？

私の理解では、次のように思います。

1. 2 つのオブジェクトが同じハッシュコードを持つことは完全に合法です。
2. 2 つのオブジェクトが (equals() メソッドを使用して) 等しい場合、それらは同じハッシュコードを持ちます。
3. 2 つのオブジェクトが等しくない場合、同じハッシュコードを持つことはできません

私は正しいですか？

正しければ、次の質問HashMapがあります。オブジェクトのハッシュコードを内部的に使用します。では、2 つのオブジェクトが同じハッシュコードを持つことができる場合、どのHashMapキーを使用するかを追跡するにはどうすればよいでしょうか?

HashMapオブジェクトのハッシュコードを内部で使用する方法を誰かが説明できますか?

ブルーム フィルターに複数のハッシュ関数 (SHA と MD5 など)が必要な理由がよくわかりません。

たとえば、より大きなSHA ハッシュを作成し、それを複数の部分に分割して、個別のハッシュとして扱ってみませんか? その方が速度的に効率的ではないですか？

プログラムにユーザーのパスワードを保存しようとしていますが、プレーン テキストで保存したくありません。したがって、私はそれをハッシュして代わりに保存しています。ユーザーがプログラムの開始時にパスワードを入力する必要がある場合 (不正なユーザーから保護するため)、入力されたパスワードをハッシュし、2 つのハッシュを比較しています。

ただし、次のコードは、入力されたほぼすべてのパスワードに対して同じハッシュを生成しています。次のコードを修正する方法を誰かに教えてもらえますか、またはより良いハッシュ関数を教えてもらえますか?

ご協力ありがとうございます。

GSMモデムまたはイーサネット接続のいずれかを使用してネットワークに接続するデバイスに統一された一意のIDを与えるために使用できるハッシュ関数を探しています。

したがって、特定のデバイスについて、ハッシュの生成に使用できるIMEI番号またはMACアドレスがハードコーディングされています。

私はここ数時間ハッシュ関数を研究していて、使用したいと思うかもしれないさまざまな非暗号化および暗号化ハッシュを読んでいます。ハッシュはあまり頻繁に計算されないため、私の焦点はパフォーマンスよりも衝突が少ないことです。

私のフロントランナーは、MD5、FNV-1a、MurmurHash2、Hsieh、およびDJBです。

私が使用するハッシュはすべてCで実装する必要があり、小さなプロセッサを搭載したマイクロコントローラで使用されます。

ニーズに合った適切なハッシュ関数を選択する秘訣は、どのような種類の入力をフィードするかを知ることです。

私がこの質問をしている理由は、IMEIとMACの両方が有限の長さと範囲を持っているという考えが頭に浮かんだので、おそらく両方の完全なセットをカバーでき、衝突がない非常に単純なハッシュ関数が存在するからです。（したがって、完全なハッシュ関数）

IMEI番号は10進数の15桁（16進数で12〜13バイト？）で、MACアドレスは6バイトです。よく考えてみると、2つの入力番号のセットが衝突することはないと思いますが、それが間違っている場合は、遠慮なく訂正してください。もしそうしたら、それを防ぐために何かできるでしょうか？セットの1つにシードを追加しますか？

私は正しい方向に進んでいますか？これらの組み合わせたセットに最適なハッシュ関数を見つけることは可能ですか？

ありがとう！

アップデート

回答とコメントをありがとう。ハッシュ関数として恒等関数;）を使用し、数値のセット間で重複する可能性があるため、マスクも使用することになりました。

IMEI、IMEISV、およびMACはすべて6.5バイト以下に収まるので、値を7バイトに格納してから、最初のバイトで、数値の取得元のセットに基づいたマスクを使用してビット単位のORを実行します。すべてのセットで一意です。

文字列の局所性保持ハッシュ関数の実装 (または複数) を提供する Java ライブラリはありますか?

このように unordered_map を定義する必要があります。関数を定義してこのマップにunordered_map<pair<int, int>, *Foo>渡すための構文は何ですか?hashequal

私はそれにこのオブジェクトを渡そうとしました:

そして運がない：

私はそれが何をsize_type_Buskets意味するのか分からないので、私はそれを与えました1。それを行う正しい方法は何ですか？ありがとう。