問題タブ [hash-function]

長さ128文字のブール文字列(「01100..001」など)があります(0/1の128個を意味します)。Java で効率的な (高速な) ハッシュ関数を探しています。これは、128 ビットよりもはるかに低い表現を生成し、明らかに衝突が少ないものです。誰でも私を助けることができますか、そのようなハッシュ関数はありますか? なにか提案を ？

ハッシュ関数の使用に問題があります。ドキュメント内のすべての単語にいくつかの番号（128ビットまたは64ビット）を割り当てる必要があります。したがって、「類似性」のハッシュ値は「類似性」に近い必要があります。つまり、similarity => 10022（say）の値がある場合、similar=>10025になります。これは似たような言葉で近づくはずです。また、異なる名前のハッシュ値も類似している必要があります。つまり、「john」のハッシュ値も「michel」または「sita」とほぼ同じである必要があります...など。誰かがそれについて何か考えを持っているなら。

よろしくお願いします。:)

重要なお知らせ：

これは、人々がハッシュについて意見を述べるためのディスカッション スレッドではありません。指定された関数をJavaで機能させる方法を知る必要があるだけです-例が最適です。

問題：

保留中のインタビューに向けてハッシュ関数の理解を深めるために、MIT コンピューター サイエンスの教授による 2 つの無料講義 (http://videolectures.net/mit6046jf05_leiserson_lec08/) を見ています。そこで、講義の後、Javaで以下のハッシュ関数を実装しようとしています。

これはJavaで簡単に実装できると思いました。しかし、w=32 で 2^w を実行すると、Java で不正確な結果が得られます。実際2^32 = 4294967296には Java ではなく、結果を2^31 - 1orに切り捨て2147483647ます。

Javaで関数を実装するために、この問題を修正する方法を知っている人はいますか?

編集：

多くの返信が 32 に集中しているのを目にします。私のコンピューターが 64 ビットの場合はどうなりますか? w = 32Javaを使用しているため、設定に行き詰まっていますか?

私はGoogleAppEngineでdjangononrel/djangoappengineを使用しています。複合主キーを直接指定することはできません。ただし、この動作をエミュレートすることは可能です。最善のアプローチは何か疑問に思っています。

問題

次のデータモデルを検討してください

（セールスマン、年）を主キーとして扱いたい。つまり、私がそうするなら

'テーブル'AccumulatedSalesには1つの行が含まれている必要があります。したがって、2回目の保存で最初の保存が上書きされます。

考えられる解決策

質問

• このアプローチは良いですか、それとも「正しいアプローチ」ですか？
• フィールドキーに最適なデータ型は何ですか？個人的には128ビットフィールドが欲しいのですが、私の知る限りでは利用できません。

大学のコースでMASH-2ハッシュ関数を使用しましたが、試験では、関数電卓のみを使用してこのような（（62500）^ 257））mod（238194151）を計算するための質問に直面しました。今、私はa ^ b（mod n）を使ったいくつかの理論を知っていますが、上記の問題を手動で計算することさえ困難です。これを解決するには約15分かかると思います。これを行うためのより速い方法があるかどうか知りたいです。または、2進数でそれを行う方法がある場合でも（数値を2進数に変換してから、いくつかの操作を行います）。関数電卓を使って手作業でこれを行う必要があります。

私は数学に優れたスキルを持っていないので、将来変更される可能性があるクラスで使用する必要があるアルゴリズムが存在するかどうかを尋ねます.

次のシナリオを検討してください。

クラス「ロール」には次のフィールドがあります。

数週間後、ロール「ゲスト」を追加することにしました。

数週間後、「プリンター」の役割を削除することにしました。

ハッシュコードをデータベースに永続化するため、このクラスのすべてのバージョンが一意のハッシュコードを生成することを 100% 確信する必要があります。

これは問題ではないかもしれませんが、私は常に Eclipse IDE ソース ジェネレーターで提供されているものを使用してきました。

Eclipse IDE (Indigo) Java バージョン >= 6 メソッドで安全かどうか、またはこのトピックに関する他のアドバイスを教えてください。これは非常に一般的なことだと確信しています。

前もって感謝します

MIT朗読からの良いハッシュ関数の特性：

1. 単純な均一ハッシュの仮定を（ほぼ）満たします。各キーは、m個のスロットのいずれかに等しくハッシュされる可能性があります。
2. ハッシュ関数は特定のスロットに偏ってはいけません。同じスロットに類似のキーをハッシュしないでください（たとえば、コンパイラのシンボルテーブルは変数iとjを同じスロットにハッシュしないでください。これらは、多くの組み合わせで使用されるためです）。
3. 計算が速く、O（1）ランタイムが必要です
4. 決定論的です。h（k）は、指定されたkに対して常に同じ値を返す必要があります

誰かがポイント2をさらに説明できますか？変数名はハッシュ関数と何の関係がありますか？

編集：私はJavaを使用しています。したがって、回答にJavaセマンティクスを使用した説明が含まれている場合は、問題ありません。

Scala でCount-Min Sketchアルゴリズムを実装しようとしているので、k 個のペアごとに独立したハッシュ関数を生成する必要があります。

これは私がこれまでにプログラムしたことのあるものよりも低レベルであり、アルゴリズム クラス以外のハッシュ関数についてはあまり知りません。

MD5 や MurmurHash などのハッシュ関数を使用する必要がありますか? f(x) = ax + b (mod p)p が素数で、a と b がランダムな整数である という形式の k 個のハッシュ関数を生成するだけですか? (つまり、誰もがアルゴリズム 101 で学習するユニバーサル ハッシング ファミリー)

私は生の速度よりも単純さを求めています (たとえば、実装が簡単な場合は、5 倍遅いものを使用します)。

私は言語の通訳を書いています。問題があります: 任意の型の値をインデックスで配置できる型辞書を作成したいのですが、任意の型の値 (simple[int,float,string] または complex[list,array,dictionary] の単純型または単純型の複合体 ...)。これは python-lang と同じです。ハッシュ関数のどのアルゴリズムを使用すればよいですか?

文字列のハッシュには多くの例があります。最も単純なものは、すべての文字の合計を 31 倍し、HASH_SIZE で割った単純な数値です。

しかし、DIFFERENT TYPES については、もっと複雑なアルゴリズムに違いないと思います。SHA256 を見つけましたが、ハッシュ テーブルのアドレス指定に「unsigned char[32]」結果型を使用する方法がわかりません。コンピューターの RAM よりもはるかに多くなります。ありがとうございました。

構造体をキーとしてunordered_mapを使用したいのですが、順序付けは必要ないためです。しかし、ハッシュ関数をすべて使用することはできません。

副次的な質問として..pplが順序付けされていないマップと順序付けられたマップを比較するとき、ハッシュ関数について話すことはありません。悪いハッシュ関数を使用すると、順序付けされていないマップがマップよりも遅くなりますか？（ハッシュ関数のみによる）

}

-edit- a、b、cは、値'a'、'b'、'c'、または'd'のみを持つことができ、nは約3から60まで変化します。