One of the advantages of using Dictionary instead of Object when mapping key-value pairs is that you can use whatever type of key you want, not just a String. However, a recent comment points out that the keys are still checked with the loose equality operator (==) and you can therefore get clashes like 4 == "4". For today’s article, I’ve written a TypesafeDictionary class that allows you to overcome this limitation. Read on for the implementation, performance testing, and more.

Let’s begin by looking at what the problem is exactly. Consider the following code that uses Dictionary and an equivalent version that uses TypesafeDictionary:

package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class TypesafeDictionaryCorrectness extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function log(msg:*): void { __logger.appendText(msg + "\n"); }
 
		public function TypesafeDictionaryCorrectness()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(__logger);
 
			var i:* = 4;
			var iAlias:String = "the number four";
			var s:* = "4";
			var sAlias:String = "'f' 'o' 'u' 'r'";
			var k:*;
			var k2:*;
 
			log("--Dictionary--");
			var d:Dictionary = new Dictionary();
			d[i] = iAlias;
			d[s] = sAlias;
			for (k in d)
			{
				log(k + ": " + d[k]);
			}
 
			log("--TypesafeDictionary--");
			var td:TypesafeDictionary = new TypesafeDictionary();
			td.insertVal(i, iAlias);
			td.insertVal(s, sAlias);
			for (k2 in td.types)
			{
				log(k2);
				var type:Dictionary = td.types[k2];
				for (k in type)
				{
					log("\t" + k + ": " + type[k]);
				}
			}
		}
	}
}

In the Dictionary version, the line d[s] = sAlias overwrites the value stored in the Dictionary by the line d[i] = iAlias. This is because the Dictionary class does a loose equality check (==) when inserting and finds a match between the String "4" and the int 4. As we see in the output, the TypesafeDictionary version avoids this problem and stores both key-value pairs as expected:

--Dictionary--
4: 'f' 'o' 'u' 'r'
--TypesafeDictionary--
string
	4: 'f' 'o' 'u' 'r'
number
	4: the number four

Here is the source code for the TypesafeDictionary class:

/*
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 values without overwriting keys based on
    *   loose equality (i.e. the == operator)
    *   @author Jackson Dunstan, http://JacksonDunstan.com
    */
	public class TypesafeDictionary
	{
		/** Dictionary that maps the type of the user's key to a Dictionary
		*** which maps the user's key to the user's value */
		public var types:Dictionary;
 
		/** If the keys of the type Dictionaries are weakly-referenced */
		private var __weakKeys:Boolean;
 
		/**
		*   Make the dictionary. It is initially empty.
		*   @param weakKeys If the keys of the map are weakly-referenced.
        *                   Defaults to false.
		*/
		public function TypesafeDictionary(weakKeys:Boolean=false)
		{
			this.types = new Dictionary();
			__weakKeys = weakKeys;
		}
 
		/**
        *   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 keyType:String = typeof key;
			var type:Dictionary = this.types[keyType];
			if (!type)
			{
				type = this.types[keyType] = new Dictionary(__weakKeys);
			}
			type[key] = val;
		}
 
		/**
        *   Get the value mapped to a given key
        *   @param key Key to get value for
        *   @return The value mapped to the given key or undefined if no value
        *           is mapped to the given key
        */
		public function getVal(key:*): *
		{
			var type:Dictionary = this.types[typeof key];
			return type ? type[key] : undefined;
		}
 
		/**
        *   Check if a key has a value mapped to it
        *   @param key Key to check
        *   @return If the given key has a value mapped to it
        */
		public function hasKey(key:*): Boolean
		{
			var keyType:String = typeof key;
			return keyType in this.types && key in this.types[keyType];
		}
 
		/**
        *   Unmap the given key and any value mapped to it
        *   @param key Key to unmap
        */
		public function removeKey(key:*): void
		{
			var keyType:String = typeof key;
			var type:Dictionary = this.types[keyType];
			if (type)
			{
				delete type[key];
			}
		}
	}
}

So, what kind of performance penalty do we suffer by using TypesafeDictionary instead of Dictionary? To find out, I’ve written a small performance testing app:

package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class TypesafeDictionaryPerformance extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function row(...cols): void
		{
			__logger.appendText(cols.join(",") + "\n");
		}
 
		public function TypesafeDictionaryPerformance()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(__logger);
 
			var beforeTime:int;
			var afterTime:int;
			var dTime:int;
			var tsTime:int;
			var key:String;
			var val:String;
			var REPS:int = 1000000;
			var SIZE:int = 100;
			var DELETE_KEY:String = "--keynotfound--";
			var GET_KEY:String = "key0";
			var SET_VAL:String = "val0";
			var i:int;
 
			var dict:Dictionary = new Dictionary();
			var tsDict:TypesafeDictionary = new TypesafeDictionary();
			for (i = 0; i < SIZE; ++i)
			{
				key = "key" + i;
				val = "val" + i;
				dict[key] = val;
				tsDict.insertVal(key, val);
			}
 
			row("Function", "Dictionary", "TypesafeDictionary");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				delete dict[DELETE_KEY];
			}
			afterTime = getTimer();
			dTime = afterTime - beforeTime;
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				tsDict.removeKey(DELETE_KEY);
			}
			afterTime = getTimer();
			tsTime = afterTime - beforeTime;
			row("removeKey", dTime, tsTime);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				dict[GET_KEY];
			}
			afterTime = getTimer();
			dTime = afterTime - beforeTime;
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				tsDict.getVal(GET_KEY);
			}
			afterTime = getTimer();
			tsTime = afterTime - beforeTime;
			row("getVal", dTime, tsTime);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				GET_KEY in dict;
			}
			afterTime = getTimer();
			dTime = afterTime - beforeTime;
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				tsDict.hasKey(GET_KEY);
			}
			afterTime = getTimer();
			tsTime = afterTime - beforeTime;
			row("hasKey", dTime, tsTime);
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				dict[GET_KEY] = SET_VAL;
			}
			afterTime = getTimer();
			dTime = afterTime - beforeTime;
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				tsDict.insertVal(GET_KEY, SET_VAL);
			}
			afterTime = getTimer();
			tsTime = afterTime - beforeTime;
			row("insertVal", dTime, tsTime);
		}
	}
}

I ran this 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.183.7
  • 2.4 Ghz Intel Core i5
  • Mac OS X 10.7.1

And got these results:

Function Dictionary TypesafeDictionary
removeKey 117 238
getVal 103 232
hasKey 89 303
insertVal 122 239

TypesafeDictionary Performance Chart

Clearly, Dictionary is the performance winner here. It would be impossible to beat it since it’s built in native code and has special handling by the Flash Player. For example, it handles for-in and for-each-in loops without resorting to the Proxy class (and its poor performance).

The performance we see is about double due to doubling the Dictionary lookups. In the case of hasKey, which is exceptionally fast, the function call time itself is skewing the results to about 3x slower since we cannot simply use the in operator.

So, TypesafeDictionary may not be suitable for performance-critical areas of your code. I recommend limiting its use there and instead using it as a lesson. When using Dictionary in a performance-critical area of code, design your keys such that they will not match each other with the loose equality operator (==). This will obviate the need for TypesafeDictionary, avoid key overwriting, and keep your code speedy.

Spot a bug? Have a suggestion? Post a comment!