多対1のマッピングを生成するためのアルゴリズム/ハッシュ関数

Question

整数ストリームからバッチを生成するために使用できるハッシュ関数を探しています。具体的には、多くのxiが1つのyjにマッピングされるように、整数または文字列のセット（例：Y）に、整数またはをセットまたはストリーム（たとえばX）からマッピングする必要があります。その際、最大nxiが1つのyjにマッピングされていることを確認したいと思います。ハッシュの場合と同様に、を指定してyを確実に見つける必要があります。

私はyjのほとんどは（XからYに非常にまばらなマッピングを回避するため）、それらにマッピングされxiのn数に近いを持っていることを確認したいと思います。私は考えることができる

一つの機能は商である：

int BATCH_SIZE = 3; 
public int map(int x) { 
    return x/BATCH_SIZE; 
} 

シーケンシャル整数のストリームのための、それはかなりうまく動作することができます。例えばストリーム1.9は

1 -> 0 
2 -> 0 
3 -> 1 
4 -> 1 
5 -> 1 
6 -> 2 
7 -> 2 
8 -> 2 
9 -> 3 

などにマップされます。しかし、順不同の大きな整数と小さなバッチサイズ（私の使用例）では、これはスーパースパースマッピングを生成する可能性があります（各バッチはたいてい1つの要素しか持たない）。

は、このようなマッピング（バッチ処理）

Answer 1

それはこれらの仮定の下で動作するように取得する方法はありませんを生成するための任意の標準的な方法があります。

ストリームに含まれるアイテムの数とそれらの配信を知る必要があります。アイテムをバッチに正確にマップする機能を緩和する必要があります。

ストリームからアイテムaとbがあるとします。 あなたはそれらを同じバッチにまとめようとしているのですか？あなたは2つ以上のバッチを満たすためにもっと多くのアイテムを取得しようとしているかどうか分からない限り、これに答えることはできません（バッチを別のバッチに入れることにした場合）。

（およそ）どれくらいの数があるか分かっている場合は、その分布を取り、それに基づいてバッチを構築できます。文字列ハッシュ（32ビット以上の一様分布）を持っているとします。 100万のバッチが必要な場合は、2^32 /（1.000.000/100）の間隔を生成し、バッチID（yj）として使用することができます。これは、batch_sizeのバッチを確実に取得することを保証するものではありませんが、およそbatch_sizeである必要があります。分布が均一でない場合は、より困難になりますが、まだ実行できます。

アイテムをバッチにマップする機能を緩和した場合、ストリームから出てくるすべてのバッチサイズをグループ化するだけです。スペースがあれば、スチームアイテムのマップをバッチに保存することができます。