Maintaining a key index steady

Question

I have an object used as index.

const index= {};

I use a counter to get a new key:

var key=0; 
function getNewKey(){
   return ++key;
}

Then I can add object to index:

function addObject(object){
    const key= getNewKey();
    index[key]= object;
    return key;
}

But, like that, if I remove objects in index, and add new ones, there will be holes, and the key may become big.

So I would like to know if there was patterns for this kind of problem, which often appears.

You can use an array for this. why do you want to use a plain object since the keys are indexed numbers? — Rajaprabhu Aravindasamy, Apr 10 '16 at 16:25
There will be no holes if you use `delete index[key]` to remove objects. And what is the problem with larger keys? — user0815, Apr 10 '16 at 16:34
problems could be an integer overflow, but before that I think that it is preferable to maintain a reasonable key size. If there is a lots of adds/removes, the key will increase fast. — Gaël Barbin, Apr 10 '16 at 16:38

score 1 · Accepted Answer · edited May 23 '17 at 12:13

You could use an array as your index.

const index= [];

Removing an object can then be done by setting the corresponding array entry to undefined.

function removeObject(key) {
    index[key] = undefined;
    if( key == index.length - 1 ) index.pop();
}

A new object is placed in the next free slot of the array, which can be found with the indexOf method.

function addObject(object) {
    const pos = index.indexOf(undefined)
    const key = pos == -1 ? index.length : pos;
    index[key]= object;
    return key;
}

With this approach the key size will be minimal. Since array implementations are usually sparse as discussed here, also the memory usage will be as small as possible.

Maintaining a key index steady

1 Answers1