I came across this old question because I have a use case in Mono Webassembly (where we have to code as though CPU speeds are back to 2000s levels) that warrants this, and was disappointed that no answer was actually given. So let me offer my solution that works for integer keys (and could be adapted to work with keys of any type by providing a parameterized way to generate a new key):
public class RecyclingDictionary<T> : Dictionary<int, T>
{
Queue<int> _freedKeys = new Queue<int>();
int _lastAssignedKey = -1;
public int Add(T item)
{
var key = GetNextKey();
base[key] = item;
return key;
}
public new void Remove(int key)
{
base.Remove(key);
_freedKeys.Enqueue(key);
}
private int GetNextKey()
{
if (_freedKeys.Count > 0)
{
int key = _freedKeys.Dequeue();
return key;
}
return ++_lastAssignedKey;
}
}
As for why one might want to do this, well, here are a couple reasons:
Guid
's are expensive to generate and store in memory (36 bytes when stringified vs. 4 for int
). They're also more expensive to hash and thus more expensive to use as Dictionary
keys.
- Integer keys are usually much faster than
string
keys, however, there is an article (which I sadly cannot find) from years ago that analyzed the efficiency of different key types and concluded that simple incrementing integers were actually a POOR key type. As I recall, it had to do with the way dictionaries bucket their entries for purposes of the binary search tree. Thus the impetus to recycle keys.