6

パフォーマンス上の理由から、文字列で識別されるオブジェクトのセットをグループに分割する必要があります。オブジェクトは、数字または識別子の一部をドットで区切る接頭辞（修飾）形式の文字列のいずれかで識別できます。

12
323
12343
2345233
123123131
ns1:my.label.one
ns1:my.label.two
ns1:my.label.three
ns1:system.text.one
ns2:edit.box.grey
ns2:edit.box.black
ns2:edit.box.mixed

数値識別子は1から数百万です。テキスト識別子は、同じ名前空間プレフィックス（ns1 ::）と同じパスプレフィックス（edit.box。）で始まるものが非常に多い可能性があります。

この目的に最適なハッシュ関数は何ですか？オブジェクト識別子の統計に基づいて、バケットのサイズを何らかの形で予測できればよいでしょう。いくつかの統計情報に基づいて優れたハッシュ関数を構築するための優れた記事はありますか？

このような識別子は数百万ありますが、目的はハッシュ関数に基づいて1〜2千のグループに分割することです。

4

3 に答える 3

3

2 つの優れたハッシュ関数は、両方とも同じ値の空間にマップでき、一般にそれらを組み合わせた結果として新しい問題が発生することはありません。

したがって、ハッシュ関数は次のようになります。

if it's an integer value:
    return int_hash(integer value)
return string_hash(string value)

N を法とする特定の値の周りに整数の塊がない限り (N はバケットの可能な数)、int_hashその入力を返すことができます。

文字列ハッシュの選択は新しい問題ではありません。「djb2」 ( http://www.cse.yorku.ca/~oz/hash.html ) または同様のものを試してください。

一般的な接頭辞を考慮してハッシュ関数を変更してもあまり意味がないと思います。ハッシュ関数が最初から適切である場合、一般的なプレフィックスがハッシュ値の塊を作成する可能性はほとんどありません。

これを行い、ハッシュのパフォーマンスが予想外に悪くならず、数百万のハッシュ値を数千のバケットに入れると、バケットの母集団は平均 (数百万÷数千) と分散で正規分布します。 1/12 (数千)^2

バケットあたり平均 1500 エントリの場合、標準偏差は約 430 になります。正規分布の 95% は平均の 2 標準偏差内にあるため、バケットの 95% には 640 ～ 2360 エントリが含まれます。私の合計が間違っていました。それは十分ですか、それともバケットをより類似したサイズにする必要がありますか?

于 2009-12-14T17:17:12.333 に答える
0

おそらく安全に使用してsha1、必要なサイズに切り詰めることができます。

非常に効率的ではありませんが、ハッシュ関数がボトルネックにならないのでしょうか?

于 2009-12-14T16:42:54.367 に答える
0

CRC16 はこれらの文字列で使用するのに妥当なハッシュであり、グループは 1 ～ 2,000 を超えるべきではないと思います。

これにより、ハッシュ テーブルは約 1MB + アイテムの数 * 4 バイトになるはずです。したがって、50MB について話していると、実際のデータもすべて格納されます。これは非常に小さい方がよいでしょう。

于 2009-12-14T16:45:43.733 に答える