3 
Dictionary<string, Dictionary<string, ... >...> nestedDictionary;

上面从上到下在每个级别Dictionary都有关系。one-to-many添加一个项目非常容易，因为我们有叶子对象，我们从底部开始，创建字典并将每个字典添加到相关的父...

我的问题是当我想在内部词典中找到一个项目时。有两种选择：

  1. 嵌套foreach并找到该项目，然后在我们找到该项目的那一刻对所有循环进行快照并退出所有循环。然后我们知道项目谱系是 string1->string2->...->stringN。此解决方案的问题是 A) 性能 B) 线程安全（因为我想删除该项目，如果它没有子项，则为父项，如果没有子项则为父项......）
  2. 创建反向查找字典并索引添加的项目。类似于Tuple所有外部词典的 a 。然后将该项目添加为键，并将所有外部父项添加为 Tuple成员。Dictionary问题：A) 冗余 B)与 main保持同步反向查找Dictionary。

对快速且线程安全的解决方案有任何想法吗？

4

2 回答 2

1

看起来你实际上有两个以上的Dictionary. 由于您不能使用此类型语法支持可变数量的字典：

 Dictionary<string, Dictionary<string, ... >...> nestedDictionary;

我只能假设它是大于二的某个数字。假设它是三个。对于您构建的任何数据结构，您都有想要高效执行的预期用途和操作。

我假设你需要这样的电话：

var dictionary = new ThreeLevelDictionary();
dictionary.Add(string1, string2, string3, value);
var value = dictionary[string1, string2, string3];
dictionary.Remove(string1, string2, string3);

并且（对问题至关重要）您描述的反向查找：

var strings = dictionary.FindKeys(value);

如果这些是您需要执行并快速执行的操作，那么您可以使用的一种数据结构是Dictionary带Tuple键的：

public class ThreeLevelDictionary<TValue> : Dictionary<Tuple<string, string, string>, TValue>
{
    public void Add(string s1, string s2, string s3, TValue value)
    {
        Add(Tuple.Create(s1, s2, s3), value);
    }

    public TValue this[string s1, string s2, string s3]
    {
        get { return this[Tuple.Create(s1, s2, s3)]; }
        set { value = this[Tuple.Create(s1, s2, s3)]; }
    }

    public void Remove(string s1, string s2, string s3)
    {
        Remove(Tuple.Create(s1, s2, s3);
    }

    public IEnumerable<string> FindKeys(TValue value)
    {
        foreach (var key in Keys)
        {
            if (EqualityComparer<TValue>.Default.Equals(this[key], value))
                return new string[] { key.Item1, key.Item2, key.Item3 };
        }
        throw new InvalidOperationException("missing value");
    }
}

现在，如果性能表明这是一个瓶颈，您就可以完美地使用另一个创建反向查找哈希表。 Dictionary

如果之前喜欢的操作不是您想要执行的操作，那么此数据结构可能无法满足您的需求。无论哪种方式，如果您首先描述总结您希望数据结构做什么的接口，那么更容易查看是否有其他替代方案。

于 2011-05-21T02:58:44.793 回答
1

虽然我对C5 集合库没有什么直接经验，但听起来你可以使用他们的TreeDictionary类。它带有一整套有用的方法来查找、迭代和修改树，并且文档记录得很好。

另一种选择是使用 QuickGraph 库（可以在 NuGet 或 codeplex 中找到）。这涉及到一些图论知识，但在其他方面是一个非常有用的库。

这两个库都要求您处理并发，就像标准 BCL 集合一样。

于 2011-05-21T03:40:09.717 回答