Действительно ли словарь ActionScript 3 является hashmap?
http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/
Словарь делает то, в чем я нуждаюсь, но я действительно должен заботиться о производительности. Кто-либо знает, реализован ли Словарь как хеш-таблица?
Или более конкретно, это работает в O (1)?
3 ответа
он действует как хэш-карта. Фактически, каждый объект ActionScript, являющийся экземпляром динамического класса, действует как хэш-карта. конечно, ключи всегда могут столкнуться со свойствами. это поведение исходит из JavaScript. Считаю это ошибкой конструкции.
Array отличается тем, что он выполняет некоторые трюки с целочисленными ключами, а Dictionary отличается тем, что не преобразует ключи в строки, а использует любое значение объекта в качестве ключа. Обратите внимание, что число и логическое значение преобразуются в строку.
а какое вам дело до того, как это реализовано? если это хорошо реализовано, вы, вероятно, не хотите знать. Вы можете сравнить это. Он имеет 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 {}
}
}
Документация Adobe по ассоциированным массивам, кажется, подразумевает, что словари являются хэш-картами:
«Вы можете использовать класс Dictionary для создания ассоциативного массива, который использует объекты для ключей, а не для строк. Такие массивы иногда называют словарями, хэшами или картами "
http://livedocs.adobe.com/flex/3/html/help.html?content=10_Lists_of_data_4.html
Нет, это не так. Хэш-карты 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, но он выглядит очень бесперспективным ...