Data structure for complex keys in dictionary

Question

In case of a Dictionary where the key is complex (a combination of values) For instance, the key could be a pair of string and integer.

What data type would you recommend to use for the key? I take into account performance and memory usage in case of massive reads from the dictionary, data types that are heavy to allocate would probably not be a good candidate for the task.

I tested 4 different strategies.

The most naive one, using a string as key and concat the components:

int Read(string str, int num) { var key = str + "|" + num; return dict[key]; }

Using a tuple for representing the key:

int Read(string str, int num) { var key = new Tuple<string, int>(str, num); return dict[key]; }

Using a KeyValuePair for representing the key:

int Read(string str, int num) { var key = new KeyValuePair<string, int>(str, num); return dict[key]; }

I don't like the first method much, the one with the tuple seems more elegant. However, Tuple is not so different than a string in the sense that they are both classes and allocating them can be expensive. KeyValuePair seemed like the most viable data type but after running some tests i saw that it performs much worse than strings or tuples which now seems obvious to me given that KeyValuePair does not implement GetHashCode(). I then tried to implement my own "KeyValuePair" that overrides Equals and GetHashCode():

struct KVPair<K, V> { public K Key { get; set; } public V Value { get; set; } public KVPair(K key, V value) { Key = key; Value = value; } public override bool Equals(object obj) { if (!(obj is KVPair<K,V>)) { return false; } KVPair<K, V> other = (KVPair<K, V>)obj; return Key.Equals(other.Key) && Value.Equals(other.Value); } public override int GetHashCode() { int keyHash = Key.GetHashCode(); int valHash = Value.GetHashCode(); return (((keyHash << 5) + keyHash) ^ valHash); } }

And use it as a key in my dictionary:

 int Read(string str, int num) { var key = new KVPair<string, int>(str, num); return dict[key]; }

It seems to perform better than the string and tuple options and much better than the native KeyValuePair.

I just wanted to hear what would you recommend. I am always cautious when having to implement my own data types, since the FCL usually takes care of that.

Igor Quirino · Accepted Answer · 2016-11-22 20:37:01Z

I prefer to use especific type with related property names:

public class RowKey { public string Title { get; set; } public int Id { get; set; } public RowKey() { } public RowKey(string title, int id) { Title = title; Id = id; } public override bool Equals(object obj) { if (!(obj is RowKey)) return false; RowKey other = obj as RowKey; return Title.Equals(other.Title) && Id.Equals(other.Id); } public override int GetHashCode() { int titleHash = Title.GetHashCode(); int idHash = Id.GetHashCode(); return (((titleHash << 5) + titleHash) ^ idHash); } }

Read using:

int Read(string str, int num) { var key = new RowKey(str, num); return dict[key]; }

But isn't it the same as using a Tuple? It's a class and my considerations against it are allocations.
Yes, but, think about your code structure and organization. Tuples are generic and you can lost your context...
That's a good point against using Tuples in this case. But what about making your key a struct instead of class?
To your usecase, class can be fastest, see: dotnetperls.com/struct-versus-class

Collectives™ on Stack Overflow

Data structure for complex keys in dictionary

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related