有一个保证公平的变化一致性散列吗？

Question

我正在寻找类似一致散列的东西，但是保证分发结果尽可能公平(不仅仅是随机密钥的平均分布)--有这样的东西吗?如果是这样的话，我在哪里可以找到它？

编辑:在我的具体情况下，这组键是预先知道的(并且是“小的”)。确切地说，这些键将始终存在，并且必须在任何给定的时间点分配给每个节点。

Answer 1

听起来你在找最小完全散列。

Answer 2

不仅仅是随机密钥的平均

这并不是对一致散列所提供的保证的准确描述。首先，“平均”并不能捕捉到这样一个事实:在圆上随机放置大量虚拟节点和一个良好的哈希函数家族(例如，一个独立于日志的函数)，负载不平衡不太可能很大(我认为通常的不平衡应该是分配给特定机器的键数的平方根)。第二，只要密钥不依赖于随机选择的散列函数(不经意的对手)，密钥就不必是随机的。

因为您希望散列始终是公平的，随机化不会有帮助，因为RNG的结果可能与这一个没有区别。任何确定性算法都不能静态地为键分配节点首选项，而不存在不平衡的可能性，除非键是脱机已知的。

如果您有足够少的项目，您关心平方根不平衡，您可以做老式的有状态负载平衡。