class/object生成唯一的id

Question

我正在使用C#,但即使你不知道它,也应该很容易理解这个问题.

这是我的问题:我有一些对象,我想保留在类似hashset的数据结构中,以便我可以根据intID 查找它们.这些对象具有可变属性,因此散列它们不是一个选项(我需要一些关于它们的常量哈希,是吗？).

我所做的是开发以下界面:

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序列.

启发式是这样的:假设一次最多可以请求5,000个ID.但是,ID经常要求然后发布.释放将倾向于在范围内发生 - 即可能一次请求100,然后所有100将在短时间间隔内释放.

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

所以我的问题是:考虑到启发式方法,请求和发布方法在上面给出的接口中,伪代码方面应该是什么样的？

Answer 1

如果您确定已发布的ID可以安全地立即重复使用(即,如果为新对象分配了最近发布的ID,则不会过时引用旧ID,如果新对象被分配了最近发布的ID,则会混淆)发布ID的第一个.因此,当ID被释放时,您将其放在队列的末尾.请求新ID时,使用队列中的第一个ID.如果队列为空,则递增内部计数器并给出新编号.

这种实施的优点:

• 所有操作都是O(1).你永远不会迭代一个集合或范围.您只需在队列末尾插入,从队列前面删除,或增加计数器.
• 内存占用量应该相当低,因为您尝试尽快使用队列.
• 实施很简单.

缺点:

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