Creating a true Map implementation with object equality (rant!)

[JonnyR]

Afternoon chaps,

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.


This stackoverflow post (http://stackoverflow.com/questions/51007/lack-of-operator-overloading-in-actionscript-3-0) sums it up pretty well. 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 support 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 dictionay and performing the equality check whenever I perform a containsKey() or get() operation - however, this pretty much defeats the entire point of a hashtable (cheap lookup operations).

If anyone has any views on the this, or a suggestion on how to implement a custom hashing algorythm (so I can replace the Dictionary instance with a "pure" hashtable) I'd love to chat about it!

[Krilnon]

You could follow the Java approach and add something like a hashCode method to your Equalizer interface.

[IQAndreas]

Have you looked into the proxy class? Is that sortof what you are looking for? Then you are notified whenever people are trying to add or remove properties from the "new Dictionary", and avoid using your functions for getting and setting, and whenever properties are set or accessed you can compare them to your list which will check properties and not just where the object references to.

Here is some nice reading on the Proxy class:
http://www.kirupa.com/forum/showthread.php?p=2507388


I did some testing a while back on the Dictionary Class, and since primitives are stored as actual values and not references, doing your above code will give the results you want:

const jonny1 : String = "jonny";
const jonny2 : String = "jonny";

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

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

You can use this to your advantage by having every class you create have a "generateString()" or "toString()" or something, so it can be stored and retrieved from the Dictionary with a String as a key instead of the actual object. Do you need code for this, or do you understand?


If you don't have control over all the classes that are stored in the Dictionary, like if some of them are Flash's builtin classes, you could just use the "describeType()" function which returns XML data, and all properties should match if the two instances are identical.
EDIT: Nevermind. I was thinking wrong. "describeType()" returns a description of the class and does not include property values.

Or you could write your own function that loops through all properties on an object and generates String or XML data listing all properties and values, and returns that for strict checking in the dictionary.


As for storing it as a hash code, sorry, I have no idea. Still learning.

[JonnyR]

@Krilnon
I think you're right - hashCode() is as essential as the equals() method; I think I am going to have to go down the java route if I want this to work correctly. However, I am concerned that it will force me to check that all non primative keys implement the Equalizer/Hashable interface so that I can effectivley store them.

@Iq
Thanks for your response, but in order for me to fully implement a HashMap I am going to need to be able to store references to non primative datatypes; although the toString() method works, it's not explicit enough for me to use as part of a Collections framework.

[JonnyR]

In case anyone is curious to know more about hashMaps, and hashCodes, this post on Stack Overflow (http://stackoverflow.com/questions/730620/how-a-hashtable-works) sums it all up pretty well.

I think I am going to be forced to use some kind of type check on incoming objects to see if they implement a hashCode() method; if they don't then I am going to be forced to use a single bucket and iterate through that. (I guess this is pretty similar to how Java works if an Object implements hashCode() as returning 0).

It's a shame as its yet another thing that developers will have to implement in order to make use of these Collections I'm writing, but I guess that's the price we pay if we want true object equality.