ActionScript 3 MultiMap Class
Recently I needed a HashMap for a project to map key/value pairs but in that particular case the Map required to map not just one but several values to a key. I could have used an array or object to store the values in and map that one but in practice it turned out that accessing the map looked rather messy. It would be much more elegant to have a map to that multiple values can be mapped directly. After some investigation (strangely even Java seems not to have a MultiMap included) I came up with writing my own MultiMap class, so here it is!
The MultiMap is heavily based on Michael Baczynski’s HashTable class but I modified it to my requirements and added a couple of additional methods for luxury. At first I wrote an even more customized version that would decide automatically which hash function to use but as it turned out some of these changes weighted heavy on the performance, especially not using a strict equality operator (===) and having a HashEntry object with non-numeric keys. In fact Michael’s class is still a tad faster (he really squeezed out the last bit of performance there) but as long as the MultiMap isn’t too large/full there is only a minor difference of some milliseconds.
As a trade-off I added checking for existing keys (which can be omitted to improve performance when adding values) and of course there is the multiple values functionality which required a more complex implementation of some methods.
I’m sure there is still a lot of room for improvement so if you have any suggestions it would be cool to let us know!
Nice work
Perhaps I would add a function that just retrieves all stored values at a given key perhaps like so:
public function getValues(key:*):Array
{
...
for (...)
{
if (entry.key === key)
{
return entry.data;
}
}
return null;
}
This would be a a little bit faster when often processing a bunch of values at a key.
ah I forgot to mention, when you omit the valueIndex parameter in the getValue() function and the entry has multiple items you don’t know if the function returns an array or an object/primitive. Maybe it would be better to always return an array (even if it contains only one item) or feed it with an empty array and the function fills out the array elements and instead returns the number of items:
var data:Array = [];
var numItems:int = getValues(myKey, []);
Hi Michael, adding a getValues method that always returns an array is a good idea. But it makes me thinking about if in that case changing the getValue method to always return an array makes sense. If the user doesn’t provide a valueIndex an Array should always be expected so how about this …
Adding the getValues method and in the getValue method at the beginning use this:
if (valueIndex < 0) return getValues(key);
That way always an Array is returned if valueIndex was omitted. But then again it is questionable if valueIndex should be an optional or obligatory parameter.
Interesting to mention that your find method is still faster than the getValues method even though they are virtually the same. In fact typing the entry variable inside the for loop provides a small performance boost for my method.
Hey! Thxs for the reply!
I think I gave the wrong mail now it’s the correct! thanxS!!!
how do i implement it? can i see an example? tk.
Gaston, there’s an example of how to use it in the class comment. Or did you mean something else?
Hi All:
I wonder if next thing if possible:
If more than one key is accepted, it will return values based on:
Key1, key2, key3, etc.
And if just one key is entered, it should return all values that match that key.
Thx.
Randall
Hmm.. looking through your code makes me wonder why you don’t use hash tables to store the array hash/map? I usually do sth like that (shortened, simplified):
_map : Object;
function setValue( key : String , value : * ) : void {
if ( _map[key] == undefined ) _map[key] = [];
_map[key].push(value);
}
That way you don’t have to iterate through all lists which is MUCH faster. All methods in your class would be feasible with that data structure (I think). Or is there sth I’m not getting?
Sev, yes thanks for the tip. I might be rewriting the class anyway soon so I will try using tables.