¿Es el diccionario ActionScript 3 un hashmap?

Question

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

El diccionario hace lo que necesito, pero sí me importa el rendimiento. ¿Alguien sabe si el Diccionario se implementa como una tabla hash?

O más específicamente, ¿funciona en O (1)?

Answer 1

Actúa como un HashMap. de hecho, cada objeto de ActionScript que es una instancia de una clase dinámica, actúa como hashmap. por supuesto, las claves siempre pueden colisionar con las propiedades. este comportamiento proviene de JavaScript. Lo considero una falla de diseño.

La matriz es diferente en cuanto a que realizará algunos trucos en las claves enteras, y Dictionary es diferente en cuanto a que no convierte las claves en cadenas, sino que utiliza cualquier valor de objeto como clave. Tenga en cuenta que Number y Boolean se convierten a String.

ahora ¿por qué le importa cómo se implementa? si está bien implementado, probablemente no quieras saberlo. Usted puede compararlo. Tiene O (1) para todas las operaciones y es razonablemente rápido (la inserción cuesta aproximadamente el doble de tiempo que una llamada de método vacía, eliminando los costos menos). Cualquier implementación alternativa será más lenta.

aquí una referencia sencilla (asegúrese de compilarlo para la liberación y ejecutarlo en el jugador de la derecha):

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

Answer 2

La documentación de adobe en matrices asociadas parece implicar que los diccionarios son HashMaps:.

"Puede utilizar la clase Dictionary para crear una matriz asociativa que utiliza objetos como claves en lugar de cadenas Tales matrices se llaman a veces los diccionarios, hashes, o mapas ".

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

Answer 3

No, no lo es. java hashmaps se basan en códigos hash, mientras que Dictionary se basa en la estricta igualdad (===) de las claves y, por lo tanto, no se deben usar si planea colocar objetos como claves.

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 

Estoy buscando en el camino correcto de la aplicación de hash en AS3, pero que tiene un aspecto muy prometedor ...