CODEWITHSUNDEEP
actionscript-3hashtablehashmap
Bart van Heukelom
Bart van Heukelom

Reputation: 44104

Is ActionScript 3 Dictionary a hashmap?

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)?

Upvotes: 15

Views: 24188

Answers (3)

Yog Sothoth
Yog Sothoth

Reputation: 384

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...

Upvotes: 4

back2dos
back2dos

Reputation: 15623

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 {}
    }
}

Upvotes: 14

justkevin
justkevin

Reputation: 3199

The adobe documentation on associate arrays seems to imply that dictionaries are hashmaps:

"You can use the Dictionary class to create an associative array that uses objects for keys rather than strings. Such arrays are sometimes called dictionaries, hashes, or maps."

http://livedocs.adobe.com/flex/3/html/help.html?content=10_Lists_of_data_4.html

Upvotes: 0

Related Questions