Creating a "true" HashMap implementation with Object Equality in ActionScript 3

Question

I've been spending some of my spare time working a set of collections for ActionScript 3 but I've hit a pretty serious roadblock thanks for the way ActionScript 3 handles equality checks inside Dictionary Objects.

When you compare a key in a dictionary, ActionScript uses the === operator to perform the comparison, this has a bit of a nasty side effect whereby only references to the same instance will resolve true and not objects of equality. Here's what I mean:

const jonny1 : Person = new Person("jonny", 26);
const jonny2 : Person = new Person("jonny", 26);

const table : Dictionary = new Dictionary();
table[jonny1] = "That's me";

trace(table[jonny1]) // traces: "That's me"
trace(table[jonny2]) // traces: undefined.

The way I am attempting to combat this is to provide an Equalizer interface which looks like this:

public interface Equalizer 
{
    function equals(object : Object) : Boolean;
}

This allows to to perform an instanceOf-esq. check whenever I need to perform an equality operation inside my collections (falling back on the === operator when the object doesn't implement Equalizer); however, this doesn't get around the fact that my underlying datastructure (the Dictionary Object) has no knowledge of this.

The way I am currently working around the issue is by iterating through all the keys in the dictionary and performing the equality check whenever I perform a containsKey() or get() operation - however, this pretty much defeats the entire point of a hashmap (cheap lookup operations).

If I am unable to continue using a Dictionary instance as the backing for map, how would I go about creating the hashes for unique object instances passed in as keys so I can still maintain equality?

Answer 1

How about you compute a hash code for your objects when you insert them, and then look them up by the hash code in your backing dictionary? The hashcode should compare === just fine. Of course, that would require you to have a Hashable interface for your object types instead of your Equalizer interface, so it isn't much less work than you are already doing, but you do get the cheap lookups.

Answer 2

How about rather doing this:

 public interface Hashable {
      function hash():String;
 }

personally, I ask myself, why you want to do this ... hashing objects to obtain keys makes little sense if they are mutable ...

also, you might consider using a different approach, as for example this factory:

package {
 public class Person {
  /**
   * don't use this!
   * @private
   */
  public function Person(name:String, age:int) {
   if (!instantiationAllowed)
    throw new Error("use Person.getPerson instead of constructor");
   //...
  }
  private static var instantiationAllowed:Boolean = false;
  private static var map:Object = {};
  private static function create(name:String, age:int):Person {
   instantiationAllowed = true;
   var ret:Person = new Person(name, age);
   instantiationAllowed = false;
  }
  public static function getPerson(name:String, age:int):Person {
   var ageMap:Array = map[name];
   if (ageMap == null) {
    map[name] = ageMap = [];
    return ageMap[age] = Person.create(name, age);
   }
   if (ageMap.hasOwnProperty(age))
    return ageMap[age];
   return ageMap[age] = Person.create(name, age);
  }
 }
}

it ensures, there's only one person with a given name and age (if that makes any sense) ...

greetz

back2dos

Answer 3

In any programming language,

const jonny1 : Person = new Person("jonny", 26); const jonny2 : Person = new Person("jonny", 26);

is creating two completely different objects that will not compare using ==, guess I don't see why it's any more of a road block because of as3