1000億のURLにインデックスを付け、さらに、機能のないものは、衝突なしで完璧に動作します。 URLは一意の文字列なので、私は任意の文字列ハッシュ関数を想定しています。 MD5のように良いですが、専門家からの入力が必要です。何が完全なハッシュfnになりますか？何十億というURLの最小サイズのハッシュ
また、URLセット（今のところDBテーブル）をハッシュで検索したいので、明らかに短いハッシュは検索時間とスペースで効率的です。
固定ハッシュ長を指定できますか？私たちは、C＃.NET 4.0
を使用している
はあなたのDBテーブルを移動するための方法ではありませんか？これはハッシュ関数の多くの要件です。ほとんどのハッシュ関数では、ハッシュの長さを設定することはできません。また、ハッシュを完全にする必要があると、それをさらに絞り込むことができます。これらのすべての要件が必要ですか？おそらく、はるかに単純な解決法も同様に機能します。
これをディスクから読み取っていますか？ （1000億のURL、ドメインのURL長4、 ".com" + "/" + 4 = URLあたりの12バイト= 1.09 TiB - 4は非常に控えめな見積もりです） Bツリー（B +木などの派生物）などのディスクフレンドリーな構造を調べたい場合 - これらのデータ構造は効率的（理論的にはlog（n）ですが、いくつかの一般的なケースではハッシュテーブルに打ち勝つことができます） 、除去、挿入。データベースは通常、ハッシュに対するインデックスに対してこれらを使用します。これは、パフォーマンスに関してヒントを与えるはずです。 （そして私の最初の質問に私を戻します：あなたはあなたのDBテーブルが行く方法ではないと確信していますか？）
ハッシュを使用すると、衝突のあるものでも動作します。 SHA256のようなものは、計算に比較的高価ですが、受け入れられるほど低い衝突率を持ちます。 （私はそれがとても低いと思いますが、あなたは雷に襲われる可能性がより高いです。複数回：衝突の恐れがなく、SHA256ハッシュの半分以下のビット数を持つUUIDを使用します。）SHA256のCPUコストあなたがディスクアクセスでそれに追いつくつもりならば、問題ではないかもしれません。
（も？：URLのあなたのDBテーブルが速くその場で検索できるように適切にインデックスされる）
thnx 4貴重なアドバイス。さて、私たちのプロジェクトが始まったので、私のための迅速なストレージ候補はDBです。私は、高速検索のためにフィールド（ここではハッシュ）上にインデックスを作成する必要があると仮定し、残りの作業はDBによって行われます。また、編集では、研究で言及されているURLの平均長は〜100バイトです。そのようなURLだけで10 TBに達すると、他の付随するデータを残します。とにかく私たちのためにデータストレージ全体の問題を引き起こします。しかし、あなたが言ったように、この問題に来るのはSHA256です。 –
根本的にthats私は私の上記のコメントにしていきたいと思っていた点。 256ビットの出力空間と良好なアルゴは、まれな衝突を確実にするはずです。まあ、私は珍しい衝突で暮らすことができます（避けられない場合）、私は誰も衝突のないことを保証しないと仮定します。だから、その100バイトの平均URLの32バイトのハッシュのような。これはimpです。私が128ビットまたは256ビットにすることを決定しました。私たちが1000億ドルで規模を上げることができれば、さらに高い目標を設定します。したがって、将来的な解決策と緩和の開始は、今やいくらか考えられる必要があります。 –
URLデータセットをご利用いただき、サポートするハードウェア（ストレージ）がある場合は、データベースを設定してください。 URL以外のデータベースを取得して実行し、インデックスを設定しても時間がかかりません。ほとんどの時間はデータのインポートに費やされると思います。小さなセットアップから始めて、それを稼働させてから、実世界を投げ込んでストレステストをしてください。理論は一日中話し合うことができますが、そこに出て手を汚すことはあなたに良い気持ちを与えるはずです。特定のソフトウェアの特定の問題は、より良いのSOの質問です。 – Thanatos
私はほかに...千億URLに対して、完璧なハッシュ関数が何をしたい、おそらくないと言うあえてこれらのURLがすべてユニークな文字列であるからといって、MD5の合計がユニークであることを意味するわけではありません：* "[...] MD5は衝突耐性ではないことが示されています" *（[MD5のWikipedia記事]（http://en.wikipedia.org/wiki/MD5））。 – stakx
@stakxなぜ完全なハッシュfnと言うのですか？私たちが狙っているものは何ですか？私たちの選択は何ですか？私はGoogleと他の大きなURLのインデックスは、何兆ものURLにインデックスを使用することを願っています。彼らはそれをどうやって行うのですか？ –
完璧なハッシュは前もって計算する必要があるため、ここでは適切ではないようです。その後、1000億のURLのうち1つだけが変更された場合は、それらが一意であることを保証するためにすべてのハッシュを再計算する必要があります。したがって、私はこれがGoogleなどの方法ではないと仮定します。 URLインデックスを維持する。完全なハッシュ関数、IIRCは、より小さく、変更されない値のセットに適しています。 – stakx