In Java and C/C++ I use hash maps (hash tables) almost exclusively for creating associative arrays. The first time I stumbled upon this datatype I remember wondering to myself about why one would ever use something other than a String or Int as a key. I eventually found a few uses for using real Objects as keys in ActionScript where hash maps are called dictionaries (I realize in some languages Strings and Ints are considered Objects). One of the most useful things for the kind of work I do is using a hash map to associate a property or group of properties with an Object, without altering the interface of that Object. I’ll give a few examples. The jQuery data() method is used to associate properties with matched elements. Like this:

// match element with id "test"
var test = $("#test");
test.data("prop", "value");
 
// outputs value
console.log(test.data("prop"));

This is really nice. Some libraries don’t offer this kind of functionality though. So a hash map could come in handy:

 
var propLookup = new HashMap();
var paper = Raphael(0, 0, 400, 400);
 
var circle = paper.circle(100, 100, 10);
circle.attr("fill", "#f00");
 
propLookup(circle, "someProperty");
 
// outputs "someProperty"
console.log(propLookup(circle);

The above example uses the great Raphaeljs library. If there is a method for dealing with dynamic properties in Raphael I haven’t found it. You could of course just add the property “circle.someProp” which will work fine, but could potentially collide with an internal property.

Implementation

I designed a javascript hash map in a bit of a strange way. It works like this:

var hMap = new HashMap();
var a = {};
var b = {};
 
hMap(a, "one");
hMap(b, "two");
hMap(100, "three");
hMap("name", "Zevan");
 
hMap.each(function(key, value){
  console.log(key, value);
});
 
// removes the element with 100 for its key
hMap.delete(100);
 
// gets the number of elements in the hash map
console.log(hMap.size());

This outputs:

Object "one"
Object "two"
100 "three"
name Zevan
3

Basically doing new HashMap() returns a function that takes either 1 or two arguments. If it gets two arguments it populates the map using the first argument as a key and the next argument as a value. If it gets one argument, it assumes you are asking for a key and returns the corresponding value. It has three methods, delete(), size() and each() which are all pretty self explanatory. Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

function HashMap() {
  var obj = [];
  function find(key){
    var i = obj.length;
    while (i--) {
      var curr = obj[i];
      if (curr[0] === key) {
        return i;
      }
    }
    return null;
  }
  var d = function dictionary(key, value) {
    var index = find(key);
    if (value) {
      if (index != null){
        obj.splice(index, 1);
      }
      obj.push([key, value]);
 
    } else {
      if (index != null){
        return obj[index][1];
      }
    }
  }
  d.size = function(){
    return obj.length;
  }
  d.delete = function(key) {
    obj.splice(find(key), 1);
  }
  d.each = function(func){
    for (var i = 0; i<obj.length; i++){
      var item = obj[i]
      func(item[0], item[1]); 
    }
  }
  return d;
}

This could probably be optimized a bit, but I wanted to leave it readable.

Just as a side note, here is the kind of thing I found myself doing in ActionScirpt from time to time:

1
2
3
4
5
6
7
8

var s:Sprite = new Sprite();
// dictionary is like a HashMap in AS
var lookup:Dictionary = new Dictionary();
lookup[s] = someValue;
s.addEventListener(MouseEvent.CLICK, onClick);
function onClick(evt:Event):void{
  trace(lookup[evt.currentTarget]);
}

This entry was posted on Tuesday, January 25th, 2011 and is filed under ActionScript, data-structures, javascript, misc. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response or Trackback from your own site.