2

文字列の非常に特殊なケースのハッシュコードを作成する最も効果的な方法を探しています。

整数に変換できる文字列があり、それらは 1 から 10,000 まで変化し、1 から 600 の範囲に非常に集中しています。

私の質問は、コレクションからアイテムを取得してそのハッシュコードを実装するパフォーマンスの観点から、最も効果的な方法は何かということです。

私が考えているのは：

  • 文字列を整数に変換し、直接アクセス テーブル (10.000 行の配列) を使用することができます。

  • 文字列を文字列として使用し、そのハッシュコードを取得できます (整数に変換する必要はありませんが、衝突に関して文字列のハッシュコードがどれほど効果的かはわかりません)

他のアイデアは大歓迎です。

どうもありがとう

皆様、早速のご回答ありがとうございます。...

これに追加するのを忘れた別の情報があります。これで私の最終目標をあなたに知らせれば、これが明確になると思います-ハッシュテーブルさえ必要ないかもしれません!!!

不変の辞書に対してストリームを検証したいだけです。特定のタグがメッセージに存在するかどうかを確認したい。

複数のタグ=値のペアを含む文字列を受け取ります。アプリでタグを処理する必要があるかどうかを確認したい。

4

4 に答える 4

1

トライ (http://en.wikipedia.org/wiki/Trie) または基数ツリー (http://en.wikipedia.org/wiki/Radix_tree) を検討することをお勧めします。文字列を整数に解析したり、ハッシュ コードを計算したりする必要はありません。ひもを歩くように、あなたは木を歩いています。

編集：

文字列のハッシュ コードの計算と文字列からの整数の解析の両方で、文字列全体を調べ、その値を特定のデータ構造へのルックアップとして使用します。他の手法では、データ構造をトラバースしながら文字列を同時に検査する必要があります。これは、「他のアイデア」を求めた投稿者にとって価値があるかもしれません。

于 2012-05-22T20:34:48.673 に答える
1

多くのコレクション (HashMap など) では、貧弱なハッシュコード アルゴリズムを支援するために、補助的な「再ハッシュ」メソッドが既に適用されています。たとえば、 のコース コードを参照しHashMap.hash()ます。また、文字列は非常に一般的なキーであるため、String.hashCode() が高度に最適化されていることを確認できます。だから、hashCodes の間で多くの衝突に気付かない限り、私は標準コードを使用します。

0..600 の文字列を HashSet に入れて何が起こったかを確認しようとしましたが、競合が発生したエントリの数を確認するのはかなり面倒です。自分で探してください！本当に気にするなら、ソースコードを HashMap から自分のクラスにコピーし、エントリにアクセスできるように編集して (私が見ている Java 6 ソースコードではtransient Entry[] table、YMMV になります)、メソッドを追加します。衝突を数えます。

于 2012-05-22T21:02:36.167 に答える
0

有効な値の範囲が限られているint[10000]場合は、提案したようにコレクションを表現してみませんか? at の値array[x]は、発生する回数ですx。

文字列が 10 進整数として表されている場合、それらを文字列に解析するには、5 回の反復ループ (最大 5 桁) と 2 回の加算と減算が必要です。つまり、信じられないほど高速です。要素の挿入は事実上 O(1) であり、検索は O(1) です。必要なメモリは約 40kb (int ごとに 4 バイト) です。

1 つの問題は、挿入順序が保持されないことです。多分あなたは気にしません。

hashcode()おそらく、ハッシュコードをキャッシュして、最後に呼び出されてからコレクションが変更された場合にのみ更新することを考えることができます。Java コレクションでのハッシュのキャッシングを参照してください。

于 2012-05-22T20:59:41.100 に答える
0

«アプリケーションのホットスポットであり、それを証明できる場合にのみこれを行うという免責事項を挿入»

整数値自体は完全なハッシュ関数になり、衝突は発生しません。ただし、このアプローチには 2 つの問題があります。

  1. HashMapカスタム ハッシュ関数を指定することはできません。そのため、独自に実装するHashMapか、ラッパー オブジェクトを使用する必要があります。
  2. HashMapモジュロ演算の代わりにビット単位の and を使用してバケットを見つけます。これは単なるマスクであるため、明らかにビットが破棄されます。java.util.HashMap.hash(int)はこれを補おうとしていますが、これはあまり成功していないという主張を見てきました。再び、独自の の実装に戻りますHashMap。

この時点で、整数値をハッシュ関数として使用しているためHashMap、文字列の代わりに整数値をキーとして使用しないのはなぜですか? これを本当に最適化したい場合は、キーintの代わりに使用するハッシュ マップを作成するか、 troveのTIntObjectHashMapを使用できます。Integer

優れたハッシュ関数を見つけることに本当に興味がある場合は、 Hashing in Smalltalkをお勧めします。著者が Java について暴言を吐く半ダースのページは無視してください (免責事項: 私は著者を知っています)。

于 2012-05-22T21:13:03.710 に答える