Geek asks and answers

Reverse Nested Dictionary Search

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

Above Dictionaryis related one-to-manyat each level from top to bottom. Adding an element is pretty simple since we have a sheet object, and we start at the bottom by creating dictionaries and adding them to the corresponding parent object ...

My problem is when I want to find an item in internal dictionaries. There are two options:

  • Nested foreachand find the element then a snapshot of all the loops at the moment we found the element and exit all the loops. Then we know the pedigree item string1-> string2 → ...-> stringN. Problems with this solution: A) Performance B) Thread safety (since I want to remove the element parent if it does not have a child, and it is parent if it does not have a child ...)
  • Create a reverse search dictionary and index added items. Something like a Tuplefor all external dictionaries. Then add the item as a key and all external parents as Tuple. Task: A) Reservation B) Keeping a synchronized reverse lookup Dictionaryfrom the main Dictionary.

Any idea for a quick and thread safe solution?

+3
source share
2 answers

It looks like you actually have more than two levels Dictionary. Since you cannot support a variable number of dictionaries using this type of syntax:

 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");
    }
}

hashtable, Dictionary, , .

, , . , , , , , , .

+1

C5, , TreeDictionary. , .

- QuickGraph ( NuGet ). , .

, concurrency, BCL.

+1

More articles:


All Articles