代码之家 › 专栏 › 技术社区 › thr

作为映射键的值列表

f# data-structures algorithm .net c#

4

thr · 技术社区 · 16 年前

我有可变长度的列表,其中每个项目可以是四个唯一的项目之一,我需要将其用作地图中另一个对象的键。假设每个值都可以是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个)。

是否还有其他一些神奇的方法可以将值列表中的项存储为我遗漏的键?

3 回复 | 直到 16 年前

1

Mikael Svenson 16 年前

[编辑-更改了答案以反映@gradbot和@brian的评论]

你是说你很少会有超过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所提到的那样。

2

6

Brian 16 年前

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

3

1

Brian 16 年前

如果列表中的项目很少超过六个,并且每个项目只有两位信息,那么我认为您需要的“关键列表”结构称为“int”。:)

只需使用前4位来表示密钥列表的长度(0-14),最后28位(或更少)用于存储实际密钥。然后使用 Dictionary<int,Blah> 其中int是键列表表示形式。