1

ハッシュに関する情報へのリンクは探していません。

私は世界最大のハッシュ関数を探しているわけではありません。

を説明するミニストーリーに興味があります

  • あなたが働いていた問題のドメイン
  • 扱っていたデータの性質
  • データのハッシュ関数を設計する際の思考プロセスについて教えてください。
  • 結果にどれほど満足しましたか。
  • その経験からあなたが学んだことは、他の人にとって価値があるかもしれません。
4

6 に答える 6

9

私が考える最初の問題は、確立されたアルゴリズムが私の要件に適合するかどうかです。

于 2008-11-11T02:56:02.223 に答える
2

データウェアハウスの開発を行っています。約9,000行のディメンションがありました。開発中のクエリには、非常に醜いクエリが含まれていました。

そこで、ディメンション行の分析を開始しました。ディメンション行は、列のさまざまな組み合わせに基づいてクラスター化されました。クラスタリングは、あるキーからそのキーを共有するディメンション行のリストへのマップでした。したがって、ハッシュキーは列値のタプルでした。

Pythonでの中間結果は、次のようになりました。

{ 
    ( (col1, col2), (col3, col4) ) : [ aRow, anotherRow, row3, ... ],
    ( (col1, col2), (col3, col4) ) : [ row1, row2, row3. row4, ... ],
}

技術的には、これは転置インデックスです。

Pythonは可変コレクション（つまりリスト）を使用しないため、ハッシュキーは列値のタプルを構築する際に注意が必要でした。さらに重要なのは、タプルが列値の単純なフラットリストではなかったことです。それらは通常、キーの組み合わせに基づいてディメンション行を互いに素なサブセットに分割しようとした2つのタプルでした。

ハッシュアルゴリズムは、深く掘り下げて、組み込みのPythonハッシュです。ただし、キーの選択は明白でも簡単でもありませんでした。

于 2008-11-11T03:03:41.600 に答える
1

ハッシュアルゴリズムの発明は簡単です。実用的で効率的かつ効果的なハッシュアルゴリズムを発明することはできません。

あなたは自問する必要があります：

  1. ハッシュが必要ですか？
  2. 次に、関連するすべての要件を含む標準のクックブックレシピ（例：Effective Java）を実装すると仮定します（例：a.equals（b）then a.hashCode（）== b.hashCode（））

等しいかどうかを比較する必要があるオブジェクトのインスタンスが2つある場合は、equals（）の実装を提供する必要があります。

ソートする必要のあるオブジェクトのインスタンスが複数ある場合は、compareTo（）の実装を提供する必要があります。

マップのキーとして使用されているカスタムオブジェクトがある場合は、おそらくhashCode（）の実装を提供する必要があります。

于 2008-11-11T05:18:30.080 に答える
1

アダムが言ったことを2番目にします：ハッシュホイールを再発明しないでください

カスタムハッシュ関数が必要になったのは、有向グラフを比較して等しいかどうかだけでした。ハッシュ関数を使用すると、2つのグラフが等しくない場合に非常に効率的に判断できます（ハッシュ値が一致した場合でも、確実にノードごとの比較を行う必要がありました）

于 2008-11-11T02:58:59.657 に答える
1

私が最初に考えるのはsteal、ハッシュアルゴリズムとそのコードに最適な場所です。適切なアルゴリズムが見つからない場合にのみ、それらを出発点として使用して独自のアルゴリズムを作成します。公平を期すために、私はこの業界に7年間携わっていますが、これまで一度も経験したことがありません。大学時代から独自のハッシュアルゴリズムを作成しました。しかし、私が独自のアルゴリズムを作成した場合、衝突を最小限に抑えることが最大の考慮事項になるはずです。あなたのありそうな価値観は何ですか？この関数はこれらの値を正確に分散して、結果の値と元の値の間に1対1の関係があることを願っていますか。結果の値は本当によく分散しますか。つまり、それらすべてに共通の要因があるわけではありませんか？これにより、モジュラス演算を実行して値を小さくし、インデックス付きコレクションに収めるときに衝突が発生する可能性があります。

于 2008-11-11T04:52:15.123 に答える
1

正確には私の経験ではありませんが、考慮しなければならない条件のいくつかは次のとおりです。

  1. 最も重要なことは、ハッシュ関数が等値チェックに類似している必要があることです。2 つの等しいオブジェクトは、常に同じハッシュを返す必要があります (2 つの等しくないオブジェクトが同じハッシュを返すことはありますが、まれです)。

  2. おそらく速度と分散のバランスが取れている可能性が高いため、既存のハッシュ関数を使用することをお勧めします。

  3. ハッシュ関数は高速でなければなりません。結果のハッシュが大幅に優れた値の分布をもたらさない場合は、少しでも遅くしたり複雑にしたりしないでください。したがって、数値型のハッシュは常に優れています (ほとんどのフレームワークには整数型のハッシュがあることに同意します)。

  4. ハッシュは、衝突の可能性が非常に少なくなければならない適切な分散を持つ必要があります。ほとんどの場合、XOR は悪い選択です。つまり、速度と配信のバランスをうまくとることが鍵となります。分散が改善されれば、ハッシュが遅くなる可能性があります。

  5. 出力のサイズを知っている関数を記述します。その場合はint32、オーバーフローが発生しないことを確認してください。

  6. ハッシュ関数は決してエラーを出すべきではありません (有効な null 参照の場合を除く)。主な原因は整数オーバーフローです。扱う。

  7. ランタイム自体の前に可能な入力が何であるかを知っている場合は、それを対象とする関数を使用して速度を上げます。

  8. ほとんどの場合、ハッシュは可逆である必要はありませんが、必要な場合 (特定のハッシュから 2 つの数値を取得するなど) は、それに応じて記述してください。これは、一般的な場合 (ハッシュが衝突する場合) には必要ない場合があります。

  9. ハッシュが 2 つのオブジェクトをすばやく比較するためのものである場合は、セキュリティ目的で使用しないでください。暗号化ハッシュは、まったく別の獣です。

  10. 手元に複数のハッシュ関数がある場合は、簡単なテストを実行して、入力に対してより適切に動作するものを見つけてください。テストは、理論的に分析するよりも常に優れています。

これらは私が頭の上から持っているものです。Eric のブログも参照してください。

于 2012-12-27T10:29:35.487 に答える