山車を使用するハッシュテーブル/辞書/

Question

を倍増誰もが彼らが何であるかを知っている

など、私は辞書、ハッシュテーブルに似た他のデータ構造について、どこかで読んではなく、int型を使用して、彼らはフロート/倍精度を使用していましたか？

Answer 1

ハッシュのキーとして浮動小数点数/倍数を使用することを意味するのは簡単です。たとえば、.NETでは、それはちょうどDictionary<double,MyValueType>を使用しています。

あなたはハッシュを持っていることについて話している場合は、

技術的には....代わりにint型の二重をオフに基づいて、あなたはあなたの内部ハッシュとして任意の要素を持つことができます。通常、これはintまたはlongを使用して行われます。これらは高速で、ハッシュアルゴリズムは計算が簡単です。

しかし、ハッシュは実際にはちょうどBitArrayであり、何も問題なく動作します。潜在的により大きいハッシュ値のセットを許可する以外に、これをintまたはlong以外のものにすることは、あまり利点がありません（つまり、あなたのハッシュに8バイト以上のタイプに行く場合）。

Answer 2

あなたの質問履歴はあなたが.Netを使用していることを示しているので、その文脈で回答します。

あなたが認識して入力している辞書をしたい場合は、あなたがそのように、あなたはブラインド型である辞書をしたい場合はSystem.Collections.Generic.Dictionary<T, U>http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

を使用し、それがキーまたは値のために山車やdouble型を使用するように指定することができるようにあなたはキーと値のために浮動小数点数と2倍を使用することができますSystem.Collections.HashTablehttp://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx

Answer 3

あなたはキーを意味しますか？それは私をトリッキーなものにします。

これらを任意のキーとして使用している場合は、整数よりも優れていません。

浮動小数点値を計算し、それをハッシュテーブルで何か見るために使用すると、非常に危険です。浮動小数点数は無限の精度を持たず、2つのわずかに異なる方法で同じものを計算すると、結果に非常に小さな差が生じることがあります。ハッシュキーは毎回まったく同じものを得ることに頼っているので、常に丸めるように注意しなければならず、まったく同じ方法で丸めなければなりません。ところで、これは聞こえるよりも厄介です。

浮動小数点ハッシュではどうしますか？

Answer 4

ハッシュアルゴリズムは一般に、より大きな入力から小さな出力を生成する単なる関数です。良いハッシュ関数は、入力のわずかな変化に対する出力の大きな変化と、いくつかの入力に対して可能なすべての出力値を生成するという保証のような興味深い特性を持っています。

整数値ではなく浮動小数点値を出力する単純な多項式型のハッシュ関数を記述するのは難しくありませんが、生成されたハッシュ関数が目的のプロパティを持つことを保証することは難しいです。使用される特定の浮動小数点表現。

ハッシュ関数がほとんど常に整数演算で実装されている理由の少なくとも一部は、整数計算に関するさまざまなプロパティが浮動小数点計算で同じことを行うよりも簡単であることを証明しているためです。

モジュロ（別の素数）のいくつか（いくつかの素因数の合計）は、必然的に、入力によってはすべての可能な出力を生成する必要があることを証明することはかなり簡単です。浮動小数点数の集まりを使った計算で同じことをすることは難題です。

浮動小数点値を破損することなく格納して送信することの相対的な難しさを加えてください。それは価値がありません。