List of values as keys for a Map
- by thr
I have lists of variable length where each item can be one of four unique, that I need to use as keys for another object in a map. Assume that each value can be either 0, 1, 2 or 3 (it's not integer in my real code, but a lot easier to explain this way) so a few examples of key lists could be:
[1, 0, 2, 3]
[3, 2, 1]
[1, 0, 0, 1, 1, 3]
[2, 3, 1, 1, 2]
[1, 2]
So, to re-iterate: each item in the list can be either 0, 1, 2 or 3 and there can be any number of items in a list.
My first approach was to try to hash the contents of the array, using the built in GetHashCode() in .NET to combine the hash of each element. But since this would return an int I would have to deal with collisions manually (two equal int values are identical to a Dictionary).
So my second approach was to use a quad tree, breaking down each item in the list into a Node that has four pointers (one for each possible value) to the next four possible values (with the root node representing [], an empty list), inserting [1, 0, 2] => Foo, [1, 3] => Bar and [1, 0] => Baz into this tree would look like this:
Grey nodes nodes being unused pointers/nodes. Though I worry about the performance of this setup, but there will be no need to deal with hash collisions and the tree won't become to deep (there will mostly be lists with 2-6 items stored, rarely over 6).
Is there some other magic way to store items with lists of values as keys that I have missed?
