作为键的值列表

我有可变长度的列表，其中每个项目可以是四个唯一的项目之一，我需要将其用作映射中另一个对象的项目。假设每个值可以是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值与一个字典相同）。

所以我的第二种方法是使用四叉树，将列表中的每个项目分解成一个节点，该节点具有四个指针（每个可能值一个）到接下来的四个可能的值（根节点代表[]，一个空表），插入[1, 0, 2] => Foo，[1, 3] => Bar和[1, 0] => Baz到这棵树应该是这样的：

Quad Tree Diagram http://episerversucks.com/upload/Diagram1111.png

灰色节点的节点不被使用的指针/节点。虽然我担心这个设置的性能，但是不需要处理散列冲突，并且树不会变得很深（主要是存储2-6个项目的列表，很少超过6个）。

是否有一些其他的魔术方式来存储项目的值列表作为我已经错过的键？

来源

2010-04-04 thr

[编辑 - 更改答案，以反映@gradbot和@布赖恩评论]

你说你很少会超过6元。如果您可以将最大值限制为14个元素，则可以使用GetHashCode()。由于您只需要2位来存储该值，因此在int中的32位将为您提供创建最多14个元素的唯一哈希码的可能性，并将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; 
}

如果你想使散列可逆，你将不得不使用一些位的长度。代码可以调整以允许15个元素以及@gradbot提到的。

来源

2010-04-04 18:44:51

这并不区分列表[0; 1; 2; 3]和列表[1; 2; 3]。 – Brian 2010-04-04 19:17:45

您可以通过将散列的初始值设置为1来解决此问题，但是您将自己限制为14个元素。这是我能想到的处理起始和尾随零的唯一方法。你可以调整它来处理15个元素。 – gradbot 2010-04-04 19:43:09

@Brian，@gradbot，我忘了标题0，并修改了我的代码，以1开始散列，以允许14个项目。感谢您指出。 – 2010-04-04 20:17:06

如果列表中很少有六个以上的项目，并且每个项目只有两位信息，那么我认为您要为“密钥列表”所需的结构称为“int”。 :)

只需使用例如前4位表示密钥列表（0-14）的“长”和存储实际密钥的最后28位（或更少）。然后使用Dictionary<int,Blah>其中int是密钥列表表示。

来源

2010-04-04 18:44:28 Brian

请注意，在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)

来源

2010-04-04 18:49:55 Brian

作为键的值列表

回答

相关问题