Generic Two Key Dictionary

Introduction

In software development it is not uncommon to come across a situation where you need a dictionary but found in your analysis you have two keys that map to the same value. A common solution is to create two dictionary and keep them synchronized or use another data structure with a higher access and processing time and live with it. Presented here is an alternative called Generic Two Key Dictionary. The Generic Two Key Dictionary provides a means to have two keys to map to the same value with an access and processing envelop close to the provided C# generic dictionary.

This article is broken up into three sections. The first covers the basics operation of the .NET generic dictionary. The second section covers the implementation of the two key dictionary. The third section gives examples of the code in use. Then close with some limitation of the two key dictionary.

The .NET Generic Dictionary

Starting off with how Microsoft .NET generic dictionary works is important because it would allow one to under stand the direction I have taken to achieved a dictionary with two keys. Getting information on the .NET generic dictionary data structure was easy given Microsoft had placed the .NET Framework source code online [1]. Each key-value is stored in a data structure called Entry. The Entry structure seen below consists of hashCode from the key, the key, and value. The next integer value is use in collection resolution. Each Entry structure is then stored in the entries array.

To find the entry in the array with a given key there is another array seen below called buckets.

The buckets is an integer array used for holding the indexes into the entries array for retrieving the value. The calculated hash value from a given key is used to find the buckets index which would have the index into the entries array for the value as illustrated in the example below.

In the case of a collision, the buckets still hold the index into the entries array but it would be the first element. This is where the next value in the Entry structure come into play. The algorithm check if the entry matches the calculated hash code. If not, it then checks the entry.next value which would give the next index in the entries array. This would continue until the proper entry is found and return the value. This technique for collision resolution is called chaining [2]. Below is a simple example of this technique.

Of course, if the key given is not in the entries array it would return the proper response value or exception error.

Generic Two Key Dictionary

With the basic example on how the .NET generic dictionary works one might be able to guess what I had done to achieve a two key dictionary. The generic two key dictionary is based off the code structure from the .NET generic dictionary. I had taken this approach because I didn’t want to reinvent the wheel. Also, the .NET generic dictionary code structure is a well-known and proven; thus, code harvesting for a two key dictionary would speed up the development time. I first started by examining the implemented interfaces for the dictionary. Those interfaces would have to be rewritten to taken into account a generic two key dictionary data structure. For example, below is the IDictionary and after that is the ITwoKeyDictionary.

As you can see the interfaces were rewritten to take into consideration having two keys instead of one. This was done with every interface implemented by the .NET generic dictionary. Presented below is the class diagram showing the generic two key dictionary with its rewritten interfaces, struct, and classes.

Entry Structure

The key to making the generic two key dictionary work is extending the entry structure. The entry structure below shows the changes made by adding IsBkey, keyA, keyB, and node.

The Entry extension with two keys would require both keys to be populated because when you remove one key you have to be able to remove the other key with value as well. The EntryNode class is used as a wrapper for holding the TValue type. This provides a means for the A-Key to hold a reference to B-Key value without having to do a lookup using B-Key.

Coding

With the basic two key dictionary inner structure explained we can move on to an example of code use. The example below shows the initialization, adding elements, indexing, key removal, and enumeration of the two key dictionary.

static void Main(string[] args)
{
	TwoKeyDictionary<int, string, string> tkd = new TwoKeyDictionary<int, string, string>();

	// Add elements to the two key dictionary
	tkd.Add(33024, "LJ02-026XN-PEP2F-M88L", "7FwCTLnD0ZdnDmYRPbZW");
	tkd.Add(66571, "LJ02-026XN-PEP2F-M88N", "Y4cE253SCT3agPC96Fhd");
	tkd.Add(86280, "LJ02-026XN-PEP2F-M88T", "cGnsZLmKK8xKDQnCprKY");
	tkd.Add(58647, "LJ02-026XN-PEP2F-M88R", "TWAggDF0jZVH454RRvrs");
	tkd.Add(87303, "LJ02-026XN-PEP2F-M88Q", "TuGEgtXSm9WQ6JLFGGLW");
	tkd.Add(86891, "LJ02-026XN-PEP2F-M88P", "ExmwnpRHWWx39dEkP6Ay");
	tkd.Add(69992, "LJ02-026XN-PEP2F-M88M", "cQ6RNcQcEm1KFXqRkBth");

	// Access by index with A-Key
	string result = string.Empty;
	result = tkd[58647];        // Result would be: TWAggDF0jZVH454RRvrs
	Console.WriteLine("Index by A-Key: {0}", result);

	// Access by index with B-Key
	result = tkd["LJ02-026XN-PEP2F-M88M"];  // Result would be: cQ6RNcQcEm1KFXqRkBth
	Console.WriteLine("Index by B-Key: {0}", result);

	// Contains key for A/B-Key
	bool bResult = false;
	bResult = tkd.ContainsKeyA(86280);  // Result would be: true

	bResult = tkd.ContainsKeyB("LJ02-026XN-PEP2F-M881");    // Result would be: false;
	Console.WriteLine("Contains BKey: {0}, Result: {1}", "LJ02-026XN-PEP2F-M881", bResult);

	// Removal A/B-Key
	tkd.RemoveKeyA(86280);    // Removes A-Key and B-Key with value from the two key dictionary.
	bResult = tkd.ContainsKeyB("LJ02-026XN-PEP2F-M88T");	// Result would be: false;
	Console.WriteLine("Contains BKey: {0}", bResult);

	int count = tkd.Count;  // Result would be: 6 After the removal of A-Key & B-Key with value.
	Console.WriteLine("Two Key Dictionary Count: {0}", count);
	Console.WriteLine();

	// Enumeration of entries from TwoKeyValueTriple
	foreach (TwoKeyValueTriple<int, string, string> item in tkd)
	{
		Console.WriteLine("{0},  {1},  {2}", item.KeyA, item.KeyB, item.Value);
	}
	/* Output
		33024, LJ02-026XN-PEP2F-M88L, 7FwCTLnD0ZdnDmYRPbZW
		66571, LJ02-026XN-PEP2F-M88N, Y4cE253SCT3agPC96Fhd
		58647, LJ02-026XN-PEP2F-M88R, TWAggDF0jZVH454RRvrs
		87303, LJ02-026XN-PEP2F-M88Q, TuGEgtXSm9WQ6JLFGGLW
		86891, LJ02-026XN-PEP2F-M88P, ExmwnpRHWWx39dEkP6Ay
		69992, LJ02-026XN-PEP2F-M88M, cQ6RNcQcEm1KFXqRkBth	
	*/

	Console.WriteLine();

	// Enumeration of A-Keys
	foreach (int item in tkd.AKeys)
	{
		Console.WriteLine("{0}", item);
	}

	/* Output
		33024
		66571
		58647
		87303
		86891
		69992	
	*/
	Console.ReadLine();
}

Limitations

With the given code example above, the first obvious question is: what if you have both A/B-Key as integers and you assigned them the same value but each map to a different value? The current version doesn’t provide any checks for such situations. This would mean it would accept the same value for both keys. The consequence is when you try to retrieve a value by a duplicate key the result would be nondeterministic.

Source

The two key dictionary is located on GitHub [3] targeting the .NET Framework 4.0 and later with the MIT license.

References

[1] Microsoft .NET, “Online .NET Framework source code” Dec 2019. [Online]. Available: Microsoft, https://referencesource.microsoft.com/
[2] Wikipedia, “Hash table” Dec 2019. [Online]. Available: Wikipedia, https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
[3] F. Ekstrand, “Two Key Dictionary” Oct 2019. [Online]. Available: GitHub, https://github.com/FredEkstrand/TwoKeyDictionary