Hi!
I have a program where I need to search for the lowest free key (non existent) in a HashMap to create a new key/value. I'm using Integers for the keys.
Right now, I am using a loop to search for the key, it goes like this:
for (int i = 0; ; i++){
if (!(myMap.containsKey(new Integer(i)))){
myMap.put(new Integer(i), value);
break;
}
}
Performance is the most important thing. Any suggestion?
If you are interested in "fast" to that degree then I wouldn't use a solution that required looking at many keys. I would relax the requirement for getting the lowest free key for a start. Then I would wrap that map in an object that keeps track of the highest key used so far, and when asked for the next free key, return that number plus one. No searching required at all.
If you always add element with such index, index is equal to number of elements. If you start with map and ever add elements using this rule, you can once collect unoccupied intervals (for O(n)) and get elements (for O(1)) after that. If your map is ever randomly mixed, you need to keep search tree, which would take O(log(n)) per operation.
After rereading this...
Felipe:
If you never delete elements (you didn't say), then if you always wants to add with the lowest free index, why not just use a List instead of a Map? Add values to the end (no need to know what the index was). And, to get index 5, just use 'get(5)'.
Can you explain more what you are trying to achieve?
I am sorry, I didn磘 explain a lot of details about my algorithm. Of course I am going to delete some keys in random order. After thinking about this, I will use a TreeMap for storing the previously deleted keys.
Something like this (pseudo-code):
if (TreeMapWithKeys.isEmpty()) {
if (HashMap.isEmpty()) {
key = 0;
} else {
key = HashMap.lastKey + 1;
} else {
key = TreeMapWithKeys.lowestKey;
TreeMapWithKeys.remove(TreeMapWithKeys.lowestKey);
}
I think this could work so much better. I hope is clear now. Thanks for you help guys.
Well, I checked the code I wrote above, and found out some mistakes...
1) I can磘 use first or last key with HashMap (Now that I think about is kinda obvious).
2) I made a mistake with the last else, it should be after the closing { of the main if.
So, finally, I implemented the algorithm with 2 TreeMaps, and it磗 working very nicely. And the code I wrote above, should go like this:
int key;
if (treeWithUnusedKeys.isEmpty()) {
if (tree.isEmpty()) {
key = 0;
} else {
key = ((Integer)tree.lastKey()).intValue() + 1;
}
} else {
key = ((Integer)treeWithUnusedKeys.firstKey()).intValue();
treeWithUnusedKeys.remove(treeWithUnusedKeys.firstKey());
}
tree.put(new Integer(key), value);