ActionScript 3 Dictionary是一个哈希映射吗？

Question

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

字典做我需要的但我确实需要关心性能.有人知道Dictionary是否实现为哈希表吗？

或者更具体地说,它是否在O(1)中执行？

Answer 1

它充当哈希映射.实际上,作为动态类实例的每个ActionScript对象都充当hashmap.当然,键总是可以与属性发生碰撞.此行为来自JavaScript.我认为这是设计失败.

数组的不同之处在于它会对整数键执行一些技巧,而Dictionary的不同之处在于它不会将键转换为字符串,而是使用任何对象值作为键.请注意,Number和Boolean都转换为String.

现在为什么你要关心它是如何实施的？如果它实施得很好,你可能不想知道.你可以对它进行基准测 它对所有操作都有O(1)并且速度相当快(插入成本大约是空方法调用的两倍,删除成本更少).任何替代实现都会变慢.

这里有一个简单的基准测试(确保将其编译为发布并在正确的播放器中运行):

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