問題タブ [hash-function]

A/B テストを実行するために、ユーザーを複数のグループに分割したいと考えています。

通常のアプローチでは、各ユーザーをランダムにバリアントに割り当て、A/B テストが終了するまで関係を保存します。しかし、それは私がその関連付けをどこかに保存することを余儀なくされるので、私はそれを避けたい.

ユーザーは既にアプリケーションに登録されているため、A/B テストで偏りのない結果を取得できるように、テスト全体でユーザーを均一に分散する機能が必要です。

どの種類のハッシュ関数を使用すればよいですか?

さまざまな長さの文字列の並べ替えとカスタムハッシュ関数のパフォーマンスを比較していますが、結果は少し驚くべきものです。次のコードの関数prime_hash（特にprime_hash2）は、sort_hashよりもパフォーマンスが優れていると期待していましたが、その逆が当てはまります。誰かがパフォーマンスの違いを説明できますか？誰かが代替ハッシュを提供できますか？[関数は、文字の同じ分布を含む文字列に対して同じ値を生成し、他のすべての文字列に対して異なる値を生成する必要があります]。

これが私が得ている結果です：

そしてここにコードがあります：

PRNG関数の強度をテストする方法の1つは、PRNG出力をランダム文字列から区別するテストを設計することです。いくつかのuまたはランダム文字列に対してPRNG（u）を出力するボックスが与えられます。出力がPRNGからのものかどうかを判断する必要があります。ハッシュ関数Hがこのテストに失敗したと仮定します。

それは、2番目の原像耐性がないことを意味しますか？

Webmatrix.WebData.Security ライブラリを使用して、サイトのログイン/登録機能を制御しています。CreateUserAndAccount() メソッドは、ユーザーが指定したパスワードをハッシュし、テーブル webpages_Membership 内に保存します。メソッドがそれをハッシュする方法を理解するのに苦労しています。誰かが私を正しい方向に向けるのを手伝ってもらえますか?

ハッシュ関数を理解しようとしているのですが、その中で BlockCopy が使用されている理由がわかりません。

3種類のプロービングを使用して、プロジェクトのハッシュテーブルを実装しています。現在、リニアに取り組んでいます。

線形プロービングについては、プロービングがどのように機能するかを理解しており、私のインストラクターは、ステップサイズを1にしたいとほのめかしました。つまり、重複は許可されていません。ですから、値を挿入する前に、値を「検索」する必要がありますよね？しかし、すべてのセルが「占有」または「削除」されるまでテーブルが使用された場合はどうなるでしょうか。次に、特定のキーを検索してそのキーがテーブルにないことを確認するには、テーブル全体を検索する必要があります。つまり、検索操作（ひいては挿入操作）はO（n）です。

それは正しくないようで、私は何かを誤解したと思います。

テーブルは少なくとも半分空である必要があり、決定された数の要素のみをプローブするため、2次プローブで同じ問題に遭遇する必要はないことを私は知っています。また、ダブルハッシュの場合、挿入するキーが存在しないことを証明するためにテーブルを検索する必要があるため、これがどのように機能するかはわかりません。しかし、どのセルも「占有されていない」場合に検索を停止する方法をどのように知ることができますか？

したがって、過去にテーブル内のすべてのエントリが占有されていたオープンハッシュでは、要素を検索するためにO（n）プローブが必要ですか（重複が許可されていない場合は挿入します）？

辞書のすべての単語にfnv1aハッシュ関数を実装しようとしています（後ですぐにアクセスできるように）。

これはfnv1aハッシュ関数です。

そして、これは私がload（）と呼ばれる関数で単語のハッシュを取得しようとしている方法です：

完全な機能は次のとおりです。

/**辞書をメモリにロードします。成功した場合はtrueを返し、そうでない場合はfalseを返します。* /

このコードをコンパイルするときに発生し続けるエラー（単語をハッシュしようとしている行を指しています）：

char*をキーとして、 を としてvector<int>持つunordered_map を作成したいと思いますvalue。以前の質問からchar* 、STL にはハッシュ関数が提供されていないことがわかりました。

このサイトから最初の実装を取得しました: http://www.cse.yorku.ca/~oz/hash.html

私のmain.cppファイルを持っているので、次のコードを挿入しました：

次に unordered_map 変数を作成しました。

ただし、これを実行して値「temp」を2回挿入すると:

ベクトルの各要素が 0 または 1 であるサイズ 2 のベクトルを持つ 1 つの「temp」キーを持つ代わりに、最終的なマップには、「temp」という名前の 2 つのキーと、各キーにサイズ 1 のベクトルがあります。

ここに詳細な画像:

どうすればこれを回避できますか? 前もって感謝します

2 つのセット間の類似性を推定する MinHash 手法について読んでいます。セット A と B が与えられた場合、h はハッシュ関数であり、hmin(S) はセット S の最小ハッシュです。つまり、hmin(S)=min(h(s(s) )) S の s に対して、次の方程式があります。

p(hmin(A)=hmin(B))=|A∩B| / |A∪B|

これは、A の最小ハッシュが B の最小ハッシュと等しい確率が、A と B の Jaccard 類似度であることを意味します。

私は上記の式を証明し、独自の証明を考え出そうとしています: a∈A と b∈B に対して、h(a)=hmin(A) と h(b)=hmin(B) となります。したがって、hmin(A)=hmin(B) の場合、h(a)=h(b) となります。ハッシュ関数 h がキーを個別のハッシュ値にハッシュできると仮定すると、a=b の場合にのみ h(a)=h(b) となり、その確率は |A∩B| になります。/ |A∪B|。ただし、ハッシュ関数は異なるキーに対して同じ値を返す可能性があるため、私の証明は完全ではありません。そこで、ハッシュ関数に関係なく適用できる証明を見つけるために、あなたの助けを求めています。