值列表作为Map的键

Question

我有可变长度列表,其中每个项目可以是四个唯一的一个,我需要用作地图中另一个对象的键.假设每个值可以是0,1,2或3(在我的实际代码中它不是整数,但更容易用这种方式解释)所以一些关键列表的例子可能是:

[1, 0, 2, 3]
[3, 2, 1]
[1, 0, 0, 1, 1, 3]
[2, 3, 1, 1, 2]
[1, 2]

因此,要重新迭代:列表中的每个项目可以是0,1,2或3,并且列表中可以有任意数量的项目.

我的第一种方法是尝试使用.NET中内置的GetHashCode()来散列数组的内容,以组合每个元素的哈希值.但由于这将返回一个int,我将不得不手动处理冲突(两个相等的int值与Dictionary相同).

所以我的第二种方法是使用四叉树,将列表中的每个项分解为一个节点,该节点有四个指针(每个可能值一个)到下四个可能的值(根节点表示[],一个空列表),插入[1, 0, 2] => Foo,[1, 3] => Bar并[1, 0] => Baz 进入此树将如下所示:

四叉树图http://episerversucks.com/upload/Diagram1111.png

灰色节点节点是未使用的指针/节点.虽然我担心这个设置的性能,但是没有必要处理哈希冲突,树也不会变得很深(主要是存储2-6个项目的列表,很少超过6个).

有没有其他神奇的方法来存储带有值列表的项目作为我错过的键？

Answer 1

请注意,在F#中,Map数据结构可以愉快地使用list或array元素作为键; 它使用结构比较(而不是哈希码)将事物存储在持久树中.

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 k v m

printfn "%s" (Map.find [1;2] m)