algorithm - 生成唯一 ID 的类/对象

Question

我正在使用 C#，但即使您不知道，也应该很容易理解这个问题。

这是我的问题:我有一些对象，我想将它们保存在类似哈希集的数据结构中，以便我可以根据 int ID 查找它们。这些对象具有可变属性，因此无法对它们进行哈希处理(我需要一些关于它们的常量来进行哈希处理，是吗？)。

我所做的是开发以下接口(interface):

public interface IUniqueIDCollection
{
    // Can return any int that hasn't been requested yet.
    public int RequestUniqueID();

    // Undos the requesting of an int
    public int ReleaseUniqueID(int uniqueID);
}

我最初的想法是只在 IUniqueIDCollection 中存储一个内部计数器，它会随着 ID 的请求而递增。然而，一旦 ID 被释放，我将不得不跟踪已被删除的范围或个人 ID。我认为后者会更好。但是，如果我使用一个计数器(或任何循环函数)来生成 ID，我将遇到一个问题，即必须检查连续请求的 ID 序列，这些 ID 序列在计数器回绕后未被释放。

启发式是这样的:假设一次最多请求 5,000 个 ID。但是，通常会请求 ID 然后发布。释放往往会在一定范围内发生——即可能会同时请求 100 个，然后在很短的时间间隔内释放所有 100 个。

我知道我可以使用 GUID 或其他东西而不是 int，但我想节省 ID 的空间/带宽/处理时间。

所以我的问题是:在我上面给出的接口(interface)中，请求和释放方法应该是什么样子的，就伪代码而言，给定启发式方法？

Answer 1

如果您确定已发布的 ID 可以安全地立即重复使用(即，不会有对旧 ID 的陈旧引用，如果新对象被分配了最近发布的 ID 会感到困惑)，您可以先使用已发布的ID。所以当一个 ID 被释放时，你把它放在队列的末尾。当请求新 ID 时，您使用队列中的第一个 ID。如果队列为空，则增加内部计数器并给出新号码。

这种实现的优点:

• 所有操作都是 O(1)。您永远不会迭代集合或范围。您只能在队列末尾插入、从队列前端移除或递增计数器。
• 内存占用应该相当低，因为您正试图尽快用完队列。
• 实现很简单。

缺点:

• 您将很快重复使用 ID，因此您不会使用整个索引范围来防止新对象使用与最近发布的对象相同的 ID。
• 您甚至无法通过查看 ID 来猜测对象的年龄。