List of values ​​as keys for the card

Question

I have variable-length lists, where each element can be one of four unique ones that I need to use as keys for another object on the map. Suppose that each value can be either 0, 1, 2, or 3 (it is not an integer in my real code, but it is much easier to explain this way), so some 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, for repeated iteration: each element in the list can be either 0, 1, 2 or 3, and there can be any number of elements in the 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 will return an int, I will have to deal with collisions manually (two identical int values ​​are identical to a dictionary).

So, my second approach was to use a square tree, breaking each item in the list into Node, which has four pointers (one for each possible value) to the following four possible values ​​(with Node root representing [] , an empty list), the insert [1, 0, 2] => Foo , [1, 3] => Bar and [1, 0] => Baz in this tree will look like this:

Square tree diagram http://episerversucks.com/upload/Diagram1111.png

Gray node nodes are unused pointers / nodes. Although I worry about the performance of this installation, there will be no need to deal with hash collisions and the tree will not become deep (basically there will be lists with 2-6 stored items, rarely more than 6).

Is there another magic way to store items with lists of values ​​as missing keys?

Answer 1

[Edit - Modified answer to reflect @gradbot and @Brian comments]

You say that you rarely have more than 6 items. If you can limit up to a maximum of 14 elements, you can use GetHashCode() . Since only 2 bits are required to store the value, 32 bits in int will give you the opportunity to create a unique hash code of up to 14 elements and take into account the value 0.

 int[] arr = new [] { 1, 2, 3, 0, 1, 2, 3 }; public override int GetHashCode() { if(arr.Length > 14) throw new Exception("max elems is 14"); int hash = 1; // start with 1 to take into account a heading 0 foreach (int i in arr) { hash = hash << 2; hash += i; } return hash; } 

If you want to make hash reversible, you will have to use some bits for length. And the code can be modified to allow 15 elements, as well as @gradbot mentioned.

Answer 2

Note that in F #, the Map data structure can happily use list or array elements as keys; it uses structural comparison (not hash code) to store things in a persistent tree.

 let myData = [ [0;1;3], "foo" [1;2], "bar" [3;1;2;0;3], "qux" ] let mutable m = Map.empty for k,v in myData do m <- Map.add kvm printfn "%s" (Map.find [1;2] m) 

Answer 3

If a list rarely contains more than six elements, and each element has only two bits of information, I think that the structure you want for your "key lists" is called "int". :)

Just use for example. the first 4 bits to say how long the list of keys is (0-14) and the last 28 (or less) bits to store the actual key. Then use Dictionary<int,Blah> , where int is the representation of the list of keys.