以确定性方式获取新 ID

Question

我在 C# 中有一个 IImmutableDictionary<int, MyType>。在我的程序执行期间，我想根据一些命令添加和删除 MyType 个实例：

public sealed class AddMyTypeCommand : ICommand
{
    public readonly MyType myTypeToAdd;

    // etc... 
}

public sealed class RemoveMyTypeCommand : ICommand
{
    public readonly int keyToRemove;

    // etc... 
}

添加 MyType 时，我想生成字典中不存在的新 int 键。

我假设我永远不会运行出 int 次，因为密钥可能会被删除并在以后重新使用。

主要问题是我希望过程是确定性的。对于给定的 ICommand 流，代码必须在不同的机器上执行相同的（并生成相同的密钥！）。

实现密钥生成步骤的稳健、可维护且高效的方法是什么？

例如，一个缓慢的方法是：从int.MinValue开始，向上走直到找到一个新的id。

Answer 1

如果你知道你不会删除比添加更多的东西，你可以尝试将所有空洞存储在一个队列中，并根据队列是否为空来确定键。所以你的字典会在没有空洞的情况下自动增加键值，如果有空洞则回填。

class ImmutableDictionary<T>
{
    private readonly Dictionary<int, T> _dict = new Dictionary<int, T>();
    private readonly Queue<int> _holes = new Queue<int>();
    private int _nextInt = 0; //what is next integer to assign, I'm starting at 0, but can be int.MinValue
    private int AssignKey()
    {
        //if we have a hole, use that as the next key. Otherwise use the largest value we haven't assigned yet, and then increment that value by 1
        return _holes.Count != 0 ? _holes.Dequeue() : _nextInt++;
    }

    public void Add(T input)
    {
        _dict.Add(AssignKey(), input);
    }

    public void Remove(int key)
    {
        if (_dict.Remove(key)) //if a remove is successful, we should add a hole
        //you can extend the logic here to not add a hole if you are removing something equal to _nextInt - 1.
            _holes.Enqueue(key);
    }
}

以确定性方式获取新 ID

Get a fresh id in a deterministic manner

c#

deterministic