Sometimes you need to map a key to many values, but AS3 has no built-in data structure for this purpose. Dictionary and Object are suitable one-to-one maps, but there’s been no one-to-many support until now. Read on for my own one-to-many class—MultiMap—as well as performance testing and analysis.

Before writing your own general-purpose class, it’s a good idea to take a few minutes and do some searching online to see if anyone else has already implemented it. I did just this and found that the Vegas Framework has a MultiValueMap and HashMap that can, together, form a suitable multi-map. I also found Sascha Balkau’s MultiMap class.

Clearly, I’ve written my own MultiMap class even though these alternatives exist. Why? Well, the Vegas Framework entails pulling in a SWC with at least 957 classes and interfaces. Some of them will surely drop out when compiling, but there are at least a half dozen classes that will be compiled in just for multi-map support. In the case of Sascha Balkau’s class, there are only two classes to compile in. However, it seems as though he’s implemented his own hash map despite the existence of Dictionary. In short, I had serious questions about both libraries’ performance, size, and license (MPL).

Still, I looked around at various multi-map APIs and tried to glean ideas from them for my own class. I decided from the start to use a Dictionary for the main mapping and a secondary Dictionary to store the mapped values. So the main Dictionary would have a key “fruit” that would map to a Dictionary whose keys would be “apple”, “pear”, and “banana”. This arrangement means that insertion, checking, and removal is all very cheap and the design’s simplicity keeps the implementation to a single 200-line class. Finally, I licensed it under the extremely-permissive MIT license.

Here are some quick usage examples:

var map:MultiMap = new MultiMap();
 
// insert one value at a time
map.insertVal("fruit", "apple");
map.insertVal("fruit", "pear");
map.insertVal("fruit", "banana");
 
// insert many values at a time
map.insertVals("continent", "europe", "asia", "africa");
 
// insert a whole object at once
map.insertProperties({first:"Jackson", last:"Dunstan", profession:"programmer"});
 
// visualize the map
trace(map.toMapString());
// fruit
//     -> apple
//     -> pear
//     -> banana
// continent
//     -> europe
//     -> asia
//     -> africa
// first
//     -> Jackson
// last
//     -> Dunstan
// profession
//     -> programmer
 
// count the keys
map.countKeys(); // 5
 
// count the values of one key
map.countVals("continents"); // 3
 
// count the values of all keys
map.countAllVals(); // 9
 
// copy the map
map2 = map.clone();
 
// check if a key exists
map.hasKey("fruit");
 
// check if a value exists in any key
map.hasVal("asia");
 
// check if a key-value pair exists
map.hasPair("first", "Jackson");
 
// remove a key and all its values
map.removeKey("fruit");
 
// remove just one value from a key
map.removeVal("asia");
 
// remove a value from one key
map.removePair("continent", "africa");
 
// remove all keys and values
map.removeAll();

Now for the full source code with more in-depth documentation:

/*
The MIT License
 
Copyright (c) 2011 Jackson Dunstan
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
package
{
	import flash.utils.Dictionary;
 
	/**
	*   A collection that maps keys to one or more values
	*   @author Jackson Dunstan, http://JacksonDunstan.com
	*/
	public class MultiMap
	{
		/** If the keys of the map are weakly-referenced */
		private var __weakKeys:Boolean;
 
		/** Mapping of keys to Dictionaries of values */
		private var __keys:Dictionary;
 
		/**
		*   Make the map
		*   @param weakKeys If the keys of the map are weakly-referenced.
		*                   Defaults to false.
		*/
		public function MultiMap(weakKeys:Boolean=false)
		{
			__keys = new Dictionary(weakKeys);
			__weakKeys = weakKeys;
		}
 
		/**
		*   If the keys of the map are weakly-referenced
		*/
		public function get weakKeys(): Boolean
		{
			return __weakKeys;
		}
 
		/**
		*   Mapping of keys to Dictionaries of values. Beware changing this.
		*/
		public function get keys(): Dictionary
		{
			return __keys;
		}
 
		/**
		*   If the map has no keys (or values)
		*/
		public function get isEmpty(): Boolean
		{
			for (var key:* in __keys)
			{
				return false;
			}
			return true;
		}
 
		/**
		*   Map a key to a value. Overwrites any previous mapping of the given
		*   key and value.
		*   @param key Key to map to the given value
		*   @param val Value to map to the given key
		*/
		public function insertVal(key:*, val:*): void
		{
			var vals:Dictionary = __keys[key];
			if (!vals)
			{
				vals = __keys[key] = new Dictionary();
			}
			vals[val] = true;
		}
 
		/**
		*   Map a key to many values. Overwrites any previous mapping of the
		*   given and values.
		*   @param key Key to map to the given values
		*   @param vals Values to map to the given key
		*/
		public function insertVals(key:*, ...vals): void
		{
			var valsDict:Dictionary = __keys[key];
			if (!valsDict)
			{
				valsDict = __keys[key] = new Dictionary();
			}
			for each (var val:* in vals)
			{
				valsDict[val] = true;
			}
		}
 
		/**
		*   Map the keys of the given object to their values. For example,
		*   {first:"Jackson", last:"Dunstan"} maps "first" to "Jackson" and
		*   "last" to "Dunstan". Overwrites any previous mapping of the given
		*   object's keys and values.
		*   @param obj Object whose properties should be mapped
		*/
		public function insertProperties(obj:*): void
		{
			for (var key:* in obj)
			{
				var vals:Dictionary = __keys[key];
				if (!vals)
				{
					vals = __keys[key] = new Dictionary();
				}
				vals[obj[key]] = true;
			}
		}
 
		/**
		*   Get the values mapped to a given key. Beware changing this.
		*   @param key Key to get values for
		*   @return The values mapped to the given key or null if no values are
		*           mapped to the given key.
		*/
		public function getVals(key:*): Dictionary
		{
			return __keys[key];
		}
 
		/**
		*   Check if a key has had values mapped to it
		*   @param key Key to check
		*   @return If the given key has had values mapped to it
		*/
		public function hasKey(key:*): Boolean
		{
			return key in __keys;
		}
 
		/**
		*   Check if any key has been mapped to a given value
		*   @param val Value to check
		*   @return If any key has been mapped to a given value
		*/
		public function hasVal(val:*): Boolean
		{
			var keys:Dictionary = __keys;
			for (var key:* in keys)
			{
				if (val in keys[key])
				{
					return true;
				}
			}
			return false;
		}
 
		/**
		*   Check if the given key has been mapped to the given value
		*   @param key Key to check
		*   @param val Value to check
		*   @return If the given key has been mapped to the given value
		*/
		public function hasPair(key:*, val:*): Boolean
		{
			var vals:Dictionary = __keys[key];
			if (!vals)
			{
				return false;
			}
			return val in vals;
		}
 
		/**
		*   Unmap the given key and all values mapped to it
		*   @param key Key to unmap
		*/
		public function removeKey(key:*): void
		{
			delete __keys[key];
		}
 
		/**
		*   Unmap the given value from all keys
		*   @param val Value to unmap
		*/
		public function removeVal(val:*): void
		{
			var keys:Dictionary = __keys;
			for (var key:* in keys)
			{
				var vals:Dictionary = keys[key];
				delete vals[val];
 
				// If the key is no longer mapped to any vals, remove it
				var empty:Boolean = true;
				for (var value:* in vals)
				{
					empty = false;
				}
				if (empty)
				{
					delete keys[key];
				}
			}
		}
 
		/**
		*   Unmap the given key-value pair
		*   @param key Key to unmap
		*   @param val Value to unmap
		*/
		public function removePair(key:*, val:*): void
		{
			var vals:Dictionary = __keys[key];
			if (vals)
			{
				delete vals[val];
 
				// If the key is no longer mapped to any vals, remove it
				var empty:Boolean = true;
				for (var value:* in vals)
				{
					empty = false;
				}
				if (empty)
				{
					delete keys[key];
				}
			}
		}
 
		/**
		*   Unmap all keys and values
		*   @param key Key to unmap
		*   @param val Value to unmap
		*/
		public function removeAll(): void
		{
			var keys:Dictionary = __keys;
			for (var key:* in keys)
			{
				delete keys[key];
			}
		}
 
		/**
		*   Count the number of keys in the map
		*   @return The number of keys in the map
		*/
		public function countKeys(): uint
		{
			var count:uint;
			for (var key:* in __keys)
			{
				count++;
			}
			return count;
		}
 
		/**
		*   Count the number of values in the map for the given key
		*   @param key Key whose values should be counted
		*   @return The number of keys in the map for the given key or zero if
		*           the given key is not mapped
		*/
		public function countVals(key:*): uint
		{
			var count:uint;
			for (var key:* in __keys[key])
			{
				count++;
			}
			return count;
		}
 
		/**
		*   Count the number of values in the map for all keys
		*   @return The number of keys in the map for all keys
		*/
		public function countAllVals(): uint
		{
			var count:uint;
			for (var key:* in __keys)
			{
				var vals:Dictionary = keys[key];
				for (var val:* in vals)
				{
					count++;
				}
			}
			return count;
		}
 
		/**
		*   Make a new map that has the same mappings and key strength
		*   (i.e. weak keys, strong keys) as this map
		*   @return A new map that has the same mappings and key strength as
		*           this map
		*/
		public function clone(): MultiMap
		{
			var ret:MultiMap = new MultiMap(__weakKeys);
			var keys:Dictionary = __keys;
			for (var key:* in keys)
			{
				var vals:Dictionary = keys[key];
				for (var val:* in vals)
				{
					ret.insertVal(key, val);
				}
			}
			return ret;
		}
 
		/**
		*   Get a new String that shows the mappings
		*   @return A new String that shows the mappings
		*/
		public function toMapString(): String
		{
			var ret:String = "";
			var keys:Dictionary = __keys;
			for (var key:* in keys)
			{
				ret += key + "\n";
				var vals:Dictionary = keys[key];
				for (var val:* in vals)
				{
					ret += "\t-> " + val + "\n";
				}
			}
			return ret;
		}
	}
}

To test the performance of this class against the two other multi-map implementations I found, I made the following performance test app that checks how fast each version can perform the core operations of a multi-map: add mappings, check if mappings exist, and remove mappings.

package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
	import system.data.maps.MultiValueMap;
	import system.data.maps.HashMap;
 
	public class MultiMapTest extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function row(...cols): void
		{
			__logger.appendText(cols.join(",") + "\n");
		}
 
		public function MultiMapTest()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(__logger);
 
			var beforeTime:int;
			var afterTime:int;
			var jdTime:int;
			var sbTime:int;
			var vTime:int;
 
			var i:int;
			var REPS:int = 20000;
 
			var mapJD:MultiMap = new MultiMap();
			var mapSB:SBMultiMap = new SBMultiMap(100, SBMultiMap.hashString);
			var mapV:MultiValueMap = new MultiValueMap(null, HashMap);
 
			row("Function", "JD", "SB", "V");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapJD.insertVal("Key", "Value");
			}
			afterTime = getTimer();
			jdTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapSB.put("Key", "Value");
			}
			afterTime = getTimer();
			sbTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapV.put("Key", "Value");
			}
			afterTime = getTimer();
			vTime = afterTime - beforeTime;
			row("add", jdTime, sbTime, vTime);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapJD.hasKey("Key");
			}
			afterTime = getTimer();
			jdTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapSB.containsKey("Key");
			}
			afterTime = getTimer();
			sbTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapV.containsKey("Key");
			}
			afterTime = getTimer();
			vTime = afterTime - beforeTime;
			row("add", jdTime, sbTime, vTime);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapJD.removePair("Key", "Value");
			}
			afterTime = getTimer();
			jdTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapSB.remove("Key");
			}
			afterTime = getTimer();
			sbTime = afterTime - beforeTime;
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mapV.removeByKey("Key", "Value");
			}
			afterTime = getTimer();
			vTime = afterTime - beforeTime;
			row("add", jdTime, sbTime, vTime);
		}
	}
}

I ran the performance test with the following environment:

  • Flex SDK (MXMLC) 4.5.1.21328, compiling in release mode (no debugging or verbose stack traces)
  • Release version of Flash Player 10.3.181.35
  • 2.4 Ghz Intel Core i5
  • Mac OS X 10.6.8

And got these results:

Function JacksonDunstan.com Sascha Balkau Vegas Framework
add 4 4597 9
contains 1 8968 3
remove 3 9632 71

MultiMap Performance Chart

For a better comparison between my version and the Vegas Framework version, let’s chop out Sascha Balkau’s version from the chart.

MultiMap Performance Chart (JD and V only)

Clearly, Sascha Balkau’s MultiMap is a ton slower than the others on all three tests. This slowdown is usually in the range of about 1000-3000x, which makes it only suitable to applications that can afford to burn a lot of performance. As for the Vegas Framework version, it’s 2x-20x slower than my own version.

So, if you want a Flash 9+ AS3 multi-map implementation with a permissive open-source license (MIT), a single-class implementation for a la carte usage, and the best performance of them all by a good margin, choose my MultiMap class! :)

Spot a bug? Have a suggestion? Question on usage? Post a comment!