uncategorized

Observations on Maps

I have been investigating Maps to better understand their advantages over arrays and hashes.

A map is essentially a collection of key-value pairs, differing from traditional hashes in that the key can be of any type, not just a string.

##Some gottcha’s when using objects as keys

It is clear that under the hood a pointer to the object is the key.
Using a string as the key when we issue the second “set” we just replace the value.

1
var mStringMap=new Map();
mStringMap.set("foo",1);
console.log(mStringMap.get("foo")) //1
mStringMap.set("foo",2);
console.log(mStringMap.size); // 1
console.log(mStringMap.get("foo")) // 2

If we now use a string object as the key the behavior is different;

1
var mStringObjectMap=new Map();
    mStringObjectMap.set(new String("foo"),1);
    console.log(mStringObjectMap.get("foo")); //undefined
    mStringObjectMap.set(new String("foo"),2);
    console.log(mStringObjectMap.size); // 2
    console.log(mStringObjectMap.get("foo")) // undefined
    mStringObjectMap.forEach(function(value,key){
        console.log(value,key);
     });

The forEach loop logs:

1
1 [String: 'foo']
2 [String: 'foo']

This is, of course because the objects created with new String(“foo”) point to different areas of memory.
If we set the key to a variable we then get results similar to using a string;

1
var mStringObjectVarMap=new Map();
    var theKey=new String("foo");
    mStringObjectVarMap.set(theKey,1);
    console.log(mStringObjectVarMap.get(theKey)) //1
    mStringObjectVarMap.set(theKey,2);
    console.log(mStringObjectVarMap.size); // 1
    console.log(mStringObjectVarMap.get(theKey)) // 2
    mStringObjectVarMap.forEach(function(value,key){
        console.log(value,key);
     });

The forEach loop now logs:

1
2 [String: 'foo']

You see the same behavior if you use an object literal as the key.
Calling ‘set’ with a second literal having the same properties still
looks like a different key to Map.

##Iterating over a map

One very nice feature of maps is the ability to iterate the keys in insertion order.
That isn’t possible for an object literal.

We all know that when iterating over an object you should never delelete an element because the
“forEach” or “for” counters will get out of synch yielding incorrect results. With a map you can safely delete the
current key. You cannot, of course, add new keys.

Lets look at the use case of deleting all the odd numbers in a list:

1
var a = [1,1,2,3,4,5,5];
console.log(a); //[ 1, 1, 2, 3, 4, 5, 5 ]
var m=new Map();
a.forEach(function(item){
    m.set(new String(item),void(0));
});
console.log(m.size); //7  if you use item instead of new String(item) you would get 5.
//delete odd values using for each
a.forEach(function(value,index){
    if((value %2)===1){
        a.splice(index,1);
    }
});
console.log(a); //[ 1, 2, 4, 5 ]  Fails because you altered array
//using loop
a = [1,1,2,3,4,5,5];
for(var i=0;i< a.length;i++){
    if((a[i]%2)===1){
        a.splice(i,1);
    }
}
console.log(a); //[ 1, 2, 4, 5 ] fails because you altered array
//with map
m.forEach(function(value,key){
    if((key%2)===1){
        m.delete(key);
        //m.set(key,void(0))
    }
});
console.log("Size of map %d",m.size); //Size of map 2
m.forEach(function(value,key){
    console.log(key);
});

The last forEach yields the correct results:

1
[String: '2']
[String: '4']

If you try to add a key in the loop (uncomment the line m.set(key,void(0))
the iterator will actually hang and never complete bringing your program to a
stop without throwing an error or exiting.

The ability to delete an item during the iteration is quite useful. I have code that uses a queue.
It is very easy to iterate over the queue and if the proper conditions are met send the item to a processor and delete it from the queue. You can, of course, use an array and process it recursively but using a map is a bit simpler.

In a future post I will look at using functions in maps which is useful for sequentially running promises.

Share