問題タブ [string-hashing]

OK、次の要件を満たすハッシュ関数が必要です。これは、同じ論理構造の一部であるが、ファイル システムの異なる物理領域に格納されているディレクトリをリンクできるようにすることを目的としています。

Java で実装する必要があります。実行セッション全体で一貫している必要があり、long を返すことができます。

ディレクトリ名/文字列をハッシュします。これは、と がそうであるように、"somefolder1"と"somefolder2"が異なるハッシュを返すよう"JJK"に動作するはず"JJL"です。また、衝突が発生する可能性が高い時期についても考えてみたいと思います。

助言がありますか？

ありがとう

次のような文字列のハッシュキーを生成するためにdjb2アルゴリズムを使用しています

これで、すべてのループで 2 つの大きな数の乗算が行われます。しばらくすると、文字列の 5 番目の文字の 4 番目の文字で、ハッシュ値が巨大になるため、オーバーフローが発生します。

ハッシュ値がオーバーフローせず、ハッシュも正しく行われるようにリファクタリングする正しい方法は何ですか?

メッセージを30文字の文字列にハッシュする必要があります。この使用法に最適で最も安全なハッシュ関数は何ですか？

2 つの文字列が同一かどうかをできるだけ早く確認しようとしています。文字列全体を比較せずに、ハッシュの衝突から身を守ることはできますか?

文字列をキーとするアイテムのキャッシュがあります。文字列のハッシュ、文字列の長さ、および文字列自体を保存します。(現在、djb2を使用してハッシュを生成しています。)

入力文字列がキャッシュ内のアイテムと一致するかどうかを確認するために、入力のハッシュを計算し、それを格納されているハッシュと比較します。それが一致する場合、入力の長さ (ハッシュ計算の副作用として取得したもの) を格納されている長さと比較します。最後に、一致する場合は、入力と格納された文字列の完全な文字列比較を行います。

その完全な文字列比較を行う必要がありますか? たとえば、同じ長さの 2 つの文字列が同じハッシュを生成しないことを数学的に保証できる文字列ハッシュ アルゴリズムはありますか? そうでない場合、アルゴリズムは、最初の N 文字のいずれかが異なる場合、同じ長さの 2 つの異なる文字列が異なるハッシュ コードを生成することを保証できますか?

基本的に、文字列が異なる場合は O(1) のパフォーマンスを提供するが、一致する場合は O(n) のパフォーマンスよりも優れた文字列比較スキームは、私が現在行っていることよりも改善されます。

ハッシュされたファイル名の最後の文字を使用して、キャッシュ内の「負荷分散」を改善することを提案しているのを見てきました-これは、たとえばnginxが行うことです（プロキシキャッシュモジュール）。最後の文字が使用される理由を誰か説明できますか?

編集：

例えば：

十分にランダムに「見える」。

キーが修正され（初期化中に修正され）、ルックアップが高速になるマップを探しています。後で要素を追加/更新することはサポートされない場合があります。キーのリストを検索し、後で検索するのが高速になるように関数を定式化するアルゴリズムはありますか？私の場合、キーは文字列です。

アップデート：

キーはコンパイル時に不明です。ただし、アプリケーションの初期化時に。後でそれ以上の挿入はありませんが、たくさんのルックアップがあります。したがって、ルックアップを最適化する必要があります。

ハッシュ方式はたくさんありますが、8096ビット長のビットハッシュを作成したいと思います。これを達成することは可能ですか？

たとえば、「House」と入力すると、次のような文字列が表示されます。

どうすればこれを達成できますか（C＃4.0を使用しても問題ありません）？

なぜそのようなものが必要なのか疑問に思われる場合は、署名ファイルとベクトル空間モデルを比較するために必要です。

ハッシュテーブルを使用してさまざまな単語を格納するCプログラムを作成しようとしていますが、助けが必要です。

まず、格納する必要がある単語の数に最も近い素数のサイズのハッシュ テーブルを作成し、ハッシュ関数を使用して各単語のアドレスを見つけます。文字を追加する最も単純な関数から始めたところ、88% の衝突が発生しました。次に、この関数を試してみたところ、どのように変更しても、衝突が 35% を下回らないことがわかりました。今、私は使用しています

これは私が思いついた単なるランダム関数ですが、最高の結果が得られます - 約 35% の衝突です。

過去数時間、ハッシュ関数に関する記事を読んでいて、djb2 などのいくつかの単純なものを使用しようとしましたが、それらのすべてでさらに悪い結果が得られました (djb2 は 37% の衝突を引き起こしました。さらに悪いことに、私は悪いことよりも良いことを期待していました) また、murmur2 などの他のより複雑なものの使用方法もわかりません。パラメーター (key、len) がわからないためです。 、種子）彼らは摂取します。

djb2 を使用していても 35% 以上の衝突が発生するのは正常ですか、それとも何か間違っていますか? キー、len、およびシード値は何ですか?

同じ都市の人を検索できるようにする機能に取り組んでいます。

私は地理位置情報の使用を楽しみにしていないので、ユーザーに都市を入力してもらいました。そのため、人々がお互いを見つけるには、同じ都市名を入力する必要があります。

現在、大文字と小文字を区別するデータベースを使用しているため、文字列が一致する必要があるため、次のような単純化手順を考えていました。

次に私が楽しみにしていることは、タイプミスとして「new yprk」と入力した人々が、それでもお互いを見つけられるようにすることです。

私は車輪を再発明したくないので、わずかに異なる単語が同じものとしてカウントされるように、そのような単語を「ハッシュ」することについて知っているスクリプトはありますか?

前もって感謝します。