Erhalten Sie eine neue ID in einer deterministischen Weise

Question

Ich habe eine IImmutableDictionary<int, MyType> in C#. Während der Ausführung meines Programms, würde Ich mag MyType Instanzen auf einigen Befehlen basierend hinzuzufügen und zu entfernen:

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

    // etc... 
} 

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

    // etc... 
} 

Wenn ein MyType hinzugefügt wird, würde Ich mag einen frischen int Schlüssel generieren, die nicht bereits im Wörterbuch vorhanden ist.

Ich nehme an, dass ich nie ausgehen werde int s, weil Schlüssel später entfernt und wiederverwendet werden können.

Der wichtigste Haken ist, dass ich möchte, dass der Prozess deterministisch ist. Für einen gegebenen Strom von ICommand s muss der Code dasselbe ausführen (und die gleichen Schlüssel erzeugen!) Auf verschiedenen Maschinen.

Was ist ein robuster, wartbarer und effizienter Ansatz zur Erreichung des Schlüsselgenerierungsschritts?

---

Zum Beispiel kann eine langsame Annäherung wäre: ab int.MinValue, zu Fuß nach oben, bis eine neue ID gefunden wird.

Answer 1

Wenn Sie wissen, dass Sie nicht mehr als das Hinzufügen entfernen, können Sie versuchen, alle Lücken in einer Warteschlange zu speichern und den Schlüssel basierend darauf zu bestimmen, ob die Warteschlange leer ist oder nicht. Ihr Wörterbuch wird den Schlüssel automatisch inkrementieren, wenn keine Löcher vorhanden sind, und er wird ausgefüllt, wenn Löcher vorhanden sind.

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); 
    } 
}