問題タブ [hash]

VS2005 の標準ハッシュ関数は、高パフォーマンスのルックアップを実現しようとすると非常に遅いことがわかりました。ほとんどの衝突を無効にする高速で効率的なハッシュ アルゴリズムの良い例は何ですか?

この質問は、タプルに関する議論から生まれました。

タプルが持つべきハッシュコードについて考え始めました。KeyValuePair クラスをタプルとして受け入れるとどうなるでしょうか? GetHashCode() メソッドをオーバーライドしないため、おそらく「子」のハッシュ コードを認識しないでしょう...したがって、ランタイムは Object.GetHashCode() を呼び出しますが、これは認識されません。実際のオブジェクト構造。

次に、GetHashCode() と Equals() がオーバーロードされているため、参照型の 2 つのインスタンスを実際に Equal にすることができます。そして、それらをタプルの「子」として使用して、辞書を「ごまかす」。

しかし、うまくいきません！ランタイムはどうにかしてタプルの構造を理解し、クラスのオーバーロードされた GetHashCode を呼び出します!

それはどのように機能しますか？Object.GetHashCode() によって行われた分析は何ですか?

複雑なキーを使用する場合、悪いシナリオでパフォーマンスに影響を与える可能性はありますか? (おそらく、不可能なシナリオ...しかし、それでも)

次のコードを例として考えてみましょう。

更新以下の回答で説明されているように、これについての説明を見つけたと思います。その主な成果は次のとおりです。

• キーとそのハッシュ コードには注意してください :-)
• 複雑な辞書キーの場合、Equals() と GetHashCode() を正しくオーバーライドする必要があります。

多くの皆さんと同じように、私は ReSharper を使用して開発プロセスを高速化しています。クラスの等価メンバーをオーバーライドするために使用すると、生成されるコード生成はGetHashCode()次のようになります。

もちろん、そこには私自身のメンバーもいますが、私が知りたいのは、なぜ 397 なのかということです。

• 編集：だから私の質問は、素数である以外に397の素数について「特別な」何かがあるのでしょうか？

同じクレジット カード番号が 2 つの異なるアカウントに登録されないようにしたいシステムがあります。クレジット カード番号は内部に保存されないため (下 4 桁と有効期限のみ)、単純にクレジット カード番号と有効期限を比較することはできません。

現在のアイデアは、カードの登録時にクレジット カード情報のシステムにハッシュ (SHA-1) を保存し、ハッシュを比較してカードが以前に使用されたかどうかを判断することです。

通常、salt は辞書攻撃を回避するために使用されます。この場合、私たちは脆弱であると想定しているため、ハッシュとともにソルトを保存する必要があります。

この方法に欠陥はありますか？これは、この問題を解決する標準的な方法ですか?

最初に: 私は、Adobe InDesign CS3 のスクリプト エンジンとして埋め込まれた JavaScript のややあいまいな実装を使用しています。この実装は、「標準」の JavaScript から逸脱することがあるため、私の問題です。

John Resig の jsdiff ライブラリ( source here ) を使用して、2 つのドキュメント間で選択したテキストを比較しています。jsdiff は通常のオブジェクトを連想配列として使用して、単語をテキストから別のオブジェクトにマップします。(jsdiff.js の 129 行付近の「ns」変数と「os」変数を参照してください。)

テキストに「反映」という言葉が出てくると、頭痛が始まります。「reflect」は、すべてのオブジェクトのデフォルトの読み取り専用プロパティです。jsdiff が連想配列の値を ns['reflect'] に割り当てようとすると、すべてが爆発します。

私の質問: これを回避する方法はありますか? 明らかなバニラオブジェクトを使用せずにJavaScriptでハッシュテーブルを作成する方法はありますか?

基本原則:スクリプト エンジンを切り替えることはできません。:)

awkで次のことを行う簡単な方法はありますか?

• データによる配列/ハッシュのソート
• 文字列キーによるハッシュのソート

ハッシュ テーブルを使用して非常に単純なキャッシュを維持する Perl スクリプトがあります。Perl (32 ビット) のメモリ不足とクラッシュを避けるために、ハッシュが n バイトを超えたらハッシュをクリアしたいと考えています。

キーと値のペアの数を確認できます。

しかし、ハッシュが占有する実際のメモリを確認することは可能ですか?

コレクションのメソッドの最適な実装をどのように決定しますかhashCode()(equals メソッドが正しくオーバーライドされていると仮定して)。

すばやく検索したい、関連のない名前の付いたものがたくさんあります。「ツチブタ」は常にどこでも「ツチブタ」であるため、文字列をハッシュして整数を再利用すると、比較が高速化されます。名前のセット全体は不明です (そして時間の経過とともに変化します)。小さな (32 または 16) ビット値を生成し、衝突率が低い高速文字列ハッシュ アルゴリズムは何ですか?

C/C++ に固有の最適化された実装を見たいと思います。

Python の基本的なデータ構造の 1 つはディクショナリです。ディクショナリを使用すると、任意の型の「値」を検索するための「キー」を記録できます。これは内部的にハッシュ テーブルとして実装されていますか? そうでない場合、それは何ですか?