java - 在多个工作线程中平衡负载的算法

Question

我有一个从 key1 到 keyn 的 HashMap，每个键的值是一个对象列表，每个对象上有不同数量的对象。

我也知道对象的总数(分布在各个键之间)。

我的目标是将数据加载到 T 个线程中，平均记录数为 K在每个线程中。

Constraint: The list of objects for a single key should go to single thread. (or cannot be splitted). However, we can group different list of records with different keys.

是否有任何经过验证的算法可以完成相同的任务？

例子:

Total size is = 1000
Request Map =

k1 -> 100
k2 -> 50
k3 -> 200
k4 -> 250
k5 -> 150
k6 -> 80
k7 -> 60
k8 -> 90
k9 -> 20

现在输出可以是:

T1 = k4 (250)
T2 = k3 + k2 (250)
T3 = k1 + k5 (250)
T4 = k6 + k7 + k8 + k9 (250)

Answer 1

这被称为 Bin Packing Problem其中 V = 总大小/线程数