java - 生成多对一映射的算法/哈希函数

Question

我正在寻找可用于从整数流中生成批处理的哈希函数。具体来说，我想将整数 xi 从一个集合或流(例如 X)映射到另一组整数或字符串(例如 Y)，例如许多 xi 映射到一个 yj。在这样做的同时，我想确保最多有 n xi 映射到单个 yj。与散列一样，我需要能够在给定 x 的情况下可靠地找到 y。

我想确保大多数 yj 有接近 n 数量的 xi 映射到它们(以避免非常稀疏的映射X 到 Y)。

我能想到的一个函数是商:

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 万件元素并且想要 100 件的批处理，则可以生成 2^32/(1.000.000/100) 的间隔并将其用作批处理 ID (yj)。这并不能保证您得到的批处理正好是 batch_size，但它们应该大约是 batch_size。如果分布不均匀，事情会更困难，但仍然可以做到。

如果您放宽将项目映射到批处理的能力，那么只需在它们从流中出来时将它们按每个 batch_size 分组即可。如果你有空间，你可以保留一个 steam 项目的 map 来批处理。