問題タブ [hash-function]

Google 検索から取得した以下の VB 関数をテストしています。これを使用して、文字列をすばやく比較するためのハッシュ コードを生成する予定です。ただし、2 つの異なる文字列が同じハッシュ コードを持つ場合があります。たとえば、これらの文字列

「122Gen 1 ヒープ サイズ (.NET CLR メモリ w3wp):mccsmtpteweb025.20833333333333E-02」

「122Gen 2 ヒープ サイズ (.NET CLR メモリ w3wp):mccsmtpteweb015.20833333333333E-02」

同じハッシュ コード 237117279 を持っています。

教えてください: - 関数の何が問題になっていますか? - どうすれば修正できますか?

ありがとうございました

マーティン

のペアを にマップする必要がありますがlong long、double使用するハッシュ関数がわかりません。各ペアは、任意の 2 つの数字で構成されますが、実際には、通常はその前後の数字になります0(100ただし、これは保証されません)。

これがtr1::unordered_mapドキュメントです。私はこのように始めました：

一般に、どのハッシュ関数を使用すればよいかわかりません。優れた汎用ハッシュ関数とは?

私はMD5 ハッシュ値に関するこの質問を読んでいましたが、受け入れられた回答は私を混乱させます。私が理解しているように、暗号化ハッシュ関数の主な特性の 1 つは、同じハッシュ値を持つ 2 つの異なるメッセージ (入力) を見つけることができないということです。

しかし、なぜ MD5 ハッシュ値が元に戻せないのかという質問に対するコンセンサスの答えはまだありません。無限の数の入力文字列が同じ出力を生成するためです。 これは私には完全に矛盾しているように思えます。

また、アルゴリズムが公開されているにも関わらず、ハッシュ値が依然として元に戻せないという事実は、私を多少困惑させます。これは、ハッシュ関数で常にデータが失われるため、どのデータが破棄されたかを知る方法がないためですか?

入力データ サイズが固定出力データ サイズよりも小さい場合 (たとえば、パスワード "abc" のハッシュ) はどうなりますか?

編集：

OK、私がこれをまっすぐに持っているかどうか見てみましょう:

1. 同じ出力を生成する入力文字列が無数にあるため、ハッシュから入力を推測するのは非常に困難です(元に戻せないプロパティ)。
2. ただし、同じ出力を生成する複数の入力文字列のインスタンスを 1 つでも見つけることも非常に困難です (衝突耐性の特性)。

パフォーマンス上の理由から、文字列で識別されるオブジェクトのセットをグループに分割する必要があります。オブジェクトは、数字または識別子の一部をドットで区切る接頭辞（修飾）形式の文字列のいずれかで識別できます。

数値識別子は1から数百万です。テキスト識別子は、同じ名前空間プレフィックス（ns1 ::）と同じパスプレフィックス（edit.box。）で始まるものが非常に多い可能性があります。

この目的に最適なハッシュ関数は何ですか？オブジェクト識別子の統計に基づいて、バケットのサイズを何らかの形で予測できればよいでしょう。いくつかの統計情報に基づいて優れたハッシュ関数を構築するための優れた記事はありますか？

このような識別子は数百万ありますが、目的はハッシュ関数に基づいて1〜2千のグループに分割することです。

単純なWebアプリでは、URLをファイル名またはファイルパスにマップする必要があります。

このアプリには、コアPerlディストリビューション（5.6.0以降）のモジュールにのみ依存できるという要件があります。問題は、ほとんどのファイルシステムのファイル名の長さが255に制限されていることです。別の制限は、単一のフォルダ内の約32kのサブディレクトリです。

私の解決策：

信頼できますか？どうすれば改善できますか？

ハッシュ テーブルは、データを保存/取得する最速/最良の方法であると言われています。

ハッシュテーブル、ハッシュについての私の理解は次のとおりです（間違っている場合は修正してください。他に何かあれば追加してください）：

• ハッシュ テーブルは、値を格納するための配列 (単一または多次元) に他なりません。
• ハッシュは、データを挿入/取得するために配列内のインデックス/場所を見つけるプロセスです。データ項目を取得し、それをキーとしてハッシュ関数に渡すと、データを挿入/取得するインデックス/場所を取得できます。

質問があります：

データの保存/取得に使用されるハッシュ関数は、MD5、HMAC、SHA-1 などの認証用のセキュリティ アプリケーションで使用される暗号化ハッシュ関数とは異なりますか?

それらはどのように異なりますか？

• Cでハッシュ関数を書くには?
• それに対する標準やガイドラインはありますか？
• ハッシュ関数の出力、つまりインデックスが範囲外にならないようにするにはどうすればよいでしょうか?

これらをよりよく理解するための良いリンクをいくつか挙げていただければ幸いです。

特定のプロパティを持つデータ構造に対して衝突のないハッシュ関数を作成することは可能ですか？

1. データ構造はint[][][]です。
2. 重複は含まれていません
3. それに含まれる整数の範囲が定義されます。それが0..1000であるとしましょう、最大整数は間違いなく10000以下です。

大きな問題は、このハッシュ関数も非常に高速である必要があることです。そのようなハッシュ関数を作成する方法はありますか？整数の範囲に応じて、実行時にたぶん？

追加：このハッシュ関数の目的は、特定の組み合わせが処理されたかどうかを簡単にチェックすることです。したがって、データ構造内の数値の組み合わせが処理されるときに、ハッシュ値を計算して保存します。次に、データ構造内の数値の別の組み合わせを処理するときに、ハッシュ値を比較します。

SHA-1の代わりにSHA-2暗号化を実装しようとしています。

このため、これら 2 つのハッシュ アルゴリズムのビット数が異なることがわかっており、混乱しています。

これはどのように達成でき、どの部分で必要な変更を加える必要がありますか?

Java、Python、その他の主要なプログラミング言語のオープン ソース ライブラリを使用できます。

1 ～ 15 バイトの範囲のバイト シーケンス (文字列) でキーを検索するハッシュ テーブルを作成したいと考えています。

整数値を格納したいので、ハッシュ用の配列で十分だと思います。特定のキーが配列にインデックスを与えるようなハッシュ関数を構築する方法を概念化するのに苦労しています。

どんな援助でも大歓迎です。

ハッシュ内のエントリの最大数は、4081*15 + 4081*14 + ... 4081 = 4081((15*(16))/2) = 489720 です。

たとえば、次のようになります。

ハッシュ関数の適切な選択肢は何ですか? または、ハッシュ関数を構築するにはどうすればよいですか?

ありがとう。