How to generate unique keys for a hashtable, and recycle deleted keys?

Question

For example, I need 10 objects stored in the hashmap.

So it creates keys 1,2,3,4,5

Then when I'm finished with '3', it deletes the whole entry and key for '3'. Making that key able to re-used for new object mappings -if I run over, via integer overflow or something.

Thoughts?

public static HashMap <GameKey, GameState> myMap  = new HashMap<GameKey, GameState>();
int i=0;

public void MapNewGameState(Gamestate gs){

myMap.add(i, gameStateA);
i++;
}


myMap.remove("3");
//Now I want to be sure that my MapNewGameState function is able to eventually map a new GameState to the key "3" later on,  

this is more a question about if HashMaps can be used in this way.

Answer 1

As I understand it you propose a key-pool where you get a key and if you don't need it anymore you put it back into the pool? If so this doesnt really make much sense since it adds complexity to your code but no other benefits (usually you pool something thats expensive to create or hold). And usually you want to recycle the value not the key?

To create truly (practical) unique keys use UUID.randomUUID(), whith this you don't have to worry about keys.

Answer 2

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.