Является ли словарь ActionScript 3 хэш-картой? - PullRequest
Новая
       9

Является ли словарь ActionScript 3 хэш-картой?

15 голосов
/ 03 марта 2010

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

Словарь делает то, что мне нужно, но мне нужно заботиться о производительности.Кто-нибудь знает, реализован ли словарь как хеш-таблица?

Или, более конкретно, он работает в O (1)?

Ответы [ 3 ]

14 голосов
/ 03 марта 2010

действует как хэш-карта. фактически каждый объект ActionScript, который является экземпляром динамического класса, действует как hashmap. конечно ключи всегда могут конфликтовать со свойствами. это поведение происходит из JavaScript. Я считаю это неудачей проекта.

Массив отличается тем, что он выполняет некоторые трюки с целочисленными ключами, а Словарь отличается тем, что он не преобразует ключи в строки, но использует любое значение объекта в качестве ключа. Обратите внимание, что 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 {}
    }
}
4 голосов
/ 07 июня 2010

Нет, это не так. Хеш-карты Java основаны на хеш-кодах, в то время как Словарь основан на строгом равенстве (===) ключей и поэтому не должен использоваться, если вы планируете помещать объекты в качестве ключей.

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

Я ищу правильный способ реализации хеширования в AS3, но это выглядит очень бесперспективно ...

0 голосов
/ 03 марта 2010

Документация Adobe по ассоциированным массивам, по-видимому, подразумевает, что словари являются хеш-картами:

"Вы можете использовать класс Dictionary для создания ассоциативного массива, который использует объекты для ключей, а не для строк. Такие массивы иногда называют словарями, хэшами или картами."

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

...