What data-structure should I use to represent many-to-one mapping?

Question

I have a set of objects that can be accessed with multiple keys, what structure should I use to represent this in memory? The only operation I require is a finder that will return me the value giving a key.

For example:

key: {"a","aa","aaa"}, value {1}
key: {"b","bb","bbb"}, value {2}
key: {"c","cc","ccc"}, value {3}

I would use it like this:

MyStruct.Get["a"]; // return 1
MyStruct.Get["aa"]; // return 1
MyStruct.Get["bbb"]; // return 2
MyStruct.Get["d"]; // return null

To my knowledge, this doesn't exist in the class library. You can easily create your own structure. Does the order of the keys matter? Keep that in mind... — rory.ap, Aug 02 '16 at 18:51
Order of keys does not matter, there is no pre-built structure? In Java there is HashMap. — Bill Software Engineer, Aug 02 '16 at 18:52
Possible duplicate of [C# Java HashMap equivalent](http://stackoverflow.com/questions/1273139/c-sharp-java-hashmap-equivalent) — Lorentz Vedeler, Aug 02 '16 at 18:54
If keys 'a' and 'aa' both evaluate to the same value (e.g. 1), and then you change ['a'] to another value (e.g. 0), should ['aa'] then also evaluate to the updated value (0 in this example)? — wablab, Aug 02 '16 at 18:54
If the only operation you require is a finder, how do you insert data into this structure? Not trying to be pedantic, I think it genuinely influences the answer. — Dan Forbes, Aug 02 '16 at 18:56
@DanForbes Yes, a Adder is required, I mean that's definitely nessessary. — Bill Software Engineer, Aug 02 '16 at 18:59
So what does that interface look like? Is each key mapping to the same value added separately, or do you add them all at once, like w/ an array? — Dan Forbes, Aug 02 '16 at 19:00
@DanForbes Well I don't think it matters, it would be nice if I could add them all at once like an array, but I can easily foreach the value seperately. — Bill Software Engineer, Aug 02 '16 at 19:02
I wasn't sure if Dictionary would duplicate value when added, but it seem like it does not. — Bill Software Engineer, Aug 02 '16 at 19:04

Ricardo Pieper · Accepted Answer · 2016-08-02T19:07:52.537

4

You should use a Dictionary. And you can use it like this:

Dictionary<string, int> myDict = new Dictionary<string, int>();
myDict.Add("a", 1);
myDict.Add("aa", 1);
myDict.Add("c", 3);

int result;
if (myDict.TryGetValue("a", out result)){
   //do something with result
}

Or you can do the lookup like this:

int result1 = myDict["a"]; //throws exception when the value is not present

Be careful when using your own classes for the TKey parameter. If you do so, you should override the .Equals and .GetHashCode methods.

edited Aug 02 '16 at 19:07

answered Aug 02 '16 at 18:54

Ricardo Pieper

2,613
3
26
40

Careful, strings are immutable. "1" <> "1" reference-wise. You should make that clear. For longer strings, it could be a problem. – rory.ap Aug 02 '16 at 18:56
Also, `Dictionary` throws an exception if you enter duplicated key. Worth mentioning. – Khalil Khalaf Aug 02 '16 at 18:56
@FirstStep -- not entering a dupe key, just dupe values (if you take into account my first comment, that is). – rory.ap Aug 02 '16 at 18:56
@roryap It works absolutely fine for strings. Also, there is no difference in C# between using .Equals and `==` for strings. – Ricardo Pieper Aug 02 '16 at 18:58
@RicardoPieper -- I'm not saying it doesn't work. I'm just saying it for memory purposes and efficiency, mainly. – rory.ap Aug 02 '16 at 19:00
My problem is does it all link to the same object? I mean in this example I use int, but in my actual code, I have a class object. I don't want to have to duplicate the object value. – Bill Software Engineer Aug 02 '16 at 19:00
1

@YongkeBillYu -- just pass the same object for all of your keys that reference that object. – rory.ap Aug 02 '16 at 19:01
@YongkeBillYu I recommend you override the .Equals and .GetHashCode methods when using your own class for the TKey parameter. Be explicit on how to differentiate 2 objects. – Ricardo Pieper Aug 02 '16 at 19:04
As for the TValue parameter, it does not matter, as roryap said. – Ricardo Pieper Aug 02 '16 at 19:06
@YongkeBillYu I have just read again your question. While a `Dictionary` *~solves~* the prolem, I started to think whether this is the best way to do so. In your dataset, check if you have more distinct keys than values. If you have only a handful of different values and many different keys, I think you should invert those and use a `Dictionary>` instead. However, if you absolutely need to do the lookup using the string, then go ahead, this should be good enough. – Ricardo Pieper Aug 02 '16 at 19:15
2

I think it might also be worth mentioning that when using your own type for the key that it should be immutable. Using mutable types for keys is possible but leads to a world of pain if you're not careful. – Kyle Aug 02 '16 at 19:29
@RicardoPieper Thanks a lot for the consideration, unfrotunately I have to have the Many-To-One mapping, so I guess Dictionary is the way to go! – Bill Software Engineer Aug 02 '16 at 20:05

What data-structure should I use to represent many-to-one mapping?

1 Answers1