Is ActionScript 3 Dictionary a hashmap?

Question

http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/

The dictionary does what I need but I do need to care about performance. Does anybody know if the Dictionary is implemented as a hashtable?

Or more specifically, does it perform in O(1)?

Solution 1

it acts as a hashmap. in fact, every ActionScript object that is an instance of a dynamic class, acts as hashmap. of course keys can always collide with properties. this behaviour comes from JavaScript. I consider it a design failure.

Array is different in that it will perform some tricks on integer keys, and Dictionary is different in that it doesn't convert keys to strings, but uses any object value as key. Please note that Number and Boolean are both converted to String.

now why whould you care how it is implemented? if it is well implemented, you probably don't wanna know. You can benchmark it. It has O(1) for all operations and is reasonably fast (inserting costs a about twice as much time as an empty method call, deleting costs less). Any alternative implementation will be slower.

here a simple benchmark (be sure to compile it for release and run it in the right player):

package  {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.*;
    public class Benchmark extends Sprite {

        public function Benchmark() {
            var txt:TextField = new TextField();
            this.addChild(txt);
            txt.text = "waiting ...";
            txt.width = 600;        
            const repeat:int = 20;
            const count:int = 100000;
            var d:Dictionary = new Dictionary();
            var j:int, i:int;
            var keys:Array = [];
            for (j = 0; j < repeat * count; j++) {
                keys[j] = { k:j };
            }
            setTimeout(function ():void {
                var idx:int = 0;
                var out:Array = [];
                for (j = 0; j < repeat; j++) {
                    var start:int = getTimer();
                    for (i = 0; i < count; i++) {
                        d[keys[idx++]] = i;
                    }
                    out.push(getTimer() - start);
                }
                txt.appendText("\n" + out);
                start = getTimer();
                for (var k:int = 0; k < i; k++) {
                    test();
                }
                txt.appendText("\ncall:"+(getTimer() - start));
                idx = 0;
                out = [];
                for (j = 0; j < repeat; j++) {
                    start = getTimer();
                    i = 0;
                    for (i = 0; i < count; i++) {
                        delete d[keys[idx++]];
                    }               
                    out.push(getTimer() - start);
                }
                txt.appendText("\n" + out);
            },3000);//wait for player to warm up a little
        }
        private function test():void {}
    }
}

Solution 2

Nope, it's not. java hashmaps are based on hash codes, while Dictionary is based on strict equality (===) of keys and therefore must not be used if you plan to put objects as keys.

java:

class MyStuff {
  public final int id;

  MyStuff(int i) {
    this.id = i;
  }
  public int hashCode() {
    return this.id;
  }
  public int equals(MyStuff o) {
    return (this.id - o.id);
  }
}

Map<MyStuff, Object> m1 = new HashMap<MyStuff, Object>();
m1.put(new MyStuff(1),  new Object());
assert(m1.get(new MyStuff(1)) != null); //true

as3:

class MyStuff {
  public var id:Number;

  public function MyStuff(i:Number):void {
    this.id = i;
  }
  //no notion of hashCode or equals in AS3 Object class,
  //so we can't really control how the Objects are compared.
}

var d:Dictionary = new Dictionary();
d[new MyStuff(1)] = {};
trace(d[new MyStuff(1)]); //outputs null

I'm looking into the right way of implementing hashing in AS3, but it does look very unpromising...