c# - C＃辞書メモリ管理

Question

私には、Dictionary<string,int>1,000万以上の一意のキーが含まれる可能性があるがあります。辞書の機能を維持しながら、これに必要なメモリの量を削減しようとしています。

代わりに、文字列のハッシュを長く保存することを考えていました。これにより、アプリのメモリ使用量が許容可能な量（〜1.5ギガから〜.5ギガ）に減少しますが、私の方法についてはあまり気分が良くありません。これ。

long longKey=
BitConverter.ToInt64(cryptoTransformSHA1.ComputeHash(enc.GetBytes(strKey)), 0);

基本的に、これはSHA1ハッシュの終わりを切り取り、その最初のチャンクをlongに入れ、それをキーとして使用します。これは機能しますが、少なくとも私がテストしているデータについては、キーの衝突の可能性が高くなるため、これが非常に信頼できるソリューションであるとは思えません。

辞書のメモリフットプリントを削減する他の方法はありますか、それとも上記の方法は私が思っているほどひどいものではありませんか？

[編集]明確にするために、文字列を使用して辞書に含まれる値を検索する機能を維持する必要があります。実際の文字列を辞書に保存すると、多くのメモリが必要になります。代わりに私がしたいのはDictionary<long,int>、longが文字列のハッシュ関数の結果であるaを使用することです。

Answer 1

それで、私は最近似たようなことをしました、そして私のアプリケーションにかなり独特である特定の一連の理由のためにデータベースを使用しませんでした。実際、私はデータベースの使用をやめようとしました。GetHashCodeが3.5で大幅に改善されていることがわかりました。重要な注意点の1つは、GetHashCodeの結果を永続的に保存しないことです。決して。フレームワークのバージョン間で一貫性があることは保証されていません。

したがって、さまざまなハッシュ関数がデータに対して良くも悪くも機能する可能性があるため、実際にデータの分析を行う必要があります。また、速度も考慮する必要があります。原則として、ハッシュの数が数十億に達しても、暗号化ハッシュ関数は多くの衝突を起こしてはなりません。一意である必要があるものについては、通常、SHA1マネージドを使用します。一般に、基礎となるハッシュ関数がうまく機能している場合でも、CryptoAPIのパフォーマンスはひどいものです。

64ビットハッシュの場合、現在、両方とも32ビットハッシュであるLookup3とFNV1を一緒に使用しています。衝突が発生するためには、両方が衝突する必要がありますが、これは数学的にはあり得ないことであり、約1億回のハッシュで発生することはありません。両方のコードは、Webで公開されています。

それでもあなた自身の分析を行ってください。私のために働いたことはあなたのために働かないかもしれません。実際、私のオフィス内では、要件が異なるさまざまなアプリケーションが、実際にはさまざまなハッシュ関数またはハッシュ関数の組み合わせを使用しています。

証明されていないハッシュ関数は避けます。ハッシュ関数は、書くべきだと考える人と同じくらいたくさんあります。あなたの研究とテストテストテストを行います。

Answer 2

1,000 万件以上のレコードがあるため、非クラスター化インデックスを含むデータベースの使用を検討したことがありますか? データベースには、この種のことに対して、さらに多くのトリックが用意されています。

ハッシュは、定義上、どのアルゴリズムの下でも、衝突の可能性があります-特に大量の場合。シナリオによっては、私はこれに非常に注意を払います。

文字列を使用するとスペースがかかる場合がありますが、信頼性があります... x64を使用している場合、これは大きすぎる必要はありません(ただし、間違いなく「大きい」と見なされます;-p)

Answer 3

ちなみに、暗号化ハッシュ/ハッシュ関数は辞書には非常に悪いです。彼らは大きくて遅いです。1つの問題（サイズ）を解決することで、別のより深刻な問題が発生するだけです。関数は入力を均等に拡散しなくなり、衝突のないアドレス指定に近づくための適切なハッシュの最も重要な単一のプロパティが破壊されます（あなたは自分自身に気づいたようです）。

/編集：アンドリューが指摘したように、それが意図された使用法でGetHashCodeあるため、この問題の解決策です。そして、本当の辞書のように、衝突を回避する必要があります。そのための最良のスキームの1つは、ダブルハッシュです。残念ながら、100％信頼できる唯一の方法は、実際に元の値を保存することです。そうでなければ、あなたは無限の圧縮を作成したでしょう、それは私たちが存在することができないことを知っています。

Answer 4

GetHashCode()文字列のハッシュを取得するためだけに使用してみませんか？

Answer 5

私が過去に使用したハッシュテーブルの実装では、ハッシュによってバケットが表示されます。これは、同じハッシュを持つ他のオブジェクトのリンクリストであることがよくあります。ハッシュは一意ではありませんが、データを非常に管理しやすいリスト（2〜3の長さの場合もあります）に分割して、実際のアイテムを検索できるようにするのに十分です。

優れたハッシュの鍵は、その一意性ではなく、速度と分散機能です...可能な限り均等に分散する必要があります。

Answer 6

SQLite を入手してください。あなたはそれを打ち負かす可能性は低く、たとえ勝ったとしても、おそらく時間/労力/複雑さに見合う価値はないでしょう.

SQLite。