11

我正在寻找一种可以使用多个键进行搜索的数据结构。用一个例子更容易解释：

var myDataStructure = new MultiKeyDataStructure<int, string, MyType>();
myDataStructure.Add(1, "some string 1", new MyType());
myDataStructure.Add(2, "some string 2", new MyType());

var myType = new MyType();
myDataStructure.Add(3, "some string 3", myType);

Tuple<string, MyType> t1 = myDataStructure[1];
Tuple<int, MyType> t2 = myDataStructure["some string 1"];
Tuple<int, string> t3 = myDataStructure[myType];

像这样的事情是否可能，如果是这样，是否有任何已经存在的东西可以做到这一点？您将如何实现将所有内容都视为键并通过搜索其中任何一个来返回所有关联键的东西？

理想情况下，您还可以使用任意数量和/或类型的参数：

var myDataStructure = new MultiKeyDataStructure<int, string, Foo, Bar>();
4

8 回答 8

5

所以这里有一个适用于三个键的。您可以按照列出的模式为 4、5、6 等键制作一个。这将是很多代码，但不是特别困难的任务（只是乏味）。

请注意，由于键的每个部分都有一个字典，因此会占用大量内存；这就是您为从任何密钥访问非常事实的灵活性所付出的代价。

public class MultiKeyDictionary<T1, T2, T3>
{
    private Dictionary<T1, Tuple<T1, T2, T3>> firstLookup = new Dictionary<T1, Tuple<T1, T2, T3>>();
    private Dictionary<T2, Tuple<T1, T2, T3>> secondLookup = new Dictionary<T2, Tuple<T1, T2, T3>>();
    private Dictionary<T3, Tuple<T1, T2, T3>> thirdLookup = new Dictionary<T3, Tuple<T1, T2, T3>>();

    public void Add(Tuple<T1, T2, T3> values)
    {
        if (!firstLookup.ContainsKey(values.Item1) &&
            !secondLookup.ContainsKey(values.Item2) &&
            !thirdLookup.ContainsKey(values.Item3))
        {
            firstLookup.Add(values.Item1, values);
            secondLookup.Add(values.Item2, values);
            thirdLookup.Add(values.Item3, values);
        }
        else
        {
            //throw an exeption or something.
        }
    }

    public Tuple<T1, T2, T3> GetFirst(T1 key)
    {
        return firstLookup[key];
    }

    public Tuple<T1, T2, T3> GetSecond(T2 key)
    {
        return secondLookup[key];
    }

    public Tuple<T1, T2, T3> GetThird(T3 key)
    {
        return thirdLookup[key];
    }

    public void RemoveFirst(T1 key)
    {
        var values = GetFirst(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }

    public void RemoveSecond(T2 key)
    {
        var values = GetSecond(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }

    public void RemoveThird(T3 key)
    {
        var values = GetThird(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }
}

下面是一种完全不同的方法。它不是为每个键填充查找，而是将所有值存储在单个集合中并执行线性搜索以查找给定键的项目。它将有 O(n) 搜索/删除时间，但 O(1) 添加。之前的实现有 O(1) 的添加、删除和搜索，但是会占用更多的内存。

public class MultiKeyDictionary2<T1, T2, T3>
{
    private HashSet<Tuple<T1, T2, T3>> lookup = new HashSet<Tuple<T1, T2, T3>>();
    private HashSet<T1> firstKeys = new HashSet<T1>();
    private HashSet<T2> secondKeys = new HashSet<T2>();
    private HashSet<T3> thirdKeys = new HashSet<T3>();

    public void Add(Tuple<T1, T2, T3> values)
    {
        if (lookup.Any(multiKey => object.Equals(multiKey.Item1, values.Item1) ||
            object.Equals(multiKey.Item2, values.Item2) ||
            object.Equals(multiKey.Item3, values.Item3)))
        {
            //throw an exception or something
        }
        else
        {
            lookup.Add(values);
        }
    }

    public Tuple<T1, T2, T3> GetFirst(T1 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item1, key));
    }

    public Tuple<T1, T2, T3> GetSecond(T2 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item2, key));
    }

    public Tuple<T1, T2, T3> GetThird(T3 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item3, key));
    }

    public void RemoveFirst(T1 key)
    {
        var values = GetFirst(key);
        if (values != null)
            lookup.Remove(values);
    }

    public void RemoveSecond(T2 key)
    {
        var values = GetSecond(key);
        if (values != null)
            lookup.Remove(values);
    }

    public void RemoveThird(T3 key)
    {
        var values = GetThird(key);
        if (values != null)
            lookup.Remove(values);
    }
}
于 2013-01-11T17:16:13.833 回答
2

首先，不幸的是没有内置任何东西，所以你必须手动实现一些东西。

这里的问题是你不能有一个具有未指定数量的泛型类型定义的类，即不存在这样的东西：

class MultiKeyDictionary<T1, ...>
{}

因此，您可以决定实现某些情况（2 键、3 键等，使用类似于Tuple<>实现的方法），或者您应该放弃类型安全。

如果您决定采用第一种方法，您应该可以执行以下操作（例如使用 3 个键）：

class ThreeKeysDict<T1,T2,T3>
{
   var dict1 = new Dictionary<T1,Tuple<T2,T3>>();
   var dict2 = new Dictionary<T2,Tuple<T1,T3>>();
   var dict3 = new Dictionary<T3,Tuple<T1,T2>>();
   public void Add(T1 key1,T2 key2, T3 key3)
   {
      dict1.Add(key1,Tuple.Create(key2,key3));
      dict2.Add(key2,Tuple.Create(key1,key3));
      dict3.Add(key3,Tuple.Create(key1,key2));
   }
   public Tuple<T2,T3> GetByKey1(T1 key1)
   {
      return dict1[key1];
   }
   public Tuple<T1,T3> GetByKey2(T2 key2)
   {
      return dict2[key2];
   }
   public Tuple<T1,T2> GetByKey3(T3 key3)
   {
      return dict3[key3];
   }
}

非通用版本将是这样的：

class MultiKeyDict
{
    Dictionary<object, object[]>[] indexesByKey;
    public MultiKeyDict(int nKeys)
    {
        indexesByKey = new Dictionary<object, object[]>[nKeys];
    }
    public void Add(params object[] values)
    {
        if (values.Length != indexesByKey.Length)
            throw new ArgumentException("Wrong number of arguments given");
        var objects = values.ToArray();
        for (int i = 0; i < indexesByKey.Length; i++)
            this.indexesByKey[i].Add(values[i], objects);
    }
    public object[] Get(int keyNum, object key)
    {
        return this.indexesByKey[keyNum][key];
    }
}

如果不同键的数量增加，这两种方法都会使用大量内存（因为它们为每个键采用一个字典）。

免责声明：

这些代码没有经过测试，也没有空值/超出范围检查等。
它们只是为了给你一个整体的想法。

于 2013-01-11T17:36:52.587 回答
2

既然您说您想要编译时类型安全，那么您必须放弃许多事情：

  1. 具有任意数量参数的能力（C# 没有可变参数泛型）
  2. 拥有多个相同类型的键的能力（编译器会抱怨不明确的重载）

这两个限制可以通过使用基于反射的方法来解决，但是你会失去编译时类型的安全性。

因此，根据您的限制，这是您将使用的解决方案（仅在所有泛型类型不同时才有效！）

class TripleKeyDictionnary<TKey1, TKey2, TKey3>
{
    public Tuple<TKey2, TKey3> this[TKey1 key]
    {
        get
        {
            return _key1Lookup[key];
        }
    }

    public Tuple<TKey1, TKey3> this[TKey2 key]
    {
        get
        {
            return _key2Lookup[key];
        }
    }

    public Tuple<TKey1, TKey2> this[TKey3 key]
    {
        get
        {
            return _key3Lookup[key];
        }
    }

    private Dictionary<TKey1, Tuple<TKey2, TKey3>> _key1Lookup = new Dictionary<TKey1, Tuple<TKey2, TKey3>>();
    private Dictionary<TKey2, Tuple<TKey1, TKey3>> _key2Lookup = new Dictionary<TKey2, Tuple<TKey1, TKey3>>();
    private Dictionary<TKey3, Tuple<TKey1, TKey2>> _key3Lookup = new Dictionary<TKey3, Tuple<TKey1, TKey2>>();

    public void Add(TKey1 key1, TKey2 key2, TKey3 key3)
    {
        _key1Lookup.Add(key1, Tuple.Create(key2, key3));
        _key2Lookup.Add(key2, Tuple.Create(key1, key3));
        _key3Lookup.Add(key3, Tuple.Create(key1, key2));
    }
}
于 2013-01-11T17:22:45.613 回答
1

当我遇到这样的情况时，我只使用两个字典，而不是尝试提出一些新的数据结构。每个字典都有一个映射到值的可能键。

如果你真的希望它被抽象，你总是可以创建一个内部使用两个或更多字典的类，这取决于你需要多少不同类型的键。

于 2013-01-11T17:19:32.550 回答
0

我不确定是否存在任何这样的数据结构，但您可以创建一个。

假设键/子键是唯一的

以下是MultiKeyDictionary（使用 2 个内部字典，一个用于键（as object），一个用于值）。

public class MultiKeyDictionary<TValue> 
{
    private Dictionary<Guid, TValue> values;
    private Dictionary<Object, Guid> keys;

    public MultiKeyDictionary()
    {
        keys = new Dictionary<Object,Guid>();
        values = new Dictionary<Guid,TValue>();
    }
    public IEnumerable<Object> Keys
    {
        get { return keys.Keys.AsEnumerable();} // May group according to values here
    }

    public IEnumerable<TValue> Values
    {
        get { return values.Values;}
    }

    public TValue this[object key]
    {
        get 
        {
            if (keys.ContainsKey(key)) 
            {
                var internalKey = keys[key];
                return values[internalKey];
            }
            throw new KeyNotFoundException();
        }
    }


    public void Add(TValue value,object key1, params object[] keys) // key1 to force minimum 1 key
    {
        Add(key1 , value);
        foreach( var key in keys)
        {
        Add (key, value);
        }
    }

    private void Add(Object key, TValue value)
    {
        var internalKey = Guid.NewGuid();
        keys.Add( key, internalKey);
        values.Add(internalKey, value);     
    }   
}

它可以用作

MultiKeyDictionary<string> dict = new MultiKeyDictionary<string>();
dict.Add("Hello" , 1,2,3,"StringKey"); // First item is value, remaining all are keys
Console.WriteLine(dict[1]); // Note 1 is key and not intex
Console.WriteLine(dict[2]); // Note 2 is key and not index
Console.WriteLine(dict["StringKey"]);
于 2013-01-11T17:38:07.957 回答
0

怎么样

class MultiKeyLookup<A, B, C> : IEnumerable<Tuple<A, B, C>>
{
    private readonly ILookup<A, Tuple<B, C>> a;
    private readonly ILookup<B, Tuple<A, C>> b;
    private readonly ILookup<C, Tuple<A, B>> c;
    private readonly IEnumerable<Tuple<A, B, C>> order;

    public MultiKeyLookup(IEnumerable<Tuple<A, B, C>> source)
    {
        this.order = source.ToList();
        this.a = this.order.ToLookup(
            o => o.Item1, 
            o => new Tuple<B, C>(o.Item2, o.Item3));
        this.b = this.order.ToLookup(
            o => o.Item2, 
            o => new Tuple<A, C>(o.Item1, o.Item3));
        this.c = this.order.ToLookup(
            o => o.Item3, 
            o => new Tuple<A, B>(o.Item1, o.Item2));
    }

    public ILookup<A, Tuple<B, C>> Item1
    {
        get
        {
            return this.a
        }
    }

    public ILookup<B, Tuple<A, C>> Item2
    {
        get
        {
            return this.b
        }
    }

    public ILookup<C, Tuple<A, B>> Item3
    {
        get
        {
            return this.c
        }
    }

    public IEnumerator<Tuple<A, B, C>> GetEnumerator()
    {
        this.order.GetEnumerator();
    }

    public IEnumerator IEnumerable.GetEnumerator()
    {
        this.order.GetEnumerator();
    }
}

您会使用哪个，

var multiKeyLookup = new MultiKeyLookup(
    new[] {
        Tuple.Create(1, "some string 1", new MyType()),
        Tuple.Create(2, "some string 2", new MyType())}); 

var intMatches = multiKeyLookup.Item1[1];
var stringMatches = multiKeyLookup.Item2["some string 1"];
var typeMatches = multiKeyLookup.Item3[myType];
于 2013-01-11T18:14:32.920 回答
0

您可以获得的最接近的东西可能是HashSet<Tuple<int, string, MyType>>. HashSets 自动检查重复项，并Tuple检查它的值是否相等。 

class MultiKey<T1, T2, T3> : HashSet<Tuple<T1, T2, T3>>
{
    public bool Add(T1 t1, T2 t2, T3 t3)
    {
        return this.Add(Tuple.Create(t1, t2, t3));
    }
    public T1 Get(T2 t2, T3 t3)
    {
        var match = this.SingleOrDefault(x => x.Item2.Equals(t2) && x.Item3.Equals(t3));
        if (match == null) return default(T1);
        else return match.Item1;
    }
    public T2 Get(T1 t1, T3 t3)
    {
        var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item3.Equals(t3));
        if (match == null) return default(T2);
        else return match.Item2;
    }
    public T3 Get(T1 t1, T2 t2)
    {
        var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item2.Equals(t2));
        if (match == null) return default(T3);
        else return match.Item3;
    }
}

用法：

key.Add(1, "Foo", new MyType("foo"));
key.Add(2, "Bar", new MyType("bar"));
key.Add(2, "Bar", new MyType("bar")); // Does not add, because it already exists.
var key1 = key.Get("Bar", new Foo("bar")); // Returns 2
var defaultKey = key.Get("Bar", new Foo("foo")); // Returns 0, the default value for an int
var key2 = key.Get(1, new Foo("foo")); // returns "Foo"

MyType如果您将它与很多news一起使用，您需要确保根据其值比较相等性。否则，创建一个新的将保证一个独特的价值。

于 2013-01-11T17:13:50.463 回答
-2

System.Tuple添加时牢记将其用作字典键。用法：

var dict = new Dictionary<Tuple<string, int>, DateTime>();
dict.Add(Tuple.Create("Louis", 14), new DateTime(1638, 9, 5));

虽然元组语法很麻烦，但静态工厂方法在创建站点上承担了很多痛苦。

于 2013-01-11T17:06:37.270 回答