Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 753
Bart van Heukelom Avatar asked Mar 03 '10 09:03

Bart van Heukelom


People also ask

Is dictionary a Hashmap or Hashtable?

Yes, it is a hash mapping or hash table.

Is a Hashmap like a dictionary?

A dictionary (also known as a map, hashmap or associative array) is a set of key/value pairs.


1 Answers

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 {}
    }
}
like image 58
back2dos Avatar answered Dec 05 '22 03:12

back2dos