开发者

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

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, h开发者_如何学编程ow would I go about creating the hashes for unique object instances passed in as keys so I can still maintain equality?


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.


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) ...


Old thread I know, but still worth posting.

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

The problem with AS3/JavaScript/EcmaScript is not that they create two different, equivalent objects.

The problem is that they cannot equate those two equivalent objects--only identity works, since there is no equals or hashCode methods that can be overriden with class-specific comparison logic.

For Map implementations such as dynamic Object or Dictionary, this means that you have to either use Strings or references as keys: you cannot recover objects from a map using different but equivalent objects.

To work around that problem, people either resort to strict toString implementations (for Object maps) which is undesirable, or to instance control for Dictionaries, as in @back2dos example, which introduces different problems (Also, note that @back2dos solution does not really guarantee unique Person instances since there is a time window during which asynchronous threads will be allowed to instantiate new Persons).

@A.Levy's solution is good except that in general, hashCodes are not strictly required to issue unique values (they are meant to map entries to buckets allowing for fast lookups, wherein fine-grained differentiation is done through equals method).

You need both a hashCode and an equals method, e.g.

public interface IEquable
{
    function equals(object : Object) : Boolean;
    function hash():String;    
}


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜